数据不规则问题全相关Block递归方程组多维流水线并行技术研究  

Research on Multi-Dimensional Pipeline Parallel Solution of All-Correlative Block Recursive Equations for Data-Irregular Problems

作　　者：刘鑫[1] 陆林生[1] 

机构地区：[1]江南计算技术研究所,无锡214083

出　　处：《计算机学报》2006年第10期1750-1756,共7页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2003AA723042);国家自然科学基金(10072077)资助.

摘　　要：主要讨论数据不规则问题全相关Block递归方程组多维流水线并行的实现.首先给出全相关Block递归方程组的模型方程,并从图论的角度给出了流水关系有向图的定义以及流水线并行条件的判别准则,分析了影响流水线并行效率的主要因素.在此基础上,提出一种基于流水关系有向图的流水线并行实现算法并应用于数据不规则问题.实验结果表明该方法在复杂区域情况下也可以取得较高的效率.This paper mainly discusses multi-dimensional pipeline parallel solution of the all-correlative block recursive equations for data-irregular problems. First, the mathematic model of the all-correlative block recursive equations is supplied. Then from the viewpoint of graph theory, the paper gives the definition of pipeline relationship directional graph and the condition of whether the pipeline parallel computing can be implemented. Based on these, the main factors which affect the pipeline parallel efficiency are given and a pipeline parallel implementing algorithm based upon pipeline relationship directional graph which can be applied in data-irregular problems is presented. The experimental results show that the algorithm can get high efficiency in complicated computing area.

关 键 词：数据不规则问题 流水线并行计算 流水关系有向图 

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