Energy-efficient scheduling for parallel real-time tasks based on level-packing

Fanxin Kong, Nan Guan, Qingxu Deng, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

8 Citations (Scopus)

Abstract

While much work has addressed energy-efficient scheduling for sequential tasks where each task can run on only one processor at a time, little work has been done for parallel tasks where an individual task can be executed by multiple processors simultaneously. In this paper, we develop energy minimizing algorithms for parallel task systems with timing guarantees. For parallel tasks executed by a fixed number of processors, we first propose several heuristic algorithms based on level-packing for task scheduling, and then present a polynomial-time complexity energy minimizing algorithm which is optimal for any given level-packed task schedule. For parallel tasks that can run on a variable number of processors, we propose another polynomial-time complexity algorithm to determine the number of processors executing each task, task schedule and frequency assignment. To the best of our knowledge, this is the first work that addresses energy-efficient scheduling for parallel real-time tasks. Our simulation result shows that the proposed approach can significantly reduce the system energy consumption.
Original languageEnglish
Title of host publication26th Annual ACM Symposium on Applied Computing, SAC 2011
Pages635-640
Number of pages6
DOIs
Publication statusPublished - 23 Jun 2011
Externally publishedYes
Event26th Annual ACM Symposium on Applied Computing, SAC 2011 - TaiChung, Taiwan
Duration: 21 Mar 201124 Mar 2011

Conference

Conference26th Annual ACM Symposium on Applied Computing, SAC 2011
CountryTaiwan
CityTaiChung
Period21/03/1124/03/11

Keywords

  • dynamic voltage scaling
  • energy-efficient scheduling
  • level-packing
  • parallel tasks
  • real-time systems

ASJC Scopus subject areas

  • Software

Cite this