Memory-Aware Task Scheduling with Communication Overhead Minimization for Streaming Applications on Bus-Based Multiprocessor System-on-Chips
- 2 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 25 (7) , 1797-1807
Abstract
Inter-core communication introduces overheads in task schedules on Multiprocessor System-on-Chips (MPSoCs). Inter-core communication overhead not only negatively impacts the timing performance but also significantly degrades the memory usage for streaming applications running on MPSoC architectures. By minimizing inter-core communication overhead, a shorter period can be applied and system performance (e.g., throughput, memory usage) can be improved. In this paper, we focus on solving the problem of minimizing inter-core communication overhead for streaming applications on bus-based MPSoCs. The objective is to minimize inter-core communication overhead while minimizing the overall memory usage. To solve the problem, we first 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. By doing this, inter-core communication overhead can be effectively removed. To minimize the overall memory usage, we then perform schedulability analysis and obtain the bounds of the times needed to reschedule each task. Based on the schedulability analysis, we formulate the scheduling problem as an integer linear programming (ILP) model and obtain an optimal schedule. In addition, we propose a heuristic approach to efficiently obtain a near-optimal solution. We conduct experiments on a set of benchmarks from both real-life streaming applications and synthetic task graphs. The experimental results show that the proposed approach can significantly reduce the schedule length and improve the memory usage compared with the previous work.Keywords
This publication has 38 references indexed in Scilit:
- Predictable task migration for locked caches in multi-core systems2011
- A Communication-Driven Routing Technique for Application-Specific NoCsInternational Journal of Parallel Programming, 2010
- Multi-layer Bus Optimization for Real-Time Task Scheduling with Chain-Based Precedence Constraints2009
- CART: Communication-Aware Routing Technique for Application-Specific NoCs2008
- Resource Allocation for Distributed Streaming Applications2008
- Assessing Task Migration Impact on Embedded Soft Real-Time Streaming Multimedia ApplicationsEURASIP Journal on Embedded Systems, 2008
- Bus Access Optimization for Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip2007
- Optimization of static task and bus access schedules for time-triggered distributed embedded systems with model-checkingProceedings of the 39th conference on Design automation - DAC '02, 2007
- Design space exploration of real-time multi-media MPSoCs with heterogeneous scheduling policies2006
- Selective code/data migration for reducing communication energy in embedded MpSoC architectures2006