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

Parallel Sorting Algorithm on Reconfigurable Computational Model with Wide Bus Network

作　　者：陈宏建[1] 陈崚[1] 沈洁[1] 

机构地区：[1]扬州大学信息工程学院计算机系,江苏扬州225009

出　　处：《小型微型计算机系统》2005年第3期344-347,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金资助项目(60473012)资助;国家高性能计算基金资助项目(00219)资助;扬州大学自然科学基金项目(KK0413161)资助

摘　　要：在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的快速高效并行排序算法,在具有N个处理机和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,则对元素位数固定的N个元素可以在O(1)时间完成排序,对元素位数不固定的N个元素,可以在O(k)时间完成排序,这里k为元素的最大位数.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 a parallel sorting algorithm on RAPWBN model are presented. On a RAPWBN of N processors with bandwidth ω>logN, the algorithm can sort N numbers with fixed magnitude in O(1) time and sort N unbounded numbers in O(k) time here k is the largest magnitude of the numbers.

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

分 类 号：TP37[自动化与计算机技术—计算机系统结构] O141.3[自动化与计算机技术—计算机科学与技术]