Two Algorithms That Simulate RMESH by PRAM
Peng Chen · Acta Scicentiarum Naturalum Universitis Pekinesis · 2005
Both PRAM and RMESH are important parallel computing models. This paper gives two algorithms that simulate RMESH by PRAM. The first algorithm is to use PRAM-CRCW with n processors to simulate RMESH with n×n processors, whose time complexity is O(nlogn). The algorithm has three steps respectively used to simulate the following three basic sub-steps of a unit computing time step of RMESH: bus reconfiguration, bus write and bus read. The most core part is to simulate bus reconfiguration on PRAM, which is implemented by an algorithm based on bus combination technique. The second one improves the efficiency, which is O(logn), but with the number of processors increased to n2. Simulations on PRAM-EREW and PRAM-CREW are also discussed.