Runtime Scheduling of Dynamic Task Graphs Communication with Embedded Multiprocessors
1K.Gowthami, PG Student, Department of ECE, Anna University of Technology, Coimbatore, India.
2N.Kumaresan Assistant Professor, Department of ECE, Anna University of Technology, Coimbatore, India.
Manuscript received on July 01, 2012. | Revised Manuscript received on July 05, 2012. | Manuscript published on July 10, 2012. | PP: 139-142 | Volume-1, Issue-2, July 2012. | Retrieval Number: B0158061212/2012©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Multiprocessor mapping and scheduling algorithms have been extensively studied over the past few decades and havebeen tackled from different perspectives.Task scheduling is an essential aspect of parallel programming. Most heuristics for this NP-hard problem are based on asimple system model that assumes fully connected processors and concurrent interprocessor communication. Hence, contention for communication resources is not considered in task scheduling, yet it has a strong influence on the execution time of a parallel program. This paper investigates the incorporation of contention awareness into task scheduling. The proposed methodology is runtime scheduling which is designed to reduce the wastage of time during static scheduling. We have assumed heterogeneous processors with broadcast and point-to-point communication models and have presented online algorithms for them. Experimental results shows that dynamic scheduling provides better performance than static scheduling.
Keywords: Static, dynamic, edge scheduling, Heterogeneous processors, Communication between tasks.