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

北京大学学报（自然科学版）

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

陈鹏,张立昂

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

收稿日期:2004-02-12 出版日期:2005-05-20 发布日期:2005-05-20

Two Algorithms That Simulate RMESH by PRAM

CHEN Peng, ZHANG Li'ang

School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871

Received:2004-02-12 Online:2005-05-20 Published:2005-05-20

摘要/Abstract

摘要： 给出用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模型模拟的时间复杂度。

关键词: PRAM, RMESH, 模拟

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

Key words: PRAM, RMESH, simulation

中图分类号:

TP302

陈鹏,张立昂. PRAM模型模拟RMESH模型的2种方案[J]. 北京大学学报（自然科学版）.

CHEN Peng,ZHANG Li'ang. Two Algorithms That Simulate RMESH by PRAM[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2005/V41/I3/465

[1]	李青, 余钊圣, 刘朋欣, 李婷婷, 陈坚强, 袁先旭. 高焓流动中的可压缩颗粒两相流并行求解器: 数值方法及其验证[J]. 北京大学学报自然科学版, 2024, 60(1): 89-108.
[2]	唐菱珮, 陈效逑, 钱思蔚, 莫志鸿. 北京植物园主要观赏植物春花期和秋叶期的过程模拟[J]. 北京大学学报自然科学版, 2023, 59(4): 649-658.
[3]	苏晗, 邹锐, 梁中耀, 叶瑞, 王志芸, 刘永. 基于数值模拟的负荷削减–水体水质响应的非线性强度指标[J]. 北京大学学报自然科学版, 2023, 59(4): 695-703.
[4]	叶裕佳, 秦华鹏, 毛俊祺. 城市立交桥洞内涝过程的精细化模拟研究[J]. 北京大学学报自然科学版, 2023, 59(1): 105-114.
[5]	王迎, 李江海, 马昌明, 宋珏琛. 基于离散元法的龙门山构造带隆升变形主控因素研究[J]. 北京大学学报自然科学版, 2022, 58(5): 850-860.
[6]	刘晓旭, 党卓, 张南. 地幔柱的发生机制研究——以Ferrar为例[J]. 北京大学学报自然科学版, 2022, 58(2): 234-240.
[7]	程鹏, 李江海, 刘志强. 下刚果盆地中段挤压带盐底辟构造形成演化分析——基于物理及离散元模拟[J]. 北京大学学报自然科学版, 2021, 57(3): 470-480.
[8]	孙煜航, 程舒鹏, 张祺, 杜鹏举, 李振山, 赵志杰. 黄河下游花园口至艾山河段滩区洪水漫滩风险度评估研究[J]. 北京大学学报自然科学版, 2021, 57(3): 575-586.
[9]	邓迪, 肖万博, 王彦宾. 全火星模型中震波传播特征的数值模拟研究[J]. 北京大学学报自然科学版, 2020, 56(4): 629-637.
[10]	姚永芳, 孙振旭, 刘文, 杨国伟. 高速列车受电弓气动噪声特性分析[J]. 北京大学学报自然科学版, 2020, 56(3): 385-398.
[11]	郑宇凡, 蔡旭晖, 康凌, 张宏升, 宋宇. 大气扩散应急预报的风场不确定性影响研究[J]. 北京大学学报自然科学版, 2019, 55(5): 878-886.
[12]	张鑫, 张洪亮, 周雷, 何涛, 梁前勇, 董一飞, 何川. 基于测斜仪的天然气水合物开采海底变形监测[J]. 北京大学学报自然科学版, 2019, 55(4): 635-642.
[13]	王殿举, 李江海, 程鹏, 刘志强, 于法浩. 构造倾斜角度对盐构造形成的控制模式: 以下刚果盆地为例[J]. 北京大学学报自然科学版, 2019, 55(2): 277-288.
[14]	毋宇斌, 刘永岗, 易朝路, 刘鹏. 末次冰盛期青藏高原冰川变化对亚洲气候的影响[J]. 北京大学学报自然科学版, 2019, 55(1): 159-170.
[15]	邢英华, 程翔, 秦华鹏, 赵志杰. 基于HSPF的绿色基础设施水文效应模拟——以大浪河流域为例[J]. 北京大学学报自然科学版, 2018, 54(5): 1053-1059.