TY - GEN
T1 - Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs
AU - Chang, Che Wei
AU - Chen, Jian Jia
AU - Munawar, Waqaas
AU - Kuo, Tei Wei
AU - Falk, Heiko
PY - 2012
Y1 - 2012
N2 - This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1 )-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.
AB - This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1 )-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.
KW - Approximation algorithms
KW - Multiprocessor partitioned scheduling
KW - Real-time systems
KW - Shared SRAM
UR - http://www.scopus.com/inward/record.url?scp=84869014229&partnerID=8YFLogxK
U2 - 10.1145/2380356.2380384
DO - 10.1145/2380356.2380384
M3 - 会议稿件
AN - SCOPUS:84869014229
SN - 9781450314251
T3 - EMSOFT'12 - Proceedings of the 10th ACM International Conference on Embedded Software 2012, Co-located with ESWEEK
SP - 153
EP - 162
BT - EMSOFT'12 - Proceedings of the 10th ACM International Conference on Embedded Software 2012, Co-located with ESWEEK
T2 - 10th ACM International Conference on Embedded Software 2012, EMSOFT 2012, Co-located with 8th Embedded Systems Week, ESWEEK 2012
Y2 - 7 October 2012 through 12 October 2012
ER -