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

A Parallel Merge Sorting Algorithm for Reconfigurable Computational Models Based on Wide-Bandwidth Bus Networks

作　　者：陈宏建[1] 陈崚[1] 秦玲[1] 徐晓华[1] 屠莉[1] 

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

出　　处：《计算机工程与科学》2005年第5期59-62,共4页Computer Engineering & Science

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

摘　　要：在介绍带有宽总线网络的可重构计算模型(RAPWBN)的二进制值的前缀和操作的基础上,提出了该模型上的抽取压缩操作算法,并由此得到了该模型上的并行归并排序算法。在具有N个处理器和N条行总线的RAPWVN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,在最坏情况下以O(logN·loglogN)时间完成.Based on the architecture and the binary prefix sum operations of reconfigurable computational models based on wide-bandwidth bus networks (RAPWBN), an algorithm for the operation of compressing is presented and hence a parallel merge sorting algorithm on the RAPWBN model is obtained To sort N elements on a RAPWBN with N processors and the N-row bus with bandwidth ω>logN , the algorithm runs in O(logNloglogN) time in the worst case.

关 键 词：计算机系统 可重构计算模型 并行归并排序算法 总线网络 

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