出度与平衡度对并行程序固有并行性的约束

The Effect of Out-Degree and Balance-Degree on the Inherent Parallelism of Parallel Programs

摘要: 分析程序的固有并行性虽然困难,但却很重要,因为固有并行性限制了程序并行性开发的限度。本文用两个新的概念——程序步APS 和IPS 来表示数据流图的粒子执行次序,证明出度(OD)与平衡度(BD)是影响执行次序与程序固有并行性的新因素。从而为并行计算时程度划分与重构中提高固有并行性找到了依据。

Abstract: Analysis of the inherent parallelism for parallel programs is a difficult but necessaryresearch The inherent parallelism restricts the development of parallelism in program execution.Byintroducing two new concepts——APS and IPS program stages,the execution order of dataflow graphsis described.It is proved that out-degree(OD)and balance-degree(BD)are two new factors influ-encing the inherent parallelism in parallel programs These factors will help increase the inherentparallelism during partitioning and reconfiguring parallel programs.