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），我们实现了PRAM（并行随机存取模型），这是最理论的模型之一，并表明它可以通过使用可行的硬件数量来实现，其性能良好。我们还设计了一些处理器，以便可以有效地仿真数百个PRAM处理器。此外，我们展示了另一种方法来实现PRAM的多线程概念的基础上。对于（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 划分问题的线性算法”施普林格计算机科学讲座笔记。

Castanho, C.D, Chen, W., Wada, K.: "Polynomially fast parallel algorithms for some P-complete problems"IEICE Trans.on Fundamentals of Electronics,Communications and Computer Sciences. E84-A. 1244-1255 (2001)

Castanho, C.D, Chen, W., Wada, K.：“针对某些 P 完全问题的多项式快速并行算法”IEICE Trans.on 电子、通信和计算机科学基础。

Wada K. et al.: "An optimal fault-tolerant routing for triconnected planar graphs"Springer Lecture Notes in Computer Science. Vol. 1665. 191-201 (1999)

Wada K. 等人：“三联平面图的最佳容错路由”计算机科学中的施普林格讲义。

Bordim, J. L. et al.: "Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks"Springer Lecture Notes in Computer Science. Vol. 1741. 215-224 (1999)

Bordim, J. L. 等人：“Ad-hoc 无线电网络的节能初始化协议”施普林格计算机科学讲座笔记。

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 连接图的最佳容错路由”卷。