RAPWBN计算模型上的快速并行归并排序算法  

Parallel Merge Sorting Algorithm Based on RAPWBN Model

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

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

出　　处：《小型微型计算机系统》2009年第12期2461-2464,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673060)资助;江苏省自然科学基金项目(BK2008075)资助;扬州大学自然科学基金项目资助

摘　　要：在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有Nα(1<α<2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)2)时间完成.After introducing the basic structure and the binary prefix sum operation of the reconfigumble computational model with wide bus network （ RAPWBN）, an algorithm for parallel merge sorting on RAPWBN model is presented. The algorithm can sort N elements in O （ { loglogN } 2 } time on a RAPWBN with N^α （ 1 〈 α 〈 2 ） processors and N-row bus with bandwidth to 〉 logN, the algorithm runs in O{ { loglogN）^2 ） time.

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

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