Title :
Multi-layer Bus Optimization for Real-Time Task Scheduling with Chain-Based Precedence Constraints
Author :
Hsiu, Pi-Cheng ; Lee, Der-Nien ; Kuo, Tei-Wei
Author_Institution :
Res. Center for Inf. Technol. Innovation, Acad. Sinica, Taipei, Taiwan
Abstract :
One major challenging issue in the designs of multi-core embedded systems is to tackle the communication problem among tasks with performance requirements and precedence constraints. This paper targets the problem of scheduling real-time tasks with chain-based precedence constraints over multi-layer bus systems with an objective to minimize the bus cost. We show the NP-hardness of the problem and the best possible approximation ratio of approximation algorithms. A polynomial-time optimal algorithm is first proposed for a restricted case in which one multi-layer bus and unit execution and communication times are considered. The result is then extended as a pseudo-polynomial-time optimal algorithm in the considerations of multiple multi-layer buses and arbitrary execution and communication times. The capability of the proposed algorithm was evaluated to provide more insights in system designs, compared to some popular heuristics.
Keywords :
algorithm theory; approximation theory; optimisation; processor scheduling; real-time systems; system buses; NP hardness; approximation algorithms; chain based precedence constraints; multilayer bus optimization; polynomial time optimal algorithm; possible approximation ratio; real-time task scheduling; unit execution communication; Constraint optimization; Multi-layer-bus embedded systems; bus cost optimization; precedence constraints; real-time scheduling;
Conference_Titel :
Real-Time Systems Symposium, 2009, RTSS 2009. 30th IEEE
Conference_Location :
Washington, DC
Print_ISBN :
978-0-7695-3875-4
DOI :
10.1109/RTSS.2009.15