A Link-Disjoint Subcube for Processor Allocation in Hypercube Computers

Jong-Uk Kim, Kyu-Hyun Shim , Kyu Ho Park

Parallel Computing Vol. 22, pp.1579-1595, 1997

Abstract

We propose a new type of subcubes, called link-disjoint subcubes (LS), which can be used for the subcube as in the problem in hypercube computers. A link-disjoint subcube is not a contiguous subcube as in the previous schemes, but this subcube still has no common communication link with any other subcubes. When link-disjoint subcubes are used, the performance degradition caused by non-contiguous processor allocation is lower than 1.0% in many cases. With the availability of link-disjoint subcube, there are [n/2]n-2Ck-12^(n-k) k-dimensional LSs recognizable in an n-dimensional hypercube. The number of all the recognizable subcubes under our allocation scheme is ([n/2](n-k)k+n(n-1))/n(n-1) times that under the previous schemes.

1. Introduction

Definition 1 (Continguous subcube). A k-dimensional contiguous subcubes (k-CS) of an n-cube is, in itself, a k-cube which is a subgraph of the given n-cube graph, where 0≦k≦n.

For example, one 2-CS δ of an 3-cube

N(δ) = { 000,001,010,011}

δ is noted by 0xx

The number of k-CSs in an n-cube is nCk*2^(n-k),where 0≦k≦n.

For example, 0000xxx0.

The buddy strategy recongnizes only 2^(n-k) k-subcubes out of nCk2^(n-k) within an n-cube copmuter

The subcube recognintion ability of single gray code (SGC) strategy is 2^(n-k+1)

.

0000 0110 1100 1010

0001 0111 1101 1011

0011 0101 1111 1001

0010 0100 1110 1000

Which is twice that of the buddy strategy, and it's extended version, the Multiple gray code(MGC) strategy, can achieve full recognition of all the available subcubes of any size using nCn/2GCs.

Recently, several kinds of approaches with full recognition abilities have been reported such as maximal set of subcubes(MSS) approach, tree collapsing(TC) strategy, free-list strategy, prime cube graph approach, MSIS approach.

2. Link-disjoint subcube

Definition 2 (Exact distance). The exact distance, E, between two CSs α, β in an n-cube is defined as

Where e(α,β) = 0 if < αi=0,βi=0 > or <αi=1,βi=1> or <αi=x,βi=x>, and e(αi,βi) = 1 otherwise.

Definition (Link-disjoint subcube). A k-dimensional link-disjoint subcube(k-LS),,of an n-cube(1≦k≦n-1),is defined as a graph with the following nodes and links of two (k-1)-CSs,

α=αn-1αn-2……α2l-1α2l-2……α1α0

β=βn-1βn-2……β2l-1β2l-2……β1β0

N(δ)=N(α)∪N(β)

L(δ)=L(α)∪L(β)∪B(α,β)

H(α,β)=2;E(α,β)=2 and < α2l-1≠β2l-1 and α2l-2≠β2l-2, 1≦l≦(n/2)>

An LS, can be addressed by the symbols in . We can retrieve its constituent CSs using the two following rules:

[R1] If there are two s's in the address, we substitute them by two 0's first, and then by two 1's. The two substitutecd addresses represent two subset of N(δ).

[R2] If there are two t's in the address, we substitute them by 0 and 1, and then by 1 and 0. Now, the two addresses represent the two subsets of N(δ).

For example, δ=ssxx

α=00xx

β=11xx

a=01x1

b=10x0

Some structural properties of an LS can be extracted from the defintition and the two rules directly. They are listed below.

[P1] A k-LS is composed of two (k-1)-CS's whose Hamming distance is 2.

[P2] The distance between any pair of nodes in a k-LS is less than or equal to (k+1).

[P3] Every bridge of an LS consists of links. One node of the link is included in the LS while the other is not.

Theorem An n-cube is link-disjoint under an LS-decomposition.

The number of k-LSs in an n-cube is [n/2]n-2Ck-12^(n-k), where 1≦k≦n-1 and 2≦n.

The number of all the recognizable subcubes under a CLS-decomposition is

times that under a CS-decomposition.

3. Consideration of performance degradation

The performance degradation factor, denoted by PDF.

4. Algorithm

Algorithm 1.Allocation

1. Apply the allocation algorithm link-disjoint free list (LFL) strategy.

2. If not allocated, find two free subcubes satisfying [C1] of Definition in k-1 dimension free lists.

3. If found, allocated these as k-subcube.

Algorithm 2.Deallocation

1. If this subcube is a LS,

2. Apply the deallocation algorithms in LFL to two k-1 subcubes of the LS.
3. else Apply the deallocation algorithms in LFL to the k-subcube.

5. Conclusion

An LS is not a contiguous cubcube as in the previous schemes, but has very similar structural properties to the contiguous subcubes.

Created by : Jain-Ming Chen

Date :June 10, 1997