基于流水光总线阵列的快速并行排序算法  

A Fast Parallel Sorting Algorithm Based on the Reconfigurable Optical Pipeline Bus

作　　者：陈宏建[1] 陈山凌 沈洁[1] 秦玲[1] 徐晓华[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机工程与科学》2004年第5期34-37,共4页Computer Engineering & Science

基　　金：国家自然科学基金资助项目 ( 60 0 740 13 ) ;国家高性能计算基金资助项目 ( 0 0 2 19) ;江苏省教育厅自然科学基金资助项目( 99KJB5 2 0 0 0 3 ) ;南京大学软件新技术国家重点实验室开放基金资助项目

摘　　要：基于流水光总线的可重构线性阵列系统 (LARPBS)是一种建立在光总线上的并行计算模型。本文提出了一种基于LARPBS模型的快速排序并行算法 ,该算法使用n个处理器 ,对关键字位数固定的n个记录可以在O( 1 )时间完成排序 ;对于关键字位数不固定的n个记录 ,可以在O(d)时间完成排序 。Linear array with reconfigurable pipelined bus system (LARPBS) is a parallel computational model based on the optical bus. In this paper we develop a fast parallel sorting algorithm based on LARPBS. Using n processors, the algorithm can sort n records whose keys have a fixed length in O(1) time. It can also sort n records whose keys have arbitrary lengths in O(d) time, here d is the maximum length of the keys.

关 键 词：流水光总线 可重构线性阵列系统 LARPBS模型 排序 并行算法 关键字 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]