摘要
给出用PRAM模拟RMESH的2种方案:用n个处理器的PRAM CRCW模型模拟n×n个处理器的RMESH模型的时间复杂度为O(nlogn) ,用n2 个处理器的PRAM CRCW模型模拟n×n个处理器的RMESH模型的时间复杂度为O(logn) ,同时也给出了PRAM CREW和PRAM EREW模型模拟的时间复杂度。
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 root n × root 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.
出处
《北京大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2005年第3期465-475,共11页
Acta Scientiarum Naturalium Universitatis Pekinensis
基金
国家自然科学基金重点资助项目 (6 990 30 2 0 )