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

串行算法并行化是发挥各种巨型机的效率的关键技术之一 .“并行 -优化 -串行”归并向量算法 ( 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)方法是一个通用方法 。