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

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.