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

^*Corresponding author for this work

Research output: Contribution to conference › Paper › 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
Pages	I372-I375
State	Published - 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

Cite this

@conference{825f59d830d347d79b9fe7b0574c5554,

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",

language = "英语",

pages = "I372--I375",

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

}

TY - CONF

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

Y1 - 2002

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 - https://www.scopus.com/pages/publications/0036973862

M3 - 论文

AN - SCOPUS:0036973862

SP - I372-I375

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

Other files and links

Fingerprint

Cite this