期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于LARPBS模型的快速并行归并排序算法

A fast parallel merge sorting algorithm based on LARPBS model
在线阅读 下载PDF
导出
摘要 提出了一种基于LARPBS模型上的并行归并排序算法,该算法使用M1+ε(0<ε<1)个处理器可以在O(lb lbM)时间内对Mε个有序序列进行归并.利用该归并算法对长度为N的序列进行排序,使用N1+ε个处理器可以在O((lb lb N)2)时间内完成. In this paper a fast parallel merge sorting algorithm based on LARPBS is presented. This method uses M^1＋ε（0〈ε〈1） processors to merge the M^ε sorted sequence in O（lb lb M） time. With this merge algorithm, N^1＋ε processors can be used to sort N elements in O（（lh lb N）^2） time.
作者 陈宏建 陈峻 吕为
机构地区 扬州大学信息工程学院
出处 《扬州大学学报（自然科学版）》 CAS CSCD 2005年第3期1-5,共5页 Journal of Yangzhou University：Natural Science Edition
基金 国家自然科学基金资助项目(60473012) 国家高性能计算基金资助项目(00219) 江苏省教育厅自然科学基金资助项目(99KJB520003) 扬州大学科研基金资助项目(KK0413161)
关键词 光总线 LARPBS模型 归并排序 并行算法 optical bus LARPBS model merge sorting parallel algorithms
分类号 O141.3 [理学—基础数学] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献10

  • 1钟诚,陈国良.PRAM和LARPBS模型上的近似串匹配并行算法[J].软件学报,2004,15(2):159-169. 被引量：19
  • 2陈国良.并行算法设计与分析(修订版)[M].北京:高等教育出版社,2002..
  • 3PAN Y. Basic data movement operations on the LARPBS model [A]. LI K, PAN Y, ZHENG S Q. Parallel Computing Using Optical Interconnections [C]. Boston, USA: Kluwer Academic Publishers, 1998. 227～247.
  • 4PAVEL S, AKL S G. Computing the Hough transformation on arrays with reconfigurable optical buses [A]. LI K, PAN Y, ZHENG S Q. Parallel Computing Using Optical Interconnections [C]. Boston, USA: Kluwer Academic Publishers, 1998. 205～226.
  • 5RAJASEKARAM S, SAHNI S. Sorting, selection and routing on the arrays with reconfigurable optical buses[J]. IEEE Trans Par & Distr Sys, 1997, 8(11): 1123～1131.
  • 6QIAO C, MEI Y. On efficient embedding of binary trees in reconfigurable arrays with spanning optical buses [J].J Par & Distr Sys & Networks, 1999, 2(1): 40～48.
  • 7PAN Y, LI K, ZHENG S Q. Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system [J]. Par Algorithms & Appl, 1998, 13(1): 1～25.
  • 8陈燏,陈宏建,徐晓华,秦玲.一种快速高效的Hough变换并行算法[J].电子学报,2004,32(5):759-762. 被引量：7
  • 9陈宏建,陈崚,李开荣,罗家奇.基于流水光总线阵列的快速数值计算并行算法[J].扬州大学学报（自然科学版）,2003,6(3):58-65. 被引量：1
  • 10陈宏建,陈崚,秦玲,徐晓华,屠莉.带有宽总线网络的可重构计算模型上的并行归并排序算法[J].计算机工程与科学,2005,27(5):59-62. 被引量：2

二级参考文献57

  • 1陈潘毅 陈宏建 等.基于流水光总线可重构线性阵列模型[J].南京大学学报(自然科学),2002,38:88-94.
  • 2陈峻 潘毅 陈宏建 等.基于流水光总线可重构线性阵列模型[J].南京大学学报(自然科学，计算机专刊),2002,38(1):88-94.
  • 3SHEN W F, YU S N, XU W M. Row-fixation-A parallel algorighm for matrix computing[J]. J Shanghai Univ (Eng Ed), 2000, 4(12): 119-122.
  • 4LEIGHTON T. Introduction to parallel algorithms and architectures: arrays · trees · hypercubes[M]. San Mateo, CA: Morgan Kaufmann, 1992.
  • 5LI K Q, VICTOR Y P. Parallel matrix multiplication on a linear array with a reconfigurable pipelined bus system[J]. IEEE Trans Compr, 2001, 50(5): 519-525.
  • 6PAVEL S, AKL S G. Computing the hough transformation on arrays with reconfigurable optical buses[A]. Li K, et al. Parallel Computing Using Optical Intereonneetions[C]. Boston: Kluwer Aead Publ, 1998. 205-226.
  • 7QIAO C, MEI Y. On efficient embedding of binary trees in reconfigurable arrays with spanning optical buses[J]. J Par & Distr Sys & Networks, 1999, 2(1): 40-48.
  • 8PAN Y, LI K. Linear array with a reconfigurable pipelined bus system: concepts and applications[J]. Inf Sci,1998, 106(3,4):237-258.
  • 9PAN Y. Basic data movement operations on the LARPBS model[A]. Li K, et al. Parallel Computing Using Optical Interconnections[C]. Boston:Kluwer Acad Publ, 1998. 227-247.
  • 10GUO Z, MELHEM R, HALL R, et al. Pipelined communication in optically interconnected arrays[J]. J Par & Distr Computing, 1991, 12(3): 269-282.

共引文献25

扬州大学学报（自然科学版）
2005年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部