Speed scaling problems with memory/cache consideration

Weiwei Wu (), Minming Li (), Kai Wang (), He Huang () and Enhong Chen ()
Additional contact information
Weiwei Wu: Southeast University
Minming Li: City University of Hong Kong
Kai Wang: City University of Hong Kong
He Huang: Soochow University
Enhong Chen: University of Science and Technology of China

Journal of Scheduling, 2018, vol. 21, issue 6, No 7, 633-646

Abstract: Abstract Speed scaling problems consider energy-efficient job scheduling in processors by adjusting the speed to reduce energy consumption, where power consumption is a convex function of speed (usually, $$P(s) =s^{\alpha }, \alpha =2,3$$ P ( s ) = s α , α = 2 , 3 ). In this work, we study speed scaling problems considering memory/cache. Each job needs some time for memory operation when it is fetched from memory,, and needs less time if fetched from the cache. The objective is to minimize energy consumption while satisfying the time constraints of the jobs. Two models are investigated, the non-cache model and the with-cache model. The non-cache model is a variant of the ideal model, where each job i needs a fixed $$c_i$$ c i time for its memory operation; the with-cache model further considers the cache, a memory device with much faster access time but limited space. The uniform with-cache model is a special case of the with-cache model in which all $$c_i$$ c i values are the same. We provide an $$O(n^3)$$ O ( n 3 ) time algorithm and an improved $$O(n^2\log n)$$ O ( n 2 log n ) time algorithm to compute the optimal solution in the non-cache model. For the with-cache model, we prove that it is NP-complete to compute the optimal solution. For the uniform with-cache model with agreeable jobs (later-released jobs do not have earlier deadlines), we derive an $$O(n^4)$$ O ( n 4 ) time algorithm to compute the optimal schedule, while for the general case we propose a $$(2\alpha \frac{g}{g-1})^{\alpha }/2$$ ( 2 α g g - 1 ) α / 2 -approximation algorithm in a resource augmentation setting in which the memory operation time can accelerate by at most g times.

Keywords: Speed scaling; Energy efficiency; Scheduling; Memory operation time; DVS; Algorithm design (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0565-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:6:d:10.1007_s10951-018-0565-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0565-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().