×

On the scalability of PSRS algorithm. (English) Zbl 0919.68020

Summary: Using the metric of a iso-efficiency function, we analyze the scalability of PSRS (Parallel Sorting by Regular Sample) algorithm on two popular architectures (Mesh and Hypercube). The iso-efficiency function of PSRS on two-dimensional mesh with \(p\) processors reaches the lower bound \(\Omega(\sqrt p\cdot 2^{C\sqrt p})\) for that of sorting algorithms on this architecture. In this sense, we say the scalability of PSRS is optimal on two-dimensional mesh. The iso-efficiency function of PSRS on hypercube is equal to that of PSRS on two-dimensional mesh. After changing the data exchanging scheme of PSRS, we get a new iso-efficiency function \(O(\log^2p\cdot p^{C\log p})\),which is better than that of PSRS on two-dimensional mesh. So we say that hypercube is more suitable for PSRS than two-dimensional mesh.

MSC:

68P10 Searching and sorting
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Vipin Kumar and V. Nageshwara Rao. ”Parallel depth-first search, part II: Analysis,” International Journal of Parallel Programming 16(6): 501–519, 1987. · Zbl 0665.68049 · doi:10.1007/BF01389001
[2] Hanmao Shi and Janathan Schaeffer. ”Parallel Sorting by Regular Sampling” Parallel and Distributed Computing, 14(4), P361–372, 1992. · Zbl 0763.68030 · doi:10.1016/0743-7315(92)90075-X
[3] Nai-jie Gu, Guo-liang Chen. ”The scalability of PSRS algorithm”, Technical report Dept. of Computer Science, USTC, Hefei, Anhui, P. R. China, 1994. · Zbl 0919.68020
[4] V. Singh, V. Kumar, G. Agha and C. Tomlinson, ”Scalability of parallel sorting on mesh multicomputers”, Technical Report Computer Science Department, University of Minnesota. · Zbl 0761.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.