中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Scheduling for energy minimization on restricted parallel processors

文献类型：期刊论文

作者Jin, Xibo3,4; Zhang, Fa5; Fan, Liya2; Song, Ying1; Liu, Zhiyong1,4
刊名JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
出版日期2015-07-01
卷号81-82页码:36-46
关键词Energy-efficient scheduling Restricted parallel processors Speed scaling Continuous speed model Approximation algorithm
ISSN号0743-7315
DOI10.1016/j.jpdc.2015.04.001
英文摘要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.
资助项目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记录号WOS:000355962100004
出版者ACADEMIC PRESS INC ELSEVIER SCIENCE
源URL[http://119.78.100.204/handle/2XEOYT63/9706]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Jin, Xibo
作者单位1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing, Peoples R China
2.IBM China Res Lab, Beijing, Peoples R China
3.Univ Chinese Acad Sci, Beijing, Peoples R China
4.Chinese Acad Sci, Inst Comp Technol, Beijing Key Lab Mobile Comp & Pervas Device, Beijing, Peoples R China
5.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, 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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。