Products of networks with logarithmic diameter and fixed degree

Analyzes some general properties of product networks that are pertinent to parallel architectures and then focuses on three case studies. These are products of complete binary trees, shuffle-exchange and de Bruijn networks. It is shown that all of these are powerful architectures for parallel computation, as evidenced by their ability to efficiently emulate numerous other architectures. In particular, r-dimensional grids and r-dimensional meshes of trees can be embedded efficiently in products of these graphs, i.e. either as a subgraph or with small constant dilation and congestion. In addition, the shuffle-exchange network can be embedded in an r-dimensional product of shuffle-exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn network can be embedded in an r-dimensional product of de Bruijn networks with dilation cost r and congestion cost 4. Moreover, it is well known that shuffle-exchange and de Bruijn graphs can emulate the hypercube with a small constant slowdown for “normal” algorithms. This means that their product versions can also emulate these hypercube algorithms with constant slowdown. Conclusions include a discussion of many open research areas