| 带有宽总线网络的可重构计算模型上的并行归并排序算法 |
| |
| 引用本文： | 陈宏建,陈崚,秦玲,徐晓华,屠莉.带有宽总线网络的可重构计算模型上的并行归并排序算法[J].计算机工程与科学,2005,27(5):59-62. |
| |
| 作者姓名： | 陈宏建 陈崚 秦玲 徐晓华 屠莉 |
| |
| 作者单位： | 扬州大学信息工程学院,江苏,扬州,225009;扬州大学信息工程学院,江苏,扬州,225009;南京大学软件新技术国家重点实验室,江苏,南京,210093 |
| |
| 基金项目： | 国家自然科学基金资助项目(60473012)
国家高性能计算基金资助项目(00219)
江苏省教育厅自然科学基金资助项目(99KJ852003)
扬州大学自然科学基金资助项目(KK0413161) |
| |
| 摘 要： | 在介绍带有宽总线网络的可重构计算模型(RAPWBN)的二进制值的前缀和操作的基础上，提出了该模型上的抽取压缩操作算法，并由此得到了该模型上的并行归并排序算法。在具有N个处理器和N条行总线的RAPWBN模型上，若总线带宽ω>log N字节，对长度为N的序列进行归并排序，在最坏情况下以O(logN·loglogN)时间完成。
|
| 关 键 词： | RAPWBN模型 归并排序 并行算法 |
| 文章编号： | 1007-130X(2005)05-0059-04 |
| 修稿时间： | 2003年10月11 |
A Parallel Merge Sorting Algorithm for Reconfigurable Computational Models Based on Wide-Bandwidth Bus Networks |
| |
| CHEN Hong-jian,CHEN Ling,QIN Ling,XU Xiao-hua,TU Li.A Parallel Merge Sorting Algorithm for Reconfigurable Computational Models Based on Wide-Bandwidth Bus Networks[J].Computer Engineering & Science,2005,27(5):59-62. |
| |
| Authors: | CHEN Hong-jian CHEN Ling QIN Ling XU Xiao-hua TU Li |
| |
| Abstract: | 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. |
| |
| Keywords: | RAPWBN model merge sorting parallel algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
