CSE: State of art seminar - Jagpreet Singh

Title: Duplication heuristics for scheduling real-time precedence constrained tasks on heterogeneous multiprocessors

Speaker: Jagpreet Singh

Date and Time: 9th Dec, 2011, Lecture Hall 2, 3-4 pm

Abstract: Duplication based heuristics have been used for scheduling precedence constrained tasks with significant communication in them. Duplicating heavily communicating subtasks of a  task on to the same processor improves the schedulability as a larger number of tasks meet their deadlines. However, this reduction comes at the cost of extra computing power required for duplicating subtasks. In this paper, we propose a novel real-time duplication based heuristics called RTUBA & RTCDA for scheduling such tasks on heterogeneous multiprocessors. We observe that duplication is not always required. The decision whether to duplicate or not is decided by the deadlines of the tasks. If a task can meet its deadline without duplication, then it creates more schedule holes and vice versa. The algorithms can utilize these schedule holes to improve the success ratio. Preliminary simulation results of RTUBA shows that the proposed algorithm gives a better performance than the other similar algorithms.