Complexity of intensive communications on balanced generalized hypercubes

Lower bound complexities are derived for three intensive communication patterns assuming a balanced generalized hypercube (BGHC) topology. The BGHC is a generalized hypercube that has exactly w nodes along each of the d dimensions for a total of w^d nodes. A BGHC is said to be dense if the w nodes along each dimension form a complete directed graph. A BGHC is said to be sparse if the w nodes along each dimension form a unidirectional ring. It is shown that a dense N node BGHC with a node degree equal to Klog₂N, where K ⩾2, can process certain intensive communication patterns K (K-1) times faster than an N node binary hypercube (which has a node degree equal to log₂N). Furthermore, a sparse N node BGHC with a node degree equal to ¹/_Llog₂N, where L⩾2, is 2^L times slower at processing certain intensive communication patterns than an N node binary hypercube