| 一种优化BITONIC算法:"并行-优化-串行"合并和分类向量算法 |
| |
| 引用本文： | 胡玥,高庆狮,刘宏岚.一种优化BITONIC算法:"并行-优化-串行"合并和分类向量算法[J].计算机研究与发展,2002,39(10):1307-1316. |
| |
| 作者姓名： | 胡玥 高庆狮 刘宏岚 |
| |
| 作者单位： | 1. 北京科技大学智能语言与计算机科学研究所,北京,100083;中国科学院计算技术研究所,北京,100080
2. 北京科技大学智能语言与计算机科学研究所,北京,100083 |
| |
| 基金项目： | 本课题得到国家自然科学基金资助(60083008) |
| |
| 摘 要： | 串行算法并行化是发挥各种巨型机的效率的关键技术之一。“并行－优化－串行”归并向量算法（OSVM），是一种串行算法并行化的优化方法，它用O（N／p)时间把总长为N的两个有序序列归并或把总长为N的一个Bitonic序列排序。“并行－优化－串行”排序向量算法（POSVS）用O（NlogN)/p）时间在实际SIMD机上把N个数排序，这些是第1个满足以下两个条件的向量Optimal算法（加速比＝O（p))，（1）它能在实际SIMD计算机上实现，处理机的台数p的范围很宽1≤N^1-ε，这里，ε是任意的小的正数。（2）它统一了3种不同类的合并算法：Batcher的Bitonic算法（最快但效率随参数变大而向于0），优化(Optimal)算法（效率为常数的算法）和最佳的串行算法。而且综合了3个算法的优点，“并行－优化－串行”（POS）方法是一个通用方法，它还可以应用到其它类型问题上。
|
| 关 键 词： | 优化 BITONIC算法 “并行－优化－串行”归并向量算法 分类向量算法 串行算法并行化 并行算法 并行归并 并行排序 Bitonic排序 |
A PARALLEL-OPTIMAL-SEQUENTIAL VECTOR ALGORITHM FOR MERGING AND SORTING |
| |
| Abstract: | |
| |
| Keywords: | sequential algorithm deserialize parallel algorithm parallel merging parallel sorting Bitonic sorting |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
