高级检索

    双调选择网络及其在多处理器上的双调选择算法

    Bitonic Selection Network and Bitonic Selection Algorithm on Multiprocessors

    • 摘要: 所谓(m,n)选择问题系数指从n个数中选择m个最小(或最大)者的问题.此问题的并行求解目前在网络上已得以实现,而在多处理器系统上却很少被人研究.本文首先基于Batcher的双调归併原理,提出一种比较器数目和延迟级数分别为O(nlog2m)和O(logn·logm)2)的双调选择网络;然后通过观察该网络中数据移动之特点来找出双调选择网络中相继各列枢点之变化规律;最后由此规律给出了一种在n个处理器上可在O(logn·logm)时间步内完成的并行双调选择算法.

       

      Abstract: The so-called(m,n)selection problem is the problem of selecting the msmallest(or largest)numbers from n numbers(n≥m).Parallel solution of this problem has been implemented successfully 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 in which the number of comparators is O(nlog2m)and the delay time is O(logn logm);then,we find the varing rule of the pivots in all successive ranks of the network throughobserving the data transfer property in the network.According to this rule,the parallel selection algorithm executed in time O(logn logm)on n processors is given.

       

    /

    返回文章
    返回