In order to execute a parallel program Pp on a parallel machinePM, we must determine an allocation function which assigns Pp operationsto PM processors, such that the execution time of Pp is minimum. As thisproblem is known to be NP-complete, a lot of alternative approaches havebeen proposed in the literature. We refer to load balancing (LB)approaches, ie. to mapping algorithms which determine allocationfunction by uniformly distributing the computational load among PMprocessors. Through a simple example we show that internode precedencerelations (IPR) cannot be neglected in LB algorithms when we want toachieve high speed up. As far as we know, LB algorithms do not considerIPR, so we present a new LB algorithm which determines an allocation ofPp on PM respecting IPR. We compare the parallel execution timesachievable through the presented algorithm with the ones given by themapping algorithm described in (Bultan and Aykanar, 1992); comparisons,based on actual executions of Pp with different sizes and granularities,show that the presented algorithm gives performance improvements varyingfrom 6% to 76%
展开▼
