Balanced generalized hypercubes: Complexity and cost/performance analysis

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 maximal if the w nodes along each dimension form a complete directed graph. A BGHC is said to be minimal if the w nodes along each dimension form a unidirection al ring. Lower bound complexities are derived for three intensive communica tion patterns assuming the balanced generalized hypercube (BGHC) topology. A maximal N node BGHC with a node degree equal to alpha log(2)N, where alph a greater than or equal to 2, can process certain intensive communication p atterns alpha(alpha - 1) times faster than an N node binary hypercube (whic h has a node degree equal to log(2) N) On the other hand, a minimal N node BGHC with a node degree equal to 1/beta log(2) N, where beta greater than o r equal to 2, is 2(beta) times slower at processing certain intensive commu nication patterns than an N node binary hypercube. For certain communicatio n patterns, increasing one unit cost gains a normalized speedup to the bina ry hypercube by w log, vr times for the maximal BGHC. For the minimal BGHC, reducing one unit cost gains w-1/log(2)w times speedup normalized to the b inary hypercube.