Speed scaling problems with memory/cache consideration

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation
Subtitle of host publication9th Annual Conference, TAMC 2012, Proceedings
PublisherSpringer Verlag
Pages412-422
Volume7287 LNCS
ISBN (Print)9783642299513
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7287 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
PlaceChina
CityBeijing
Period16 - 21 May 2012

Abstract

We study the speed scaling problems with memory/cache consideration. Each job needs some time for its memory operation when it is fetched from the memory/cache. Two models are investigated, the non-cache model and the with-cache model. The objective is to minimize the energy consumption while satisfying the time constraints of the jobs. The non-cache model is a variant of the ideal model where each job i needs a fixed c i time for its memory operation. The with-cache model further considers the case that the cache (a memory device with much faster accessing time but limited space) is provided. The uniform with-cache model is a special case when all c i values are the same. We prove that the optimal solution of the non-cache model can be computed in polynomial time. For the with-cache model, we show that it is NP-complete to compute the optimal solution. For the aligned jobs (where later released jobs do not have earlier deadlines) in the uniform with-cache model, we derive an O(n 4) time algorithm to compute the optimal schedule. For the general jobs for with-cache model with resource augmentation where the memory operation time speeds up by at most s times, we propose a -(2αs/s-1)α/2-approximation algorithm. © 2012 Springer-Verlag.

Citation Format(s)

Speed scaling problems with memory/cache consideration. / Wu, Weiwei; Li, Minming; Huang, He; Chen, Enhong.

Theory and Applications of Models of Computation: 9th Annual Conference, TAMC 2012, Proceedings. Vol. 7287 LNCS Springer Verlag, 2012. p. 412-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)