Design Paradigm for Parallel Algorithms and Realizability of Theoretical Parallel Computer Models

并行算法设计范式及理论并行计算机模型的可实现性

• 批准号: 10205209
• 负责人: WADA Koichi
• 金额: $ 6.78万
• 依托单位: Nagoya Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205209/
• 关键词: PRAM; reconfigurable mesh; work-preserving algorithms; convex hull; fault-tolerance; radio networks; distributed cooperative algorithms; multi-agents; 耐故障性ルーティング; 光通信網; 並列アルゴリズム; VHDL; エンベロープ

The purpose of the research is mainly the followings : (1) We close a gap between theory and practice for parallel computation to implement theoretical parallel computer models. (2) We establish new design paradigm for parallel/distributed algorithms. For (1), we implement PRAM (Parallel Random Access Model), which is one of the most theoretical models and show that it can be realizable by using feasible amount of hardware and its performance is good. We also design some processor such that several hundreds of PRAM processors can be emulated efficiently. Furthermore, we show another method to implement PRAM based on the multithread concept. For (2), we examine new design paradigm to develop parallel/distributed algorithms for geometrical and graph theoretical problems. As for parallel algorithm paradigm, we propose a new method called multi-divided and conquer and we show this method can be applicable for several geometrical problems. As for distributed algorithm paradigm, we show algorithms for several problems related to radio network problems and fault-tolerant network problems. We also some distributed cooperative algorithms by using multi-agents as cooperative design paradigm.

研究的目的主要是以下内容：（1）我们在平行计算实现理论并行计算机模型的理论和实践之间缩小了差距。 （2）我们为并行/分布式算法建立了新的设计范例。对于（1），我们实现了婴儿车（并行随机访问模型），这是最理论的模型之一，并表明它可以通过使用可行数量的硬件及其性能来实现。我们还设计了一些处理器，以便可以有效地模仿数百个婴儿车处理器。此外，我们展示了基于多线程概念实现婴儿车的另一种方法。对于（2），我们检查了新的设计范式，以开发出用于几何和图理论问题的平行/分布式算法。至于并行算法范式，我们提出了一种称为多细分和征服的新方法，我们表明该方法可用于几种几何问题。至于分布式算法范式，我们显示了与无线电网络问题和容忍缺陷网络问题有关的几个问题的算法。我们还通过使用多代理作为合作设计范式来分布分布的合作算法。

项目成果

Wada, K., Chen, W.: "Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases"Springer Lecture Notes in Computer Science. 1517. 324-336 (1998)

Wada, K., Chen, W.：“不指定基数的平面图 k 划分问题的线性算法”施普林格计算机科学讲座笔记。

Chen, D. Z., Chen, W., Wada, K., Kawaguchi K.: "Parallel algorithms for partitioning sorted sets and related problems"Algorithmica. 28. 217-241 (2000)

Chen, D. Z.、Chen, W.、Wada, K.、Kawaguchi K.：“划分排序集的并行算法及相关问题”Algorithmica。

K.Wada et al.: "Efficient algorithms for a mixed k-partition problem of graphs without specifying bases" Theoretical Computer Science. 201,1-2. 233-248 (1998)

K.Wada 等人：“无需指定基数的图混合 k 分区问题的高效算法”理论计算机科学。

Wada, K., Chen, W.: "Optimal Fault-Tolerant Routings for k-connected Graphs with Smaller Routing Tables"Vol. 1928. 302-313 (2000)

Wada, K., Chen, W.：“具有较小路由表的 k 连接图的最佳容错路由”卷。

Chen,W.,Wada,K.: "(13) Designing Efficient Parallel Algorithms with Multi-Level Divide-and-Conquer"IEICE Trans.on Fundamentals of Electronics, Communications and Computer Sciences. (To appear). (2001)

Chen,W.,Wada,K.：“（13）利用多级分而治之设计高效并行算法”IEICE Trans.on 电子、通信和计算机科学基础。