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

Two Algorithms That Simulate RMESH by PRAM

作　　者：陈鹏[1] 张立昂[1] 

机构地区：[1]北京大学信息科学技术学院,北京100871

出　　处：《北京大学学报（自然科学版）》2005年第3期465-475,共11页Acta Scientiarum Naturalium Universitatis Pekinensis

基　　金：国家自然科学基金重点资助项目 (6 990 30 2 0 )

摘　　要：给出用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.

关 键 词：PRAM RMESH 模拟 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]