基于流水光总线阵列上Valiant并行归并排序的实现  

A Valiant Parallel Merge Sorting Algorithm Based on Reconfigurable Optical Pipeline Bus

作　　者：陈宏建[1] 陈崚[1,2] 沈洁[1] 李开荣[1] 罗家奇[1] 

机构地区：[1]扬州大学信息工程学院计算机系 [2]南京大学软件新技术国家重点实验室,南京210093

出　　处：《计算机工程》2004年第9期63-64,138,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60074013);国家高性能计算基金资助项目(00219);江苏省教育厅自然科学基金资助项目(99KJB520003)

摘　　要：基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Valiant并行归并的实现算法,利用该算法对长度为N的序列进行排序,最坏情况下可以使用N个处理器在O(logN loglogN)时间完成。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 .

关 键 词：光总线 LARPBS模型 归并排序 并行算法 Vnliant并行归并排序 

分 类 号：TP37[自动化与计算机技术—计算机系统结构] O141.3[自动化与计算机技术—计算机科学与技术]