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

Fast and Efficient Parallel Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network

作　　者：陈宏建[1] 陈崚[1,2] 罗家奇[1] 

机构地区：[1]扬州大学计算机系 [2]南京大学软件新技术国家重点实验室,南京210093

出　　处：《计算机工程》2005年第6期36-39,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60473012);国家高性能计算基金资助项目(00219);江苏省教育厅自然科学基金资助项目(99KJB520003);扬州大学自然科学基金资助项目(KK0413161)

摘　　要：在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了 RAPWBN 模型上的抽取压缩操作算法,并由此得到了 RAPWBN 模型上的两种快速高效并行排序算法,对长度为 N 的序列进行排序,在具有 N2个处理器和N 条行总线的 RAPWBN 模型上,若总线带宽ω>logN 字节,可以在 O(1)时间完成排序。在具有 N 个处理器和 N 条行总线的 RAPWBN 模型上,最好情况下以 O(logN)时间、最坏情况下以 O(N)时间完成排序。After introducing the basic structure and the binary prefix sum operation of the reconfigurable computational model with wide bus network (RAPWBN), algorithm for the operation of compressing and hence two fast and efficient parallel sorting algorithm on RAPWBN model are presented. One of the algorithm of sorting runs in O(l) time on a RAPWBN model of N2 processors and N-row bus with bandwidth ω>log/V. The other algorithm, using N processors and N-row bus, can sort N elements in O(logN) time at best, in O(N) time at the very worst.

关 键 词：RAPWBN模型 排序 并行算法 SIMD模型 二进制前缀 开关连接形式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]