Scheduling Task Graphs on Heterogeneous Multiprocessors with Reconfigurable Hardware
Justin Teller, F. Özgüner, Robert L. Ewing · Proceedings - International Workshops on Parallel Processing · 2008
We address the problem of scheduling applications represented as directed acyclic task graphs (DAGs) onto architectures with reconfigurable processing cores. We introduce the Mutually Exclusive Processor Groups reconfiguration model, a novel reconfiguration model that captures many different modes of reconfiguration. Additionally, we propose the Heterogeneous Earliest Finish Timewith Mutually Exclusive Processor Groups (HEFT-MEG) scheduling heuristic using the Mutually Exclusive Processor Groups reconfiguration model. HEFT-MEG schedules reconfigurations using a novel back-tracking algorithm to evaluate how different reconfiguration decisions affect previously scheduled tasks. HEFT-MEGÕs goal when choosing configurations is to choose the most efficient configuration for different application phases. In simulation, HEFT-MEG generates higher quality schedules than those generated by the hardware-software co-scheduler proposed by Mei, etal. [21] and HEFT [31] using a single configuration.