TY - GEN
T1 - Discrete min-energy scheduling on restricted parallel processors
AU - Jin, Xibo
AU - Zhang, Fa
AU - Liu, Zhiyong
PY - 2013
Y1 - 2013
N2 - Different from the previous work on energy-efficient algorithms, which focused on assumption that a task can be assigned to any processor, we study the problem of task Scheduling with the objective of Energy Minimization on Restricted Parallel Processors (SEMRPP). Restriction accounts for affinities between tasks and processors, that is, a task has its own eligible processing set of processors. It assumes all tasks have a prescribed deadline on the execution time. We study the processors run at a finite number of distinct speeds, and the processors cannot change its speed during the computation of a task. Our work is motivated by the practical variable voltage processors that they cannot run at arbitrary speed and the task may be failure if the processor adjusts its speed during the computation of the task. We assess the complexity of the problem and present a polynomial time approximation algorithm with a bounded factor related to the adjacent speed ratio.
AB - Different from the previous work on energy-efficient algorithms, which focused on assumption that a task can be assigned to any processor, we study the problem of task Scheduling with the objective of Energy Minimization on Restricted Parallel Processors (SEMRPP). Restriction accounts for affinities between tasks and processors, that is, a task has its own eligible processing set of processors. It assumes all tasks have a prescribed deadline on the execution time. We study the processors run at a finite number of distinct speeds, and the processors cannot change its speed during the computation of a task. Our work is motivated by the practical variable voltage processors that they cannot run at arbitrary speed and the task may be failure if the processor adjusts its speed during the computation of the task. We assess the complexity of the problem and present a polynomial time approximation algorithm with a bounded factor related to the adjacent speed ratio.
KW - Restricted parallel processors scheduling
KW - approximation algorithm
KW - discrete speed model
KW - speed scaling
UR - http://www.scopus.com/inward/record.url?scp=84899717957&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2013.43
DO - 10.1109/IPDPSW.2013.43
M3 - Conference contribution
AN - SCOPUS:84899717957
SN - 9780769549798
T3 - Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013
SP - 2226
EP - 2229
BT - Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013
PB - IEEE Computer Society
T2 - 2013 IEEE 37th Annual Computer Software and Applications Conference, COMPSAC 2013
Y2 - 22 July 2013 through 26 July 2013
ER -