基于PRAM并行模型最大值查找的方法与改进  

Method and Improvement of Maximum Search Based on PRAM Parallel Model

作　　者：贺成 施华君[1] HE Cheng;SHI Hua-Jun(The 32nd Research Institute of China Electronic Technology Group Corporation,Shanghai 201808,China)

机构地区：[1]中国电子科技集团公司第三十二研究所

出　　处：《计算机系统应用》2019年第10期138-144,共7页Computer Systems & Applications

摘　　要：随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM(Parallel Random Access Machine)下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本(cost)更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.With the emergence of multiprocessors,parallel technology has attracted widespread attention and become an important technology to speed up the processing of problems.Nevertheless,the use of parallel technology to speed up computing has also led to a sharp increase in the number of processors and a significant increase in parallel costs.To solve this problem,by studying the shortcomings of three parallel maximum search algorithms based on PRAM(Parallel Random Access Machine),a parallel maximum search algorithm based on data partitioning method is proposed,which is better than the balanced tree algorithm,fast search method and double logarithmic depth tree method.The maximum searching algorithm based on data partitioning method effectively solves the problems of uneven workload allocation,excessive demand for processors and harsh implementation conditions in existing parallel methods.This provides a direction for similar parallel algorithms to reduce parallel costs.

关 键 词：并行算法 最大值 并行成本 并行时间 并行机 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]