Scheduling for energy minimization on restricted parallel processors

doi:10.1016/j.jpdc.2015.04.001

	Scheduling for energy minimization on restricted parallel processors
	Jin, Xibo 1,4; Zhang, Fa 2; Fan, Liya 5; Song, Ying 3; Liu, Zhiyong 1,3
	2015-07-01
发表期刊	JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
ISSN	0743-7315
卷号	81-82 页码:36-46
摘要	Scheduling for energy conservation has become a major concern in the field of information technology because of the need to reduce energy use and carbon dioxide emissions. Previous work has focused on the assumption that a task can be assigned to any processor. In contrast, we initially study the problem of task scheduling on restricted parallel processors. The resfriction takes account of affinities between tasks and processors; that is, a task has its own eligible set of processors. We adopt the Speed Scaling (SS) method to save energy under an execution time constraint (on the makespan C-max), and the processors can run at arbitrary speeds in [s(min), s(max)]. Our objective is to minimize the overall energy consumption. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complex as it is proved to be NP-complete for general tasks. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial-time optimal scheduling algorithm for the case in which tasks have a uniform size. Our algorithm runs in O(mn(3) log n) time, where m is the number of processors and n is the number of tasks. We then present a polynomial-time algorithm that achieves a bounded approximation factor when the tasks have arbitrary-size work. Numerical results demonstrate that our algorithm could provide an energy-efficient solution to the problem of task scheduling on restricted parallel processors. (C) 2015 Elsevier Inc. All rights reserved.
关键词	Energy-efficient scheduling Restricted parallel processors Speed scaling Continuous speed model Approximation algorithm
DOI	10.1016/j.jpdc.2015.04.001
收录类别	SCI
语种	英语
资助项目	NSFC Major International Collaboration Project[61020106002] ; NSFC & Hong Kong RGC Joint Project[61161160566] ; NSFC Project for Innovation Groups[61221062] ; Comunidad de Madrid[S2009TIC-1692] ; Spanish MICINN/MINECO grant[TEC2011-29688-C02-01] ; NSFC[61202059]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000355962100004
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9707
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Jin, Xibo
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing Key Lab Mobile Comp & Pervas Device, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing, Peoples R China 4.Univ Chinese Acad Sci, Beijing, Peoples R China 5.IBM China Res Lab, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Jin, Xibo,Zhang, Fa,Fan, Liya,et al. Scheduling for energy minimization on restricted parallel processors[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING,2015,81-82:36-46.
APA	Jin, Xibo,Zhang, Fa,Fan, Liya,Song, Ying,&Liu, Zhiyong.(2015).Scheduling for energy minimization on restricted parallel processors.JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING,81-82,36-46.
MLA	Jin, Xibo,et al."Scheduling for energy minimization on restricted parallel processors".JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 81-82(2015):36-46.