10
IRUS Total
Downloads
  Altmetric

Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors

File Description SizeFormat 
HMS_springer.pdfAccepted version496.47 kBAdobe PDFView/Open
10.1007%2Fs11241-017-9291-6.pdfPublished version1.11 MBAdobe PDFView/Open
Title: Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors
Authors: Thammawichai, M
Kerrigan, EC
Item Type: Journal Article
Abstract: We propose three novel mathematical optimization formulations that solve the same two-type heterogeneous multiprocessor scheduling problem for a real-time taskset with hard constraints. Our formulations are based on a global scheduling scheme and a fluid model. The first formulation is a mixed-integer nonlinear program, since the scheduling problem is intuitively considered as an assignment problem. However, by changing the scheduling problem to first determine a task workload partition and then to find the execution order of all tasks, the computation time can be significantly reduced. Specifically, the workload partitioning problem can be formulated as a continuous nonlinear program for a system with continuous operating frequency, and as a continuous linear program for a practical system with a discrete speed level set. The latter problem can therefore be solved by an interior point method to any accuracy in polynomial time. The task ordering problem can be solved by an algorithm with a complexity that is linear in the total number of tasks. The work is evaluated against existing global energy/feasibility optimal workload allocation formulations. The results illustrate that our algorithms are both feasibility optimal and energy optimal for both implicit and constrained deadline tasksets. Specifically, our algorithm can achieve up to 40% energy saving for some simulated tasksets with constrained deadlines. The benefit of our formulation compared with existing work is that our algorithms can solve a more general class of scheduling problems due to incorporating a scheduling dynamic model in the formulations and allowing for a time-varying speed profile.
Issue Date: 1-Sep-2017
Date of Acceptance: 14-Aug-2017
URI: http://hdl.handle.net/10044/1/50432
DOI: https://dx.doi.org/10.1007/s11241-017-9291-6
ISSN: 0922-6443
Publisher: Springer
Start Page: 132
End Page: 165
Journal / Book Title: Real-Time Systems
Volume: 54
Issue: 1
Copyright Statement: © The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Keywords: 0805 Distributed Computing
0803 Computer Software
Computer Hardware & Architecture
Publication Status: Published
Appears in Collections:Electrical and Electronic Engineering
Faculty of Engineering