On Packing and Embedding Hypercubes into Star Graphs - Azevedo, Marcelo Moraes de; Latifi, Shahram; Bagherzadeh, Nader (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 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 d i > 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]! · 2 n-2 and n!/ [n/2]! · [(n-1)/2]! · 2 n-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 ≤ [log 2 (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).