Full utilization of communication resources
David S. Greenberg · 1992
Many important scientific computations can be decomposed into iterative tasks with regular, structured data dependencies. The orchestration of tens of thousands of processors to jointly solve these problems requires mapping the data dependencies to the processor interconnection network. In this thesis we compare candidate networks in terms of both their ability to maintain locality of data for common dependence graphs and their efficiency in using physical resources. Classic graph embeddings fail to exploit physical resources of interconnection networks. For example, the binary reflected gray code uses only a small fraction of the edges of the hypercube. Consequently, there is poor utilization of pins on the chip periphery--a critical resource. By ignoring physical constraints the classic embeddings waste resources and unfairly bias comparisons between networks. This thesis shows how to use multiple-path and multiple-copy embeddings to efficiently utilize the pin resources of the hypercube while simulating meshes, trees, and FFT-like graphs. These results show that when comparisons are made in a pin-constrained model the hypercube is still capable of efficient simulations. The techniques used for hypercubes are generalized and applied to k-ary n-cubes. The effect of wire length on network performance is also explored and it is shown that a moderate number of additional pins can reduce the effect of wire delay on tree networks but not on hypercube networks.