much larger than a reconfigured maximum complete subcube because the former always involves a copy of the latter plus some smaller subsystem(s). Simple and deadlock-free algorithms for routing and broadcasting messages in an incomplete hypercube have been developed [4]. A recent study on the incomplete hypercube system suggests that no congestion point exists in such a system [8]. In this work, three applications are considered to measure the degree of benefit with maximum reconfiguration. They are Gaussian elimination, mixed sort (a mixture of the shell sort and an odd-even transposition sort), and FFT. For Gaussian elimination and mixed sort, our implementations follow a ring topology on both complete and incomplete systems, thus employing the same mapping scheme on an incomplete system as on a complete one. For FFT, however, some efforts are required to adapt it to the incomplete topology, leading to a slightly different mapping scheme on an incomplete system than on a complete one. Our experimental results show that for Gaussian elimination, an incomplete system of size 12 may outperform its complete counterpart (i.e., a complete system of size 8) by as much as 49%. This is expected as Gaussian elimination is computation-intensive. For mixed sort, an incomplete system of size 12 may outperform its complete counterpart by 30%. At the other extreme, FFT is communication-intensive following the butterfly communication pattern, and an incomplete system then achieves a less impressive performance gain.
Note that if a system attempts to maintain all the faultfree nodes without assuring the incomplete topology, it is impossible to have simple, deterministic routing and broadcasting algorithms. In fact, unlike an incomplete hypercube, this often requires complicated node-to-node routing and broadcasting, which do not guarantee deadlock-freeness. Moreover, traffic density over a link is not bounded by a small constant in this situation, possibly causing congestion points to occur. It is thus more advantageous to reconfigure a faulty hypercube into a maximum incomplete subcube than to maintain all the healthy nodes without reconfiguration.
2. BACKGROUND AND DEFINITIONS
An n-dimensional complete hypercube, H n , comprises 2 n nodes, each with n links connected directly to n other nodes, called neighbors. In H n , a node is labeled by an n-