SIMD-EREW模型上的最优并行排序算法 |
| |
引用本文: | 殷新春,陈崚. SIMD-EREW模型上的最优并行排序算法[J]. 扬州大学学报(自然科学版), 2002, 5(1): 52-57 |
| |
作者姓名: | 殷新春 陈崚 |
| |
作者单位: | 扬州大学工学院计算机科学与工程系,江苏扬州,225009 |
| |
基金项目: | 国家自然科学基金资助项目(60074013); 国家高性能计算基金资助项目(99210); 江苏省教育厅自然科学基金资助项目(99KJB520003); 江苏省"333工程"资助项目(20018) |
| |
摘 要: | 给出两种在SIMD-EREW计算模型上的最优并行排序算法,为了避免存储访问冲突,算法采用了基于并行归并的并行排序方法。对于长度为n的序列,在n^ε个处理单元上,算法的排序时间为O(n^1-εlbn),成本为O(nlbn),已达到了最优,且算法是自适应的。
|
关 键 词: | SIMD-EREW计算模型 并行算法 最优并行排序算法 存储访问冲突 并行归并算法 排序时间 |
文章编号: | 1007824X(2002)01-0052-06 |
OPTIMAL SIMDEREW PARALLEL SORTING ALGORITHMS |
| |
Abstract: | |
| |
Keywords: | |
本文献已被 维普 万方数据 等数据库收录! |
|