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

摘要

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