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

The Scalability Analysis of Three Parallel Sort Algorithms

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

In this paper we use the Scaled Serial Fraction(SSF) analysis to study the scalaility of three parallel sort algorithms and that of the algorithms on a hypercube architecture.The scalability is a very important metric for predicting the performance of a parallel algorithm of a parallel system if we consider a massively parallel system with thousands of processors. The condition is griven under which the three parallel sort algorithms are all scalable and explain the applicability range of each algorithm.We show that by scalability analysis one is able to exhibit the essential properties of parallel sort algorithms in a massively parallel processing environment.Finally the computed results of the scaled serial fraction,the scaled efficiency and the,staled speedup are given.