On Packing and Embedding Hypercubes into Star Graphs
Marcelo Moraes de Azevedo, Shahram Latifi, Nader Bagherzadeh · 1994
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 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).