TY - GEN
T1 - Speed optimization for tasks with two resources
AU - Melani, Alessandra
AU - Mancuso, Renato
AU - Cullina, Daniel
AU - Caccamo, Marco
AU - Thiele, Lothar
N1 - Publisher Copyright:
© 2016 EDAA.
PY - 2016/4/25
Y1 - 2016/4/25
N2 - Multiple resource co-scheduling algorithms and pipelined execution models are becoming increasingly popular, as they better capture the heterogeneous nature of modern architectures. The problem of scheduling tasks composed of multiple stages tied to different resources goes under the name of flow-shop scheduling. This problem, studied since the '50s to optimize production plants, is known to be NP-hard in the general case. In this paper, we consider a specific instance of the flow-shop task model that captures the behavior of a two-resource (DMA-CPU) system. In this setting, we study the problem of selecting the optimal operating speed of either resource with the goal of minimizing power consumption while meeting schedulability constraints. We derive an algorithm that finds an exact solution to the problem in polynomial time, hence it is suitable for online operation even in the presence of variable real-time workload.
AB - Multiple resource co-scheduling algorithms and pipelined execution models are becoming increasingly popular, as they better capture the heterogeneous nature of modern architectures. The problem of scheduling tasks composed of multiple stages tied to different resources goes under the name of flow-shop scheduling. This problem, studied since the '50s to optimize production plants, is known to be NP-hard in the general case. In this paper, we consider a specific instance of the flow-shop task model that captures the behavior of a two-resource (DMA-CPU) system. In this setting, we study the problem of selecting the optimal operating speed of either resource with the goal of minimizing power consumption while meeting schedulability constraints. We derive an algorithm that finds an exact solution to the problem in polynomial time, hence it is suitable for online operation even in the presence of variable real-time workload.
UR - http://www.scopus.com/inward/record.url?scp=84973615740&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84973615740&partnerID=8YFLogxK
U2 - 10.3850/9783981537079_0404
DO - 10.3850/9783981537079_0404
M3 - Conference contribution
AN - SCOPUS:84973615740
T3 - Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016
SP - 1072
EP - 1077
BT - Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 19th Design, Automation and Test in Europe Conference and Exhibition, DATE 2016
Y2 - 14 March 2016 through 18 March 2016
ER -