Publications Memory & Shared-Resource Management
Optimizing resource speed for two-stage real-time tasks
Real-Time Systems, 2017
Abstract
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 the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload.
Cite this paper
@article{melani2017optimizing,
title = {{Optimizing resource speed for two-stage real-time tasks}},
author = {Melani, Alessandra and Mancuso, Renato and Cullina, Daniel and Caccamo, Marco and Thiele, Lothar},
journal = {Real-Time Systems},
year = 2017,
volume = {53},
number = {1},
pages = {82--120},
publisher = {Springer Netherlands},
doi = {10.1007/s11241-016-9259-y},
url = {https://doi.org/10.1007/s11241-016-9259-y}
}
TY - JOUR AU - Melani, Alessandra AU - Mancuso, Renato AU - Cullina, Daniel AU - Caccamo, Marco AU - Thiele, Lothar TI - Optimizing resource speed for two-stage real-time tasks JO - Real-Time Systems PY - 2017 VL - 53 IS - 1 PB - Springer Netherlands SP - 82 EP - 120 DO - 10.1007/s11241-016-9259-y UR - https://doi.org/10.1007/s11241-016-9259-y 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 the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload. ER -
%0 Journal Article %A Melani, Alessandra %A Mancuso, Renato %A Cullina, Daniel %A Caccamo, Marco %A Thiele, Lothar %T Optimizing resource speed for two-stage real-time tasks %J Real-Time Systems %D 2017 %V 53 %N 1 %P 82-120 %I Springer Netherlands %R 10.1007/s11241-016-9259-y %U https://doi.org/10.1007/s11241-016-9259-y %X 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 the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload.
[
{
"id": "melani2017optimizing",
"type": "article-journal",
"title": "Optimizing resource speed for two-stage real-time tasks",
"author": [
{
"family": "Melani",
"given": "Alessandra"
},
{
"family": "Mancuso",
"given": "Renato"
},
{
"family": "Cullina",
"given": "Daniel"
},
{
"family": "Caccamo",
"given": "Marco"
},
{
"family": "Thiele",
"given": "Lothar"
}
],
"container-title": "Real-Time Systems",
"issued": {
"date-parts": [
[
2017
]
]
},
"volume": "53",
"issue": "1",
"page": "82-120",
"publisher": "Springer Netherlands",
"DOI": "10.1007/s11241-016-9259-y",
"abstract": "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 the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload."
}
]
A. Melani, R. Mancuso, D. Cullina, M. Caccamo, and L. Thiele, “Optimizing resource speed for two-stage real-time tasks,” Real-Time Systems, vol. 53, no. 1, pp. 82–120, 2017, doi: 10.1007/s11241-016-9259-y.
Melani, A., Mancuso, R., Cullina, D., Caccamo, M., & Thiele, L. (2017). Optimizing resource speed for two-stage real-time tasks. Real-Time Systems, 53(1), 82–120. Springer Netherlands. https://doi.org/10.1007/s11241-016-9259-y