论并行算法的分类

§1.引言利用并行计算系统求解数值计算问题或非数值计算问题,需根据系统的类型设计并行算法。自然,并行算法设计的主要基础是求解问题所涉及的学科领域中的原理和方法,或直接揭示某些已有方法中潜在的并行性,或推广某些原理发展显含并行性的新方法。但是,要建立可行(能在一个并行计算系统中实现)和有效(能充分发挥系统性能使并行度与

ON THE CLASSIFICATION OF PARALLEL ALGORITHMS

First, the solution and algorithm, as well as decompositions of task level and process of solution, are described, and then a structural model of parallel algorithms is developed. Ba-sed on this, all the parallel algorithms are classified into three types: SIMD algorithms, syn-chronous MIMD algorithms and asynchronous algorithms. Furthermore, the characterization, designing and applicability of each type of algorithms are clarified respectively. Some typical examples are given.