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

摘要：

在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(log√N)时间、最坏情况下以O(√N)时间完成排序.

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

所属期刊栏目：30

分类号：TP37(计算技术、计算机技术)

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

在线出版日期：2005-01-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：17-18,191