| RAPWBN计算模型上的快速并行归并排序算法 |
| |
| 引用本文： | 陈宏建,陈崚.RAPWBN计算模型上的快速并行归并排序算法[J].小型微型计算机系统,2009,30(12). |
| |
| 作者姓名： | 陈宏建 陈崚 |
| |
| 作者单位： | 1. 扬州大学,信息工程学院计算机系,江苏,扬州,225009
2. 扬州大学,信息工程学院计算机系,江苏,扬州,225009;南京大学,软件新技术国家重点实验室,江苏,南京,210093 |
| |
| 基金项目： | 国家自然科学基金项目，江苏省自然科学基金项目，扬州大学自然科学基金 |
| |
| 摘 要： | 在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.
|
| 关 键 词： | RAPWBN模型 排序 归并 并行算法 |
Parallel Merge Sorting Algorithm Based on RAPWBN Model |
| |
| CHEN Hong-jian,CHEN Ling.Parallel Merge Sorting Algorithm Based on RAPWBN Model[J].Mini-micro Systems,2009,30(12). |
| |
| Authors: | CHEN Hong-jian CHEN Ling |
| |
| Abstract: | After introducing the basic structure and the binary prefix sum operation of the reconfigurable 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 ω>logN,the algorithm runs in O((loglogN)~2)time. |
| |
| Keywords: | RAPWBN model sorting merge parallel algorithm |
| 本文献已被 万方数据 等数据库收录！ |
|
