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

1

作者 陈宏建 陈峻 吕为 《扬州大学学报（自然科学版）》 CAS CSCD 2005年第3期1-5,共5页

提出了一种基于LARPBS模型上的并行归并排序算法,该算法使用M1+ε(0<ε<1)个处理器可以在O(lb lbM)时间内对Mε个有序序列进行归并.利用该归并算法对长度为N的序列进行排序,使用N1+ε个处理器可以在O((lb lb N)2)时间内完成.

关键词 光总线 larpbs模型 归并排序 并行算法

在线阅读 下载PDF 职称材料

基于LARP BS模型的最大值查找算法 被引量：1

2

作者 李庆华 蒋廷耀 《计算机科学》 CSCD 北大核心 2004年第3期183-185,共3页

具备可重配置流水线总线的线性阵列LARPBS(linear arrays with a reconfigurable pipelined bus systems)是近来出现的一种高效的并行计算模型,与理想的PRAM模型不同,LARPBS是现实可行的。基于LARPBS模型,Y.Pan介绍了2种宽度和精度任意... 具备可重配置流水线总线的线性阵列LARPBS(linear arrays with a reconfigurable pipelined bus systems)是近来出现的一种高效的并行计算模型,与理想的PRAM模型不同,LARPBS是现实可行的。基于LARPBS模型,Y.Pan介绍了2种宽度和精度任意的数据项的最大值查找算法:算法1使用了N^2/2个处理机、O(1)时间,它是目前时间最优的算法;算法2使用了N个处理机、O(loglogN)时间。本文介绍了2种最大值查找算法,时间复杂度同Y.Pan的算法,但所用处理机数减少了一半,这是对Y.Pan算法的重要改进。 展开更多

关键词 最大值查找算法 larpbs模型 并行计算模型 并行计算机 流水线总线 线性阵列

在线阅读 下载PDF 职称材料

基于流水光总线的可重构线性阵列模型

3

作者 陈崚 潘毅 +1 位作者 陈宏建 秦玲 《计算机工程与应用》 CSCD 北大核心 2003年第30期65-68,78,共5页

该文主要介绍基于流水光总线的可重构线性阵列系统(LARPBS)模型及其基本数据传输和操作,并以矩阵乘法和排序为例介绍了LARPBS上的并行算法及其设计方法。

关键词 光总线 larpbs模型 矩阵乘法 排序 并行算法

在线阅读 下载PDF 职称材料

基于流水光总线模型的快速归并排序算法

4

作者 刘玉慧 陈宏建 陈崚 《计算机工程与应用》 CSCD 北大核心 2006年第3期28-32,共5页

文章提出了一种LARPBS模型上的并行归并排序算法,利用该算法对长度为N的序列进行排序,使用N^(1+)着(0<着<1)个处理机可以在O((loglogN)~2)时间完成。

关键词 光总线 larpbs模型 归并排序 并行算法

在线阅读 下载PDF 职称材料

一种改进的矩阵幂运算及其性能分析 被引量：1

5

作者 陈宏建 陈崚 +1 位作者 沈洁 李开荣 《计算机工程与应用》 CSCD 北大核心 2003年第33期61-64,共4页

基于流水光总线的可重构线性阵列系统是一种建立在光总线上的并行高效计算模型。该文给出了一种LARPBS模型上改进的矩阵幂运算并行算法,并对其可扩展性和复杂性进行分析,通过分析可以看出,该算法是目前速度最快、成本最优的并行矩阵幂... 基于流水光总线的可重构线性阵列系统是一种建立在光总线上的并行高效计算模型。该文给出了一种LARPBS模型上改进的矩阵幂运算并行算法,并对其可扩展性和复杂性进行分析,通过分析可以看出,该算法是目前速度最快、成本最优的并行矩阵幂运算算法。 展开更多

关键词 larpbs模型 矩阵幂 复杂性 可扩展性 并行算法

在线阅读 下载PDF 职称材料

关联维数的并行求解算法 被引量：1

6

作者 蒋廷耀 李庆华 杨景华 《计算机科学》 CSCD 北大核心 2004年第7期169-170,F004,共3页

关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要。过去的改进算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数.其应... 关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要。过去的改进算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数.其应用范围和性能改善程度是有限的。本文给出了两个并行算法:基于PRAM模型的花费O(N^2/p+logp)时间p个处理机的算法,和基于LARPBS模型的花费O(N^2/p)时间p个处理机的算法。相对纯理论的PRAM算法,LARPBS算法是实际可行的,它是目前时间复杂度最低的算法,并且是最优可扩展和成本最优的。 展开更多

关键词 关联维数 并行算法 分形理论 PRAM模型 larpbs模型

在线阅读 下载PDF 职称材料

基于流水光总线阵列上Valiant并行归并排序的实现

7

作者 陈宏建 陈崚 +2 位作者 沈洁 李开荣 罗家奇 《计算机工程》 CAS CSCD 北大核心 2004年第9期63-64,138,共3页

基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Valiant并行归并的实现算法,利用该算法对长度为N的序列进... 基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Valiant并行归并的实现算法,利用该算法对长度为N的序列进行排序,最坏情况下可以使用N个处理器在O(logN loglogN)时间完成。 展开更多

关键词 光总线 larpbs模型 归并排序 并行算法 Vnliant并行归并排序

在线阅读 下载PDF 职称材料

基于流水光总线阵列的快速矩阵运算

8

作者 陈宏建 陈崚 +1 位作者 秦玲 徐晓华 《计算机工程与应用》 CSCD 北大核心 2003年第27期73-76,79,共5页

矩阵运算是最重要的数值计算,基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行高效计算模型。该文主要介绍LARPBS模型上的快速并行矩阵运算,从而使人们更加了解光总线计算模型及其优越性,为今后进一步研究光总... 矩阵运算是最重要的数值计算,基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行高效计算模型。该文主要介绍LARPBS模型上的快速并行矩阵运算,从而使人们更加了解光总线计算模型及其优越性,为今后进一步研究光总线模型及其并行算法奠定基础。 展开更多

关键词 光总线 larpbs模型 矩阵运算 并行算法

在线阅读 下载PDF 职称材料

基于流水光总线阵列的快速矩阵乘法运算

9

作者 陈宏建 陈崚 秦玲 《计算机工程与应用》 CSCD 北大核心 2003年第23期71-75,共5页

基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。该文主要介绍了LARPBS模型及其快速矩阵乘法运算,从而使人们更加了解光总线计算模型及其优... 基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。该文主要介绍了LARPBS模型及其快速矩阵乘法运算,从而使人们更加了解光总线计算模型及其优越性,为今后进一步研究光总线模型及其并行算法奠定了基础。 展开更多

关键词 光总线 larpbs模型 矩阵乘法 并行算法

在线阅读 下载PDF 职称材料

基于流水光总线阵列的快速矩阵运算

10

作者 陈宏建 陈崚 +1 位作者 秦玲 徐晓华 《徐州师范大学学报（自然科学版）》 CAS 2002年第4期38-41,共4页

基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行高效计算模型.介绍LARPBS模型上的一些快速而又高效的矩阵运算并行算法,包括矩阵转置、矩阵连加、矩阵与向量的乘积、矩阵乘法、矩阵幂以及矩阵连乘等,除矩阵幂... 基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行高效计算模型.介绍LARPBS模型上的一些快速而又高效的矩阵运算并行算法,包括矩阵转置、矩阵连加、矩阵与向量的乘积、矩阵乘法、矩阵幂以及矩阵连乘等,除矩阵幂运算和矩阵的连乘运算在O(logN)时间完成之外,其余矩阵运算均可在O(1)时间完成.这与以往的其他同类并行算法相比,效率都提高了O(logN),而且速度达到了最优. 展开更多

关键词 流水光总线 光总线阵列 larpbs模型 矩阵运算 并行算法 可重构线性阵列系统 光纤技术

在线阅读 下载PDF 职称材料

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

11

作者 陈宏建 陈山凌 +2 位作者 沈洁 秦玲 徐晓华 《计算机工程与科学》 CSCD 2004年第5期34-37,共4页

基于流水光总线的可重构线性阵列系统 (LARPBS)是一种建立在光总线上的并行计算模型。本文提出了一种基于LARPBS模型的快速排序并行算法 ,该算法使用n个处理器 ,对关键字位数固定的n个记录可以在O( 1 )时间完成排序 ;对于关键字位数不... 基于流水光总线的可重构线性阵列系统 (LARPBS)是一种建立在光总线上的并行计算模型。本文提出了一种基于LARPBS模型的快速排序并行算法 ,该算法使用n个处理器 ,对关键字位数固定的n个记录可以在O( 1 )时间完成排序 ;对于关键字位数不固定的n个记录 ,可以在O(d)时间完成排序 。 展开更多

关键词 流水光总线 可重构线性阵列系统 larpbs模型 排序 并行算法 关键字

在线阅读 下载PDF 职称材料

快速可扩展的矩阵幂运算并行算法及其应用

12

作者 陈宏建 李开荣 罗家奇 《扬州大学学报（自然科学版）》 CAS CSCD 2004年第3期36-40,共5页

提出了一种LARPBS模型上改进的矩阵幂运算并行算法,将它应用于矩阵的逆运算和矩阵的LU分解,分析了它们的可扩展性和复杂性.通过分析可以看出,这些算法是目前成本最优的并行算法.

关键词 larpbs模型 可扩展性 并行算法

在线阅读 下载PDF 职称材料

一种快速高效的Hough变换并行算法 被引量：7

13

作者 陈燏 陈宏建 +1 位作者 徐晓华 秦玲 《电子学报》 EI CAS CSCD 北大核心 2004年第5期759-762,共4页

本文提出了一种基于流水光总线可重构线性阵列 (LARPBS)模型的快速高效Hough变换算法 .该算法利用LARPBS有力的通讯功能和计算能力 ,对直线上的黑色象素进行抽取和统计 .对于大小为n×n的二值数字图象、m个θ参数值 ,本算法可以使用... 本文提出了一种基于流水光总线可重构线性阵列 (LARPBS)模型的快速高效Hough变换算法 .该算法利用LARPBS有力的通讯功能和计算能力 ,对直线上的黑色象素进行抽取和统计 .对于大小为n×n的二值数字图象、m个θ参数值 ,本算法可以使用mn2 个处理机在O(1)时间完成 ,从而使速度和效率都达到最优 .文中还给出当LARPBS中处理机个数少于mn2 时的算法分解执行方法 ,说明算法具有很好的可扩放性 . 展开更多

关键词 larpbs模型 HOUGH变换 并行算法

在线阅读 下载PDF 职称材料

多序列比对问题的并行近似算法 被引量：3

14

作者 宋彬 陈国良 +1 位作者 鄢超 沈一飞 《中国科学技术大学学报》 CAS CSCD 北大核心 2005年第5期656-664,共9页

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m+logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方... 基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m+logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m+log logD),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log logD通常远小于m,所以它在理论上也是线性加速的. 展开更多

关键词 多序列比对 并行算法 SIMD-CREW larpbs模型 SP比对

在线阅读 下载PDF 职称材料