三个并行排序算法的可扩充性分析

可扩充性分析是评价并行算法或并行系统性能的重要工作，特别是在大规模并行处理环境下更是如此。本文利用新近提出的扩张串行分量分析技术，研究了三个并行排序算法的可扩充性，以及这些算法在超立方体结构上的实现的可扩充性。给出了使三种算法都为可扩充的条件，解释了每个算法的适用范围。展示了算法的实质性质，计算了它们的扩张串行分量、扩张效率以及扩张加速比。本文的解析分析结果与其它文献中的实验结果一致。