PRODUCTS OF NETWORKS WITH LOGARITHMIC DIAMETER AND FIXED DEGREE

This paper first analyzes some general properties of product networks 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 r-dimensional product of shuffle exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn network can be embedded in 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.