On the scalability of PSRS algorithm

In this paper, using the metric of iso-efficiency function 1]. we analyze the scalability of PSRS (Parallel Sorting by Regular Sample) algorithm 2] on two popular architectures (Mesh and Hypercube). The isoefficiency function of PSRS on 2-dimensional mesh withp processors reaches the lower bound $\Omega \left( {\sqrt p \cdot 2^{c\sqrt F } } \right)$ for that of sorting algorithms on this architecture. In this sense, we say, the scalability of PSRS is optimal on 2-dimensional mesh. The iso-efficiency function of PSRS on hypercube is equal to that of PSRS on 2-dimensional mesh. After changing the data exchanging scheme of PSRS, we get a new iso-efficiency functionO(log² p·p ^Ciogp), which is better than that of PSRS on 2-dimensional mesh So we say that hypercube is more suitable for PSRS than 2-dimensional mesh.