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

Fast and Scalable Parallel Sorting Algorithm Based on LARPBS

作　　者：陈宏建[1] 陈崚[1] 秦玲[1] 徐晓华[1] 屠莉[1] 

机构地区：[1]扬州大学信息工程学院计算机系,扬州225009

出　　处：《计算机工程》2004年第24期17-18,191,共3页Computer Engineering

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

摘　　要：在Y.Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间,最坏情况下以O(N)时间完成的并行排序算法的基础上,提出了一种LARPBS模型上的可扩展的快速并行排序算法,对N个元素进行排序,使用p(1≤p≤N)个处理器在最好情况下以O(NlogN/p)时间,最坏情况下以O(N2/p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法,该算法对N个元素进行排序使用N个处理器在最好情况下以O(logN)时间、最坏情况下以O(N)时间完成排序。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

关 键 词：LARPBS模裂 可扩展 排序 并行算法 

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