Files in this item

FilesDescriptionFormat

application/pdf

application/pdfflowshop-TR.pdf (449kB)
Main Tech Report FilePDF

Description

Title:Resource Speed Optimization for Two-Stage Flow-Shop Scheduling
Author(s):Alessandra Melani; Renato Mancuso; Daniel Cullina; Marco Caccamo; Lothar Thiele
Subject(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.
Issue Date:2015-11-12
Genre:Technical Report
Type:Text
Image
Language:English
URI:http://hdl.handle.net/2142/88404
Sponsor:CNS-1035736
CNS-1219064
CNS-1302563
Date Available in IDEALS:2015-11-12


This item appears in the following Collection(s)

Item Statistics