高级检索

    在SIMD机器上实现的双调选择算法

    Bitonic Selection Algorithms on SIMD Machine

    • 摘要: (m,n)选择问题在多处理器系统上的并行求解是一个具有实际意义的研究课题。单指令多数据流(SIMD)机器是目前一种较为成熟和流行的并行处理系统。本文给出了在立方连接、洗牌交换连接和网孔连接三种典型SIMD机器模型上并行求解(m,n)选择问题的双调选择算法,它们所需的数据比较交换次数均为O(logn logm),数据移动次数分别为O(logn·logm)、O(log2n)和O(n)1/2

       

      Abstract: The parallel solution of the (m,n) selection problem on multiprocessorsystems is a significant topic for reseach. The SIMD machine being widely used now isa popular parallel-processing system. This paper describes the bitonic selection algorithmsto solve the (m,n) selection problem on three typical SIMD machine models includingcube connecting computer, shuffle-exchange connecting computer and mesh connectingcomputer. The number of data compare-exchange in each algorithm is O(logn logm); thenumber of data transfer in three algorithms are respectively O(logn logm), O(log2n)and O(n1/2).

       

    /

    返回文章
    返回