Scheduling Direct Acyclic Graphs on Massively Parallel 1K-core Processors

The era of manycore computing will bring new fundamental challenges that the techniques designed for single core processors will have to be dramatically changed to support the coming wave of extreme-scale computing with thousands of cores on a single processor. Today’s programming languages (e.g. C/C++, Java) are unlikely to scale to manycore levels. One approach to address such concurrency problem is to look at many-task computing (MTC). Many MTC applications are structured as graphs of discrete tasks, with explicit input and output dependencies forming the directed edges. We designed both static and dynamic schedulers for such MTC applications, scalable to 1K-cores. The simulation study by using a cycle accurate NoC simulator shows that the proposed strategy result in 85 % shorter makespan and 90 % higher utilization in comparison to random mapping. In addition, our heuristic can tolerate variance of the tasks ’ execution times at runtime and deliver improved makespan and utilization