高级检索

    一种优化BITONIC算法:“并行-优化-串行”合并和分类向量算法

    A PARALLEL-OPTIMAL-SEQUENTIAL VECTOR ALGORITHM FOR MERGING AND SORTING

    • 摘要: 串行算法并行化是发挥各种巨型机的效率的关键技术之一 .“并行 -优化 -串行”归并向量算法 ( POSVM) ,是一种串行算法并行化的优化方法 .它用 O( N / p )时间把总长为 N的两个有序序列归并或把总长为 N的一个Bitonic序列排序 .“并行 -优化 -串行”排序向量算法 ( POSVS)用 O( ( N log N) / p)时间在实际 SIMD机上把 N个数排序 .这些是第 1个满足以下两个条件的向量 Optimal算法 (加速比 =O( p ) ) .1它能在实际 SIMD计算机上实现 .处理机的台数 p的范围很宽 1≤ p≤ N 1-ε,这里 ,ε是任意的小的正数 .2它统一了 3种不同类的合并算法 :Batcher的 Bitonic算法 (最快但效率随参数变大而趋向于 0 )、优化 ( Optimal)算法 (效率为常数的算法 )和最佳的串行算法 .而且也综合了 3个算法的优点 .“并行 -优化 -串行”( POS)方法是一个通用方法 ,它还可以应用到其它类型问题上

       

      Abstract: In this paper, a parallel-optimal-sequential (POS) approach is proposed, which transforms a computation into a series subcomputation. Each subcomputation can be computed in a parallel-optimal-sequential (POS) fashion,i.e. , there arep processors, and on each of them a subcomputation is computed on an optimal sequential algorithm simultaneously. Based on this approach, a parallel-optimal-sequential vector merging algorithm (POSVM) is designed, which merges 2 sorted sequences (or sorts a Bitonic sequence) of totalN number inO(N/p) time, and a POS vector sorting algorithm (POSVS) sortsN arbitrary numbers inO((NlogN)/p) time on a practical general purpose SIMD machine. These are first vector optimal algorithms (speedup=O(p)), which satisfy two conditions as follows: ① which can be implemented in a practical SIMD machine, such as vector pipeline machine with interleaved memory modules or multiprocessors system with a multistage multi-dimensional interconnect network, in a wide range ofp, 1≤p≤N 1-ε, whereε is an arbitrary small positive number, and ②, which unify the three very different kinds of merging and sorting algorithms: Batcher’s Bitonic algorithm (the fast algorithm but not optimal), the optimal parallel algorithm, and the optimal sequential algorithm. The POS approach is a general approach which can also be used in other problems.

       

    /

    返回文章
    返回