| 基于流水光总线阵列上的快速可扩展并行排序算法 |
| |
| 引用本文： | 陈宏建,陈崚,秦玲,徐晓华,屠莉. 基于流水光总线阵列上的快速可扩展并行排序算法[J]. 计算机工程, 2004, 30(24): 17-18,191 |
| |
| 作者姓名： | 陈宏建 陈崚 秦玲 徐晓华 屠莉 |
| |
| 作者单位： | 扬州大学信息工程学院计算机系,扬州,225009;扬州大学信息工程学院计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,210093 |
| |
| 基金项目： | 国家自然科学基金资助项目(60074013)，国家高性能计算基金资助项目(00219)，江苏省教育厅自然科学基金资助项目 |
| |
| 摘 要： | 在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。
|
| 关 键 词： | LARPBS模型 可扩展 排序 并行算法 |
| 文章编号： | 1000-3428(2004)24-0017-02 |
Fast and Scalable Parallel Sorting Algorithm Based on LARPBS |
| |
| CHEN Hongjian,CHEN Ling,,QIN Ling,XU Xiaohua,TU Li. Fast and Scalable Parallel Sorting Algorithm Based on LARPBS[J]. Computer Engineering, 2004, 30(24): 17-18,191 |
| |
| Authors: | CHEN Hongjian CHEN Ling QIN Ling XU Xiaohua TU Li |
| |
| Affiliation: | CHEN Hongjian1,CHEN Ling1,2,QIN Ling1,XU Xiaohua1,TU Li1 |
| |
| Abstract: | Based on Y.Pans parallel sorting algorithm, which is on linear array with reconfiguarble pipeline optical bus system (LARPBS) with N processors in O(logN) time in the best case and O(N) in the worst case, a scalable fast parallel sorting algorithm on LARPBS is presented. The algorithm can sort N elements in O(NlogN/p) time in the best case and O(N2/p)in the worst case using p processors. This paper also presents a fast and efficient parallel sorting algorithm on LARPBS which uses N processors in O(log )time inNthe best case and O( )in the worst case. N |
| |
| Keywords: | LARPBS model Scalable Sorting Parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
