Abstract
The directional hypercube (Dcube) which is a cost-effective variation of the traditional binary hypercube is introduced and analyzed in this paper. It employs directional (simple duplex) links only. The Dcube is defined and its key properties are derived including diameter, bandwidth, and connectivity. The diameter is at most 2 greater than that for a hypercube of the same size; the bandwidth is 1 2 that of the hypercube; and the connectivity is optimal. The Dcube is shown to emulate the binary hypercube with at worst a factor of 4 degradation in time performance under any message distribution. A simple routing algorithm is demonstrated for the Dcube which requires only local information to route messages between nodes. Then, the concept of virtual channels has been added to the routing algorithm to make it deadlock-free.
| Original language | English |
|---|---|
| Pages (from-to) | 277-286 |
| Number of pages | 10 |
| Journal | Information Processing Letters |
| Volume | 53 |
| Issue number | 5 |
| Publication status | Published - 10 Mar 1995 |
Keywords
- Connectivity
- Diameter
- Emulation
- Fault tolerance
- Node-disjoint path
- Parallel processing
- Routing