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

The Maximuim Finding Algorithms Based on LARPBS

作　　者：李庆华[1] 蒋廷耀[2] 

机构地区：[1]国家高性能计算中心,武汉430074 [2]华中科技大学计算机学院,武汉430074

出　　处：《计算机科学》2004年第3期183-185,共3页Computer Science

基　　金：国家自然科学基金(No.60273075)

摘　　要：具备可重配置流水线总线的线性阵列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算法的重要改进。Linear arrays with a reconfijgurable pipelined bus systems (LARPBS) is newly proposed as a parallel computational model, which processors Eare connected by a reconfigurable optical bus- In contrast with theoretical PRAM model,LARPBS is practical and (efficient. In this paper,we present two algorithms for finding the maximum among N data elements with unbounded magnitude and precision on LARPBS. The first algorithm uses N2/2 processors and O(1)time. The second ome uses N processors and (XloglpgN)time. The processors occurpied by the proposed algorithms are half of Y. Pan's algorithms in the same time complexity.

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

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构] TP301.6[自动化与计算机技术—计算机科学与技术]