Resource Speed Optimization for Two-Stage Flow-Shop Scheduling
Author(s)
Alessandra Melani
Mancuso, Renato
Cullina, Daniel
Caccamo, Marco
Lothar Thiele
Issue Date
2015-11-12
Keyword(s)
scheduling
co-scheduling
I/O
DMA
optimization
power
power-saving
real-time systems
memory
CPU
flow-shop
multi-stage
multi-resource
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 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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
