| 基于流水光总线阵列上Valiant并行归并排序的实现 |
| |
| 引用本文： | 陈宏建,陈崚,沈洁,李开荣,罗家奇.基于流水光总线阵列上Valiant并行归并排序的实现[J].计算机工程,2004,30(9):63-64,138. |
| |
| 作者姓名： | 陈宏建 陈崚 沈洁 李开荣 罗家奇 |
| |
| 作者单位： | 1. 扬州大学信息工程学院计算机系,扬州,225009
2. 扬州大学信息工程学院计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,21003 |
| |
| 基金项目： | 国家自然科学基金资助项目（60074013），国家高性能计算基金资助项目（00219），江苏省教育厅自然科学基金资助项目（99KJB520003） |
| |
| 摘 要： | 基于流水总线的可重构线性阵列系统（LARPBS）是一种建立在光总线上的并行计算模型，许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Vnliant并行归并的实现算法，利用该法对长度为N的序列进行排序，最坏情况下可以使用N个处理器在O（logNloglogN)时间完成。
|
| 关 键 词： | 光总线 LARPBS模型 归并排序 并行算法 Vnliant并行归并排序 |
| 文章编号： | 1000-3428(2004)09-0063-02 |
A Valiant Parallel Merge Sorting Algorithm Based on Reconfigurable Optical Pipeline Bus |
| |
| CHEN Hongjian,CHEN Ling,SHEN Jie,LI Kairong,LUO Jiaqi.A Valiant Parallel Merge Sorting Algorithm Based on Reconfigurable Optical Pipeline Bus[J].Computer Engineering,2004,30(9):63-64,138. |
| |
| Authors: | CHEN Hongjian CHEN Ling SHEN Jie LI Kairong LUO Jiaqi |
| |
| Affiliation: | CHEN Hongjian1,CHEN Ling1,2,SHEN Jie1,LI Kairong1,LUO Jiaqi1 |
| |
| Abstract: | Linear array with reconfigurable pipelined bus system (LARPBS) is a parallel computational model based on optical bus, on which many researchers have developed efficient parallel algorithm. In this paper, a Valiant parallel merge sorting algorithm based on LARPBS is presented. With this algorithm, people can use N processors to sort N elements in O(logNloglogN) time at the least . |
| |
| Keywords: | Optical bus LARPBS model Merge sorting Parallel algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
