PRAM模型模拟RMESH模型的2种方案

给出用PRAM模拟RMESH的2种方案：用n个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(nlogn)，用n²个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(logn)，同时也给出了PRAM-CREW和PRAM-EREW模型模拟的时间复杂度。

Two Algorithms That Simulate RMESH by PRAM

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 sqrt(n)×sqrt(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 n². Simulations on PRAM-EREW and PRAM-CREW are also discussed.