Scheduling Optimization Through Iterative Renement

Scheduling DAGs with communication times is the theoret-ical basis for achieving ecient parallelism on distributed memory systems. We generalize Graham's task-level in a manner to incorporate the eects of computation, data size, and network latency. A new scheduling that uses the pro-posed task-level to make early reservation of resources for critical computation and communication is proposed. We also propose an optimization called Iterative Renement Scheduling (IRS) that alternatively schedules the computa-tion graph and its associated reverse. The task-level used in some scheduling iteration is the task's starting time that is achieved in the very previous iteration. IRS enables search-ing and optimizing solutions as the result of using more re-ned task-level in each scheduling iteration. Evaluation and analysis of the results are carried out for dierent instances of problem granularities, parallelism, and network latency such as the fully connected, hypercube, and ring. The nish time obtained from two-iteration schedul-ing outperforms those generated by other recently proposed scheduling as well as the clustering approaches. IRS allows exploring a space of solutions whose size grows with the amount of parallelism and communication granu-larity. Solutions generated by IRS largely outperform all known approaches specially for ne-grain problems where other approaches fail. IRS enables optimizing the solution specially for critical instances such as ne-grain DAGs and large parallelism. The time complexity of one IRS iteration is O(pn2).