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

在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。     

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

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

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

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

带有宽总线网络的可重构计算模型上的并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的二进制值的前缀和操作的基础上,提出了该模型上的抽取压缩操作算法,并由此得到了该模型上的并行归并排序算法。在具有N个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>log N字节,对长度为N的序列进行归并排序,在最坏情况下以O(logN·loglogN)时间完成。     

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

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

RAPWBN计算模型上的快速并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.     

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

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

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

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

一种改进的矩阵幂运算及其性能分析

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

基于LARPBS模型的最大值查找算法

具备可重配置流水线总线的线性阵列LARPBS(1inear 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算法的重要改进。     

可重构流水线总线并行机上图像的聚类算法

聚类是图像处理中的一个基本操作。对于分为K个簇的N个模式,且每个模式含有M个特征,该文在N个处理器的一维可重构流水线总线并行机上提出了一个时间复杂度为O(M×K)的聚类操作中一次迭代的并行算法。并对该并行算法进行了扩展,使得当处理器数分别为N×M和N×M×K时,一次迭代的时间复杂度分别为O(K)和O(1)。     

Fast sorting algorithms on a linear array with a reconfigurablepipelined bus system

We present two fast algorithms for sorting on a linear array with a reconfigurable pipelined bus system (LARPBS), one of the recently proposed parallel architectures based on optical buses. In our first algorithm, we sort N numbers in O(log N log log N) worst-case time using N processors. In our second algorithm, we sort N numbers in O((log log N)²) worst-case time using N^1+ε processors, for any fixed ε such that 0 < ε < 1. Our algorithms are based on a novel deterministic sampling scheme for merging two sorted arrays of length N each in O(log log N) time on an LARPBS with N processors. To our knowledge, the previous best sorting algorithm on this architecture has a running time of O((log N)²) using N processors     

Optimal Sorting Algorithms for a Simplified 2D Array with Reconfigurable Pipelined Bus System

In recent years, many researchers have investigated optical interconnections as parallel computing. Optical interconnections are attractive due to their high bandwidth and concurrent access to the bus in a pipelined fashion. The Linear Array with Reconfigurable Pipelined Bus System (LARPBS) model is a powerful optical bus system that combines both the advantages of optical buses and reconfiguration. To increase the scalability of the LARPBS model, we propose a two-dimensional extension: a simplified two-dimensional Array with Reconfigurable Pipelined Bus System (2D ARPBS). While achieving better scalability, we show the effectiveness of this newly proposed model by designing two novel optimal sorting algorithms on this model. The first sorting algorithm is an extension of Leighton's seven-phase columnsort algorithm that eliminates the restriction of sorting only an r times s array, where r ge s^2 , and sorts an n times n array in O(log n) time. The second one is an optimal multiway mergesort algorithm that uses a novel processor efficient two-way mergesort algorithm and a novel multiway merge scheme to sort n^2 items in O(log n) time. Using an optimal sorting algorithm Pipelined Mergesort designed for the LARPBS model as a building block, we extend our research on parallel sorting on the LARPBS to a more scalable 2D ARPBS model and achieve optimality in both sorting algorithms.