带有宽总线网络可重构计算模型上的快速并行排序算法

摘要：

该文介绍了带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作,提出了一种快速并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,可以在O(1)时间完成排序.该算法的成本达到了最优.

关键词：RAPWBN模型、排序、并行算法

所属期刊栏目：40

分类号：TP37;O141.3(计算技术、计算机技术)

资助基金：国家自然科学基金60074013;国家高性能计算基金00210;江苏省教育厅自然科学基金

在线出版日期：2004-08-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：48-50,90