Interprocessor communication in distributed memory multiprocessors
Youran Lan · Michigan State University Libraries · 1988
Distributed memory multiprocessors (DMMPs) have gained much attention recently due to their unique architectural characteristics to establish a massively parallel processing environment. In such systems, the interprocessor communication mechanism has been identified as the major source of system bottleneck. Thus, an efficient interprocessor communication mechanism is the key to the future success of DMMPs. This motivates the study of a fast, versatile, and fault-tolerant interprocessor communication mechanism for DMMPs. Both store-and-forward and virtual cut-through communication techniques are discussed. Formal models are developed to facilitate the performance comparison of these two techniques. Three types of interprocessor communication patterns are demanded from application point of view, which are unicast (one-to-one), multicast (one-to-many), and broadcast (one-to-all). A graph theoretical model, namely the optimal multicast tree, is proposed to characterize these communication patterns and to define the performance evaluation criteria, time and traffic. The multicast communication, in particular, is highly demanded, but not directly supported by any existing DMMP. A distributed multicast algorithm based on a heuristic greedy method is proposed. In addition to guaranteeing a shortest path for message delivery between the source and each destination, the total traffic created is very close to the optimal solution. More importantly, the algorithm can be efficiently implemented in hardware using the virtual cut-through technique. The architecture of the hardware router is presented. A prototype router design for a 3-cube has been fabricated by MOSIS using the 3 micron CMOS technology. Enhancement to the proposed algorithm and its hardware implementation is studied, which allows the communication mechanism to be able to handle interprocessor communication in a faulty hypercube in which each fault-free node has at most one faulty neighboring node. In summary, centered around the interprocessor communication issue, this dissertation focuses on modeling, algorithm development, and hardware implementation of a versatile and efficient communication mechanism. The proposed communication mechanism is novel in the sense that it is the first communication hardware for DMMPs which directly supports all three types of communications, and the first one which has fault-tolerant capability. It can be readily applied to future generations of DMMPs to significantly increase overall system performance.