U. Hönig and W. Schiffmann (Germany)
Task Scheduling, Efficiency, Multi-DAG-Scheduler
This paper is motivated by the poor efficiency of static DAG scheduling algorithms applied on large-sized tar get systems. We analyze the efficiency of different static scheduling heuristics with respect to a large test bench that comprises different graph categories. The poor efficiency can be essentially explained by the lack of sufficient par allelism of single DAG-problems. Thus, we propose to schedule a collection of multiple DAGs simultaneously. Because the constituent DAGs’ subtasks are independent of each other, the degree of parallelism can be increased in this way. Therefore, the processing elements of the tar get system can be utilized more efficiently. By interweav ing the subtasks of different DAGs, the total idle time of the processing elements is reduced and the overall target system’s utilization increases. By merging multiple DAGs into one big compound DAG, we can furthermore apply the whole bunch of already established scheduling heuris tics. The results for some well-known scheduling heuristics indicate that our approach can significantly increase the ef ficiency on a fixed sized target system.
Important Links:
Go Back
