A bitonic selection algorithm on multiprocessor system

Guoliang Chen, Hong Shen

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

The so-called (m, n) selection problem is defined as the selection of the m smallest (or largest) numbers from n given numbers (n>m). Solving this problem in parallel mode has been successful on the networks, but it is seldom studied on the multiprocessor systems. This paper first, based on Batcher's principle of bitonic merging, proposes the bitonic selection network. Then it repeals the varying rule of the pivots in all successive ranks of the network through our observation to the data transfer property in the network. Finally, according to this rule, the parallel selection algorithm with running time O (log nlog m)1) on n processors is presented.

原文English
頁(從 - 到)315-322
頁數8
期刊Journal of Computer Science and Technology
4
發行號4
DOIs
出版狀態Published - 10月 1989
對外發佈

指紋

深入研究「A bitonic selection algorithm on multiprocessor system」主題。共同形成了獨特的指紋。

引用此