Optimizing resource speed for two-stage real-time tasks

详细信息    查看全文

• 作者：Alessandra Melani ; Renato Mancuso ; Daniel Cullina ; Marco Caccamo…
• 关键词：Co ; scheduling ; Schedulability analysis ; Flow ; shop scheduling ; Multi ; stage model ; Multi ; resource model ; Power saving ; Energy saving ; Speed optimization ; Real ; time systems
• 刊名：Real-Time Systems
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：53
• 期：1
• 页码：82-120
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computer Systems Organization and Communication Networks; Communications Engineering, Networks; Special Purpose and Application-Based Systems; Performance and Reliability; Control, Robotics, Mechatron
• 出版者：Springer US
• ISSN：1573-1383
• 卷排序：53

文摘

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.