High-performance communication in parallel computers

The main emphasis of this dissertation is communication within parallel computers. Chapter 1 is an introduction to different work on communication within hypercube computers. In Chapter 2 we study scheduling routing of (1) broadcasting, (2) completely broadcasting, (3) scattering, (4) completely scattering, and (5) permutation for a fixed k dimensional t-m hypercube. All cases show we can get speedup with increasing communication ports. The permutation algorithm proposed here is deterministic. Then in Chapter 3 we extend the work to k-ary n-cubes. In Chapter 4 we look at how communication performance is affected in one node when the arriving messages have a Poisson distribution. In communication networks the performance under Poisson distribution often represents a conservative result. The node is assumed to have a fixed communication cycle. The service rate for each packet is fixed. Two or more messages that want to go to the same channel can be combined. A method for performing any permutation using two passes through a multistage interconnection network is presented in Chapter 5. The method works for any network that can connect each input to each output using a set of N non-blocking connections. The method is computationally simple and deterministic. Messages must be broken into N submessages of at least one bit each that are sent independently, where N is the number of ports on the network. The method can be structured so that the network is controlled externally, hence the switches need have no intelligence. Pipelining of successive permutations is supported, as is partitioning of the network into independent subnetworks, each capable of simultaneously routing a different permutation.