Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

Two Algorithms That Simulate RMESH by PRAM

CHEN Peng, ZHANG Li'ang   

  1. School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871
  • Received:2004-02-12 Online:2005-05-20 Published:2005-05-20

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

陈鹏,张立昂   

  1. 北京大学信息科学技术学院,北京,100871;E-mail: zliang@pku.edu.cn

Abstract: 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 n2. Simulations on PRAM-EREW and PRAM-CREW are also discussed.

Key words: PRAM, RMESH, simulation

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

关键词: PRAM, RMESH, 模拟

CLC Number: