The Shuffled Mesh: a flexible and efficient model for parallel computing

In this work an efficient model for parallel computing, called Shuffled Mes h (SM), is introduced. This bounded degree model has the mesh as subgraph a nd it is based on the union of mesh and shuffle-exchange topologies. It is shown that an N-processor SM combines the features of mesh, shuffle-exchang e, hypercubic networks, mesh of trees and hypercube, and is able to support all the algorithms designed for such topologies with constant or logarithm ic time performance degradation. Finally, it is proved that the VLSI layout of a SM is the same as of a shuffle exchange of the same size.