摘要： 基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Valiant并行归并的实现算法,利用该算法对长度为N的序列进行排序,最坏情况下可以使用N个处理器在O(logN loglogN)时间完成。
关键词:
光总线,
LARPBS模型,
归并排序,
并行算法
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 .
中图分类号:
陈宏建,陈崚,沈洁,李开荣,罗家奇. 基于流水光总线阵列上Valiant并行归并排序的实现[J]. , 2004, 30(09): 67-.
CHEN Hongjian1, CHEN Ling1,2, SHEN Jie1, LI Kairong1, LUO Jiaqi1. A Valiant Parallel Merge Sorting Algorithm Based on Reconfigurable Optical Pipeline Bus[J]. , 2004, 30(09): 67-.