| 带有宽总线网络可重构计算模型上的快速并行排序算法 |
| |
| 引用本文： | 陈宏建,陈崚,秦玲,徐晓华,屠莉.带有宽总线网络可重构计算模型上的快速并行排序算法[J].计算机工程与应用,2004,40(19):48-50. |
| |
| 作者姓名： | 陈宏建 陈崚 秦玲 徐晓华 屠莉 |
| |
| 作者单位： | 1. 扬州大学信息工程学院计算机系,扬州,225009
2. 扬州大学信息工程学院计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,210093 |
| |
| 基金项目： | 国家自然科学基金(批准号:60074013)，国家高性能计算基金(批准号:00210)，江苏省教育厅自然科学基金，南京大学软件新技术国家重点实验室开放基金的资助 |
| |
| 摘 要： | 该文介绍了带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作,提出了一种快速并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,可以在O(1)时间完成排序。该算法的成本达到了最优。
|
| 关 键 词： | RAPWBN模型 排序 并行算法 |
| 文章编号： | 1002-8331-(2004)19-0048-03 |
| 修稿时间： | 2004年1月1日 |
A Fast Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network |
| |
| Chen Hongjian Chen Ling , Qin Ling Xu Xiaohua Tu Li.A Fast Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network[J].Computer Engineering and Applications,2004,40(19):48-50. |
| |
| Authors: | Chen Hongjian Chen Ling Qin Ling Xu Xiaohua Tu Li |
| |
| Affiliation: | Chen Hongjian 1 Chen Ling 1,2 Qin Ling 1 Xu Xiaohua 1 Tu Li 11 |
| |
| Abstract: | This paper introduces the basic structure and the bina ry prefix sum operation of the reconfigurable comput-ational model with wide bus network(RAPWBN).A fast parallel sorting algorithm on RAPWBN model is presente d.The algorithm can sort N elements in O(1)time on a RAPWBN model of N 2 processors and N-row bus with bandwidthω>logN.The cost of the algorithm is optimal. |
| |
| Keywords: | RAPWBN model sorting parallel algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
