期刊文献+

PRAM模型模拟RMESH模型的2种方案 被引量:1

Two Algorithms That Simulate RMESH by PRAM
下载PDF
导出
摘要 给出用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 )
关键词 PRAM RMESH 模拟 PRAM RMESH simulation
  • 相关文献

参考文献9

  • 1Miller R, Prasanna-Kumar V K, Reisis D, et al. Meshes with Reconfigurable Buses. MIT Conference on Advanced Research in VLSI, Cambridge:MIT Press, 1988. 163-178.
  • 2Czumaj A, Stamann V. Simulating Shared Memory in Real Time: on the Computing Power of Reconfigurable Architectures. Information and Computation,1997,137(2):103-120.
  • 3Matias Y, Schuster A. Fast, Efficient Mutual and Self Simulations for Shared Memory and Reconfigurable Meshes. In: Proceedings of 7th IEEE Symposium on Parallel and Distributed Processing. San Antonio,Texas:1995, 238-246.
  • 4Forture S, Wyllie J. Parallelism in Random Access Machine. In: Proceedings of 10^th Annual ACM Symposium On the Theory of Computing, San Diego:1978,114-118.
  • 5Eckstein D M. Simultaneous Memory Access. Tech Rep:TR-79-6, Department of Computer Science, Iowa State University, Iowa City, 1979.
  • 6Kucera L. Parallel Computation and Conflicts in Memory Access. Information. Processing Letters, 1982, 14(2):93-96.
  • 7Vishkin U. Implementation of Simultaneous Memory Address Access in Models that Forbit It. Journal of Algorithms,1983, 4(1):45-50.
  • 8Fich F E, Ragde P,Wegderson A. Simulations among Concurrent-Write PRAMs. Algorithmica, 1988, 3(1):43-51.
  • 9Chlebus B S, Dike K, Hagerup T, et al. Efficient Simulations between Concurrent-Read Concurrent-Write PRAM Models. In: Proc of 13th Symposium on Mathematical Foundations of Computer Science. Carlsbad, Czechoslovakia: 1988,231-239.

同被引文献7

  • 1Kruskal J B. On the Shortest Subtree of a Graph and the Traveling Salesman Problem. Proc Amer Math Soc, 1956,7 ( 1 ) : 48-50.
  • 2Prim R C. Shortest Connection Networks and Some Generalizations, Bell System Tech J, 1957, 36 (6) : 1389-1401.
  • 3Tsin Y H, Chin F Y. Efficient Parallel Algorithms for a Class of Graph Theoretic Problems, SIAM J Comput, 1984,13(3) :580-590.
  • 4Kwan S C, Ruzzo W L. Adaptive Parallel Algorithms for Finding Minimum Spanning Trees. Proc Intern Conf on Parallel Computing, 1984, 439-443.
  • 5Nath D, Maheshwari S N. Parallel Algorithms for the Connected Components and Minimal Tree Problems. Inform Proc Lett, 1982, 14(1):7-11.
  • 6Miller R, Prasanna-Kumar V K, Reisis D, et al. Meshes with Reconfigurable Buses, MIT Conference on Advanced Research in VLSI, 1988, 163-178.
  • 7Wan Y Y, Xu Y L, Gu X D, et al. Efficient Minimum Spanning Tree Algorithms for the Reconfigurable Meshes.Journal of Computer Science and Technology, 2000, 15 (2) :116-125.

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部