TY - JOUR
T1 - DVS scheduling in a line or a star network of processors
AU - Mu, Zongxu
AU - Li, Minming
PY - 2015/1
Y1 - 2015/1
N2 - Dynamic voltage scaling (DVS) is a technique which allows the processors to change speed when executing jobs. Most of the previous works study either single processor or multiple parallel processors. In this paper, we consider a network of DVS enabled processors. Every job needs to go along a certain path in the network and has a certain workload finished on any processor it goes through before it moves on to the next processor. Our objective is to minimize the total energy consumption while finishing every job before its deadline. Due to the intrinsic complexity of this problem, we only focus on line networks with two nodes and a simple one-level tree network (a star). We show that in some of these simple cases, the optimal schedule can be computed efficiently and interleaving is not needed to achieve optimality. However, in both types of networks, how to find the optimal sequence of execution remains a big challenge for jobs with general workloads.
AB - Dynamic voltage scaling (DVS) is a technique which allows the processors to change speed when executing jobs. Most of the previous works study either single processor or multiple parallel processors. In this paper, we consider a network of DVS enabled processors. Every job needs to go along a certain path in the network and has a certain workload finished on any processor it goes through before it moves on to the next processor. Our objective is to minimize the total energy consumption while finishing every job before its deadline. Due to the intrinsic complexity of this problem, we only focus on line networks with two nodes and a simple one-level tree network (a star). We show that in some of these simple cases, the optimal schedule can be computed efficiently and interleaving is not needed to achieve optimality. However, in both types of networks, how to find the optimal sequence of execution remains a big challenge for jobs with general workloads.
KW - Dynamic voltage scaling
KW - Networks
KW - Optimization
KW - Sequencing
UR - http://www.scopus.com/inward/record.url?scp=84920707951&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84920707951&origin=recordpage
U2 - 10.1007/s10878-013-9668-y
DO - 10.1007/s10878-013-9668-y
M3 - 21_Publication in refereed journal
VL - 29
SP - 16
EP - 35
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 1
ER -