摘要： 在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)时间完成排序。
关键词:
LARPBS模型,
可扩展,
排序,
并行算法
Abstract: 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
中图分类号:
陈宏建,陈崚,秦玲,徐晓华,屠莉. 基于流水光总线阵列上的快速可扩展并行排序算法[J]. , 2004, 30(24): 21-.
CHEN Hongjian1, CHEN Ling1,2, QIN Ling1, XU Xiaohua1, TU Li1. Fast and Scalable Parallel Sorting Algorithm Based on LARPBS[J]. , 2004, 30(24): 21-.