@inproceedings{efa3e5a81c1d4106924e9f68dc093091,
title = "Multi-Layer Bus Optimization for Real-Time Task Scheduling with Chain-Based Precedence Constraints",
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 = "Bus cost optimization, Multi-layer-bus embedded systems, Precedence constraints, Real-time scheduling",
author = "Pi-Cheng Hsiu and Der-Nien Lee and Tei-Wei Kuo",
year = "2009",
month = dec,
doi = "10.1109/RTSS.2009.15",
language = "English",
isbn = "9780769538754",
series = "Proceedings - Real-Time Systems Symposium",
publisher = "IEEE",
pages = "479--488",
editor = "Baker, {Theodore P.}",
booktitle = "2009 30th IEEE Real-Time Systems Symposium, RTSS 2009",
address = "United States",
note = "30th IEEE Real-Time Systems Symposium, RTSS 2009 ; Conference date: 01-12-2009 Through 04-12-2009",
}