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

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

作者机构：扬州大学信息工程学院计算机系扬州225009 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2004年第30卷第24期

页      面：17-18,191页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0839[工学-网络空间安全] 0835[工学-软件工程] 081201[工学-计算机系统结构] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：LARPBS模裂 可扩展 排序 并行算法 

摘      要：在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)时间完成排序。