Interprocessor Communication and the Hypercube Graph

mes the bottleneck limiting the scalability of parallel algorithms. Thus, choosing the correct communication subsubstrate for one's parallel computer is of paramount importance to its performance. Because of the versatility of an interconnection graph known as the hypercube, it looked very attractive to machine designers in the recent past, and was used in the CM-2, Cosmic Cube, and N-Cube (one is located here at MIT, in the Earth Resources Laboratory). 5a-1 010 000 001 011 100 110 111 101 Figure 1: The Hypercube for d = 3 A Hypercube graph consists of: 1. d Dimensions 2. 2 d Vertices 3. (b 0 :::b d\Gamma1 ) and (b 0 0 :::b 0 d\Gamma1 ) are connected by an edge if and only if they differ in exactly one bit. There are d2 d\Gamma1<F62.1