更实际的并行算法的设计

THE DESIGN OF MORE REALISTIC PARALLEL ALGORITHMS

大规模并行计算机（ＭＰＣ）的出现和发展迫切要求有新的并行算法设计理论和技术来指导更实际的并行算法的设计。本文首先简单介绍了针对ＭＰＣ提出的ＬｏｇＰ和Ｂａｒｉｅｒ－ＬｏｇＰ并行计算模型，然后借助于Ｂａｒｒｉｅｒ－ＬｏｇＰ模型从通信平衡、数据分配和重叠通信与计算这三个方面讨论了更实际的并行算法设计的一般方法和技巧。

The emergence and development of massively parallel computers require new parallel algorithm design theories and techniques. In this paper, we first introduce the LogP and Barrier LogP parallel computation models. Then we discuss three principles of more realistic parallel algorithm design with the aid of Barrier LogP model. The principles proposed are balancing interprocessor communication, optimizing data placement and overlapping communication with computation. Several algorithms designed in the Barrier LogP are also given.