| RAPWBN模型上的快速高效并行排序算法 |
| |
| 引用本文： | 陈宏建,陈崚,罗家奇.RAPWBN模型上的快速高效并行排序算法[J].计算机工程,2005,31(6):36-39. |
| |
| 作者姓名： | 陈宏建 陈崚 罗家奇 |
| |
| 作者单位： | 1. 扬州大学计算机系,扬州,225009
2. 扬州大学计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,210093 |
| |
| 基金项目： | 国家自然科学基金资助项目(60473012)，国家高性能计算基金资助项目(00219)，江苏省教育厅自然科学基金资助项目(99KJB520003)，扬州大学自然科学基金资助项目(KK0413161) |
| |
| 摘 要： | 在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的两种快速高效并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω＞logN字节,可以在O(1)时间完成排序.在具有N个处理器和N条行总线的RAPWBN模型上,最好情况下以O(logN)时间、最坏情况下以O(N)时间完成排序.
|
| 关 键 词： | RAPWBN模型 排序 并行算法 SIMD模型 二进制前缀 开关连接形式 |
| 文章编号： | 1000-3428(2005)06-0036-04 |
Fast and Efficient Parallel Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network |
| |
| CHEN Hongjian,CHEN Ling,LUO Jiaqi.Fast and Efficient Parallel Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network[J].Computer Engineering,2005,31(6):36-39. |
| |
| Authors: | CHEN Hongjian CHEN Ling LUO Jiaqi |
| |
| Affiliation: | CHEN Hongjian1,CHEN Ling1,2,LUO Jiaqi 1 |
| |
| Abstract: | |
| |
| Keywords: | RAPWBN model Sorting Parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
