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

点击翻译按钮获取中文摘要

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.