高级检索

    多处理器上的分组选择算法

    A Partitioning Selection Algorithm on Multiprocessors

    • 摘要: 所谓(m,n)选择问题,系指从n个数中选取m个最小(或最大)者的问题。随着并行处理技术的发展,研究其并行解答变得越来越重要。这种并行求解在网络上曾作了相应的研究,但在多处理器环境下选择算法的研究却很少。本文给出一种基于分组原理,采用Valiant归倂和排序方法,在多处理器上实现的分组选择算法。这种算法可在n/2台处理器上,以小于O(logn log logm)2)的时间步完成(m,n)完全选择。

       

      Abstract: The so-celled(m,n)-selection problem is the problem of selecting the m smallest(or largest) elements from n given numbers(n>m). With the development of parallel computers, much attention has been paid to the design of efficient algorithm of(m, n) problem for these machines. The parallel selection algorithm has been succesful on networks, but is seldom studied on multiprocessing systems. This paper, based on partitioning approach, proposes a partitioning selection algorithm on multiprocessors using Valiant's merging and sorting schemes. By means of this algorithm,(m, n)-selection problem can be completed in parallel n/2 processors in time O(lognloglogm).

       

    /

    返回文章
    返回