ON SOME DESIGN ASPECTS OF INTERCONNECTION NETWORKS FOR TIGHTLY COUPLED MULTIPROCESSOR SYSTEMS

Abstract

Tightly connected multiprocessor systems (MPSs) are Characterized by the presence of several autonomous processors sharing multiple memory modules via some interconnection network. Since both the basic elements, processors and memory modules, are available as standard integrated circuits, the key design problem is how to put them together so that the system is efficient and reliable. The present work is a study of the interconnecting structures covering both design and analysis aspects. The interconnection networks (INs) considered are a) multiple bus b) crossbar c) multiport memory and d) multistage interconnection network. Methodologies are presented for the design of MPs by considering a variety of performance measures as no single measure gives a truly accurate estimate of the system performance. The criteria considered are : processor - memory interference, fault tolerance and some fundamental measures such as waiting time and hardware utilization. In the design of an MPS there exists enormous number of alternative decisions. In this thesis, the major design parameters that are allowed to vary for a given architecture are number of processors, memory modules, interconnection links, and the parameters of the computation being executed, such as the memory request probabilty (MRP) and memory access probabilities (MAP's). The performance of multiple-bus IN for MPS is analyzed taking into account conflicts arising from memory and bus interference. Given the number of processors, the number of memory modules, the MRP and the MAP's, the model produces as output the memory bandwidth, processor utilization, memory utilization, channel utilization and waiting time of a processor while waiting to access a memory module. Using this model it is possible to analyze the effect of input parameters on the system performance. The model presented differs from other models in its ability to allow generalized processsor demand patterns for memory access with processors of equal memory request probabilites. This model also examines the following three situations : when a memory module is equally likely to be addressed by all processors, when each processor has a different favourite memory and when all processors have the same favourite memory. Crossbar is a special case of this analysis. The closed form solutions are compared with simulation results. This analysis is extended to partially connected bus and also to Delta Network, a multistage interconnection network. The modeling technique adapted for the analysis is based on t-out-of-s system principle. Algorithms for computing the exact system reliability of t-out-of-s systems are proposed. These are simple, easy to implement, fast and memory and time efficient. The two types of real time systems, failure-critical and non failure-critical are considered. Using failure-critical models expressions for multiple -bus, crossbar and multiport memory INs are derived for the criterion, multiprocessing and terminal reliabilities. A technique for computing multiprocessor reliability through explicit path enumeration is also proposed. Non failure -critical models for the analysis of multiprocessing reliability and bandwidth availability are made, where coverage factors take into account the reconfiguration process for a graceful degradation in persence of failure of system components. The INs considered for analysis are multiple-bus and crossbar.