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

本研究的主要目的是：(1)缩小并行计算理论与实践之间的差距，实现理论并行计算机模型。(2)建立了并行/分布式算法的新设计范式。对于(1)，我们实现了PRAM (Parallel Random Access Model)，这是最具理论性的模型之一，并证明了它可以在可行的硬件数量下实现，并且性能良好。我们还设计了一些处理器，可以有效地模拟数百个PRAM处理器。此外，我们还展示了基于多线程概念的另一种实现PRAM的方法。对于(2)，我们研究了新的设计范式，以开发用于几何和图形理论问题的并行/分布式算法。对于并行算法范式，我们提出了一种新的多分征服方法，并证明了该方法可以适用于若干几何问题。对于分布式算法范例，我们给出了与无线网络问题和容错网络问题相关的几个问题的算法。采用多智能体作为协同设计范式，提出了分布式协同算法。

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.