Title :
Memory-Aware Optimal Scheduling with Communication Overhead Minimization for Streaming Applications on Chip Multiprocessors
Author :
Wang, Yi ; Liu, Duo ; Qin, Zhiwei ; Shao, Zili
Author_Institution :
Dept. of Comput., Hong Kong Polytech. Univ., Kowloon, China
fDate :
Nov. 30 2010-Dec. 3 2010
Abstract :
In this paper, we focus on solving the problem of removing inter-core communication overhead for streaming applications on chip multiprocessors. The objective is to totally remove inter-core communication overhead while minimizing the overall memory usage. By totally removing inter-core communication overhead, a shorter period can be applied and system throughput can be improved. Our basic idea is to let tasks with intra-period data dependencies transform to inter-period data dependencies so as to overlap the execution of computation and inter-core communication tasks. To solve the problem, we first perform analysis and obtain the bounds of the times needed to reschedule each task. Then we formulate the scheduling problem as an integer linear programming (ILP) model and obtain an optimal schedule. We perform simulations on a set of benchmarks from both real-life streaming applications and synthetic task graphs. The simulation results show that the proposed approach can achieve significant reduction in schedule length and improve the memory usage compared with the previous work.
Keywords :
integer programming; linear programming; multiprocessing systems; processor scheduling; storage management; chip multiprocessors; communication overhead minimization; integer linear programming model; inter-core communication overhead; intra-period data dependencies transform; memory-aware optimal scheduling; real-life streaming applications; synthetic task graphs;
Conference_Titel :
Real-Time Systems Symposium (RTSS), 2010 IEEE 31st
Conference_Location :
San Diego, CA
Print_ISBN :
978-0-7695-4298-0
DOI :
10.1109/RTSS.2010.16