RAPWBN模型上的快速高效并行排序算法

• 作者: 罗家奇 陈宏建 陈崚
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: RAPWBN模型 排序 并行算法
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 基金项目论文
• 页码范围: 36-39
• 页数: 4页
• 分类号: TP37.0141.3
• 字数: 5430字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2005.06.014

摘要

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的两种快速高效并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω＞logN字节,可以在O(1)时间完成排序.在具有N个处理器和N条行总线的RAPWBN模型上,最好情况下以O(logN)时间、最坏情况下以O(N)时间完成排序.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈宏建	扬州大学计算机系	30	550	8.0	23.0
2	陈崚	扬州大学计算机系	150	1914	19.0	39.0
6	罗家奇	扬州大学计算机系	15	67	4.0	8.0