caa a22 4500 477074693 CHVBK 20180405111436.0 cr unu---uuuuu 170330e19961201xx s 000 0 eng 10.1007/BF02900868 doi (NATIONALLICENCE)springer-10.1007/BF02900868 On the scalability of PSRS algorithm [Elektronische Daten] [Nai-jie Gu, Guo-Iiang Chen] 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(log2 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. Springer, 1996 Sorting nationallicence Parallel Algorithm nationallicence Scalability nationallicence Communication nationallicence Gu Nai-jie Department of Computer Science, University of Science and Technology of China, 230026, Hefei, Anhui, P.R.C. aut Chen Guo-Iiang Department of Computer Science, University of Science and Technology of China, 230026, Hefei, Anhui, P.R.C. aut Wuhan University Journal of Natural Sciences Wuhan University 1/3-4(1996-12-01), 450-454 1007-1202 1:3-4<450 1996 1 11859 https://doi.org/10.1007/BF02900868 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02900868 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gu Nai-jie Department of Computer Science, University of Science and Technology of China, 230026, Hefei, Anhui, P.R.C aut NATIONALLICENCE 700 1- Chen Guo-Iiang Department of Computer Science, University of Science and Technology of China, 230026, Hefei, Anhui, P.R.C aut NATIONALLICENCE 773 0- Wuhan University Journal of Natural Sciences Wuhan University 1/3-4(1996-12-01), 450-454 1007-1202 1:3-4<450 1996 1 11859 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer