On Packing and Embedding Hypercubes into Star Graphs
Resumo
Packing is a graph simulation technique hy which pk node-disjoint copies of a guest graph G(k) are embedded into a host graph H(n). Many advantages result from this technique as opposed to a simple embedding of G(k) into H(n). The multiple copies of G(k) can execute different instances of any algorithm designed to run in G(k), providing high throughput via an efficient, low-expansion utilization of H(n). Task migration mechanisms between the multiple copies of G(k) also become possible, allowing a proper allocation of the processors of H(n), load balancing and support of fault tolerance. Other advantages that arise from a well-devised packing technique are variable-dilation embeddings and multiple-sized packings. A variable-dilation embedding consists of connecting c copies of a graph G(k), packed into a host graph H(n) wilh dilation d, such as to obtain an emhedding of a graph G(k+l), l > 0, into H(n). The resulting embedding has dilation d when the nodes of G(k+l) communicate over the first k dimensions of G(k+l), and dilation di > d when a dimension i, k < i ≤ k + l, is used. Since many parallel algorithms use a restricted number of dimensions of the guest graph at any given step (e.g., SIMD-based algorithms), the resulting communication slowdown can be made significantly small on the average. We also extend the concept of connecting node-disjoint copies of a graph G(k) to obtain multiple-sized packings, in which graphs G(k), G(k + 1), ... , G(k + l) of various sizes are packed into a host graph H(n). Multiple-sized packings allow tasks with different processor requirements to be allocated proper guest graphs G(k + j) in H(n) (variable-dilation embeddings result when j > 0). This paper focuses on the problem of packing hypercubes Q(n-2) and Q(n-1) into a star graph S(n) with dilation 3. We show that 3 · [n/2]! · [(n-1)/2]! copies of Q(n-2) or [n/2]! · [(n-1)/2]! copies of Q(n-1) can be packed into S(n), with expansion n!/3 · [n/2]! · ((n-1)/2]! · 2n-2 and n!/ [n/2]! · [(n-1)/2]! · 2n-1, respectively. We also show how to connect packed Q(n-1)'s to obtain a variable-dilation embedding of Q(n - 1 + l), l ≤ [log2(ln/2]! · [(n-1)/2]!)], into S(n). Such an emhedding has dilation 3 for the first (n-1) dimensions of Q(n - 1 + l) and guarantees a minimal slowdown by using a slightly higher dilation (4 in most cases) for the remaining dimensions of Q(n - 1 + l). Finally, we also address the issue of multiple-sized packings of hypercubes into S(n).
Referências
S. B. Akers and B. Krishnamurthy, "A Group-Theoretic Model for Symmetric Interconnection Networks," Proc. Int 'l Conf. on Parallel Processing, 1986, pp. 216-223.
Y. Saad and M. H. Schultz, "Topological Properties of Hypercubes," IEEE Transactions on Computers, Vol. 37, No. 7, July 1988, pp. 867-872.
K. Oay and A. Tripathi, "A Comparative Study of Topological Properties of Hypercubes and Star Graphs," IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 1, January 1994, pp. 31-38.
C. L. Seitz, "The Cosmic Cube," Communications of the ACM, Vol. 28, No. 1, January 1985, pp. 22-33.
W. D. Hillis, The Connection Machine, Cambridge, MA: MIT Press, 1985.
J. P. Hayes and T . Mudge, "Hypercube Supercomputers," Proceedings of the IEEE, Vol. 77, No. 12, December 1989, pp. 1829-1841.
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays. Trees Hypercubes, Morgan Kauffmann Publishers, San Mateo, California, 1992, pp. 466-469.
M. Nigam, S. Sahni and B. Krishnamurthy, "Embedding Hamiltonians and Hypercubes in Star Interconnection Networks," Proc. Int 'l. Conf. Parallel Processing, 1990, pp. 340-343.
Z. Miller, O. Pritikin and I. H. Sudborough, "Near Embeddings of Hypercubes into Cayley Graphs on the Symmetric Group ," IEEE Transactions on Computers, Vol. 43, No. 1, January 1994, pp. 13-22.
M.-S. Chen and K. G. Shin, "Subcube Allocation and Task Migration in Hypercube Multiprocessors," IEEE Transactions on Computers, Vol. 39, No. 9, September 1990, pp. 1146-1155.
O. Kang, B. M. Kim, H. Yoon, S. R. Maeng and others, "A Graph-Based Subcube Allocation and Task Migration in Hypercube Systems," Proceedings of the Fourth Symposium on the Frontiers of Massively Parallel Computation, October 1992, IEEE Computer Society Press, pp. 535-538.
S. Ranka, J.-C. Wang and N. Yeh, "Embedding meshes on the Star Graph," Journal of Parallel and Distributed Computing 19, 1993, pp. 131-135.
D. E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, 1968, pp. 73, pp. 176-177.
