On the power of the mesh with hybrid buses

The main contribution of this work is to fathom the power and flexibility of the Mesh with Hybrid Buses via simulation. We propose two algorithms that perform an O(1) time stepwise simulation of an N-processor dynamic Priority CRCW-PRAM endowed with M memory cells. Our first algorithm uses a Mesh with Hybrid Buses of size max{N, MN^ε/2}×MN^ε/2 for some fixed constant ε, 0<ε⩽1. Our second algorithm uses a Mesh with Hybrid Buses of size N×max{N,M}. The first algorithm is suited for small values of M, while the second is best suited for larger M