Analysis and algorithms for scheduling with minimal switching activities

Zili Shao; Qingfeng Zhuge; Edwin H M Sha; Chantana Chantrapornchai

Analysis and algorithms for scheduling with minimal switching activities

Zili Shao, Qingfeng Zhuge, Edwin H M Sha, Chantana Chantrapornchai

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

Switching activities are one of the important factors in power minimization. This paper studies the scheduling problem which minimizes switching activities. We show that to find the schedule which minimizes switching activities only or minimizes latency and switching activities with or without resource constraints is NP-complete. Two heuristic scheduling algorithms to minimize switching activities are presented. The algorithms use the weighted bipartite matching to find a good schedule. The experimental results show that our algorithms can produce the near-optimal schedule which uses averagely the switching activities 35% less compared to the traditional list scheduling.

Original language	English
Title of host publication	Midwest Symposium on Circuits and Systems
Publication status	Published - 1 Dec 2002
Externally published	Yes
Event	2002 45th Midwest Symposium on Circuits and Systems - Tulsa, OK, United States Duration: 4 Aug 2002 → 7 Aug 2002

Conference

Conference	2002 45th Midwest Symposium on Circuits and Systems
Country/Territory	United States
City	Tulsa, OK
Period	4/08/02 → 7/08/02

ASJC Scopus subject areas

Electrical and Electronic Engineering
Electronic, Optical and Magnetic Materials

Cite this

@inproceedings{068a9b7cd5d047869e579c95c45c5d11,

title = "Analysis and algorithms for scheduling with minimal switching activities",

abstract = "Switching activities are one of the important factors in power minimization. This paper studies the scheduling problem which minimizes switching activities. We show that to find the schedule which minimizes switching activities only or minimizes latency and switching activities with or without resource constraints is NP-complete. Two heuristic scheduling algorithms to minimize switching activities are presented. The algorithms use the weighted bipartite matching to find a good schedule. The experimental results show that our algorithms can produce the near-optimal schedule which uses averagely the switching activities 35% less compared to the traditional list scheduling.",

author = "Zili Shao and Qingfeng Zhuge and Sha, {Edwin H M} and Chantana Chantrapornchai",

year = "2002",

month = dec,

day = "1",

language = "English",

booktitle = "Midwest Symposium on Circuits and Systems",

note = "2002 45th Midwest Symposium on Circuits and Systems ; Conference date: 04-08-2002 Through 07-08-2002",

}

TY - GEN

T1 - Analysis and algorithms for scheduling with minimal switching activities

AU - Shao, Zili

AU - Zhuge, Qingfeng

AU - Sha, Edwin H M

AU - Chantrapornchai, Chantana

PY - 2002/12/1

Y1 - 2002/12/1

N2 - Switching activities are one of the important factors in power minimization. This paper studies the scheduling problem which minimizes switching activities. We show that to find the schedule which minimizes switching activities only or minimizes latency and switching activities with or without resource constraints is NP-complete. Two heuristic scheduling algorithms to minimize switching activities are presented. The algorithms use the weighted bipartite matching to find a good schedule. The experimental results show that our algorithms can produce the near-optimal schedule which uses averagely the switching activities 35% less compared to the traditional list scheduling.

AB - Switching activities are one of the important factors in power minimization. This paper studies the scheduling problem which minimizes switching activities. We show that to find the schedule which minimizes switching activities only or minimizes latency and switching activities with or without resource constraints is NP-complete. Two heuristic scheduling algorithms to minimize switching activities are presented. The algorithms use the weighted bipartite matching to find a good schedule. The experimental results show that our algorithms can produce the near-optimal schedule which uses averagely the switching activities 35% less compared to the traditional list scheduling.

UR - http://www.scopus.com/inward/record.url?scp=0036973862&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

BT - Midwest Symposium on Circuits and Systems

T2 - 2002 45th Midwest Symposium on Circuits and Systems

Y2 - 4 August 2002 through 7 August 2002

ER -

Analysis and algorithms for scheduling with minimal switching activities

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this