File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783540705758_34
 Scopus: eid_2s2.049049100921
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Scheduling for speed bounded processors
Title  Scheduling for speed bounded processors 

Authors  
Keywords  Linguistics Scheduling Translation (languages) Dynamic speed scaling Maximum speed 
Issue Date  2008 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 613 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409420 How to Cite? 
Abstract  We consider online scheduling algorithms in the dynamic speed scaling model, where a processor can scale its speed between 0 and some maximum speed T. The processor uses energy at rate sα when run at speed s, where α > 1 is a constant. Most modern processors use dynamic speed scaling to manage their energy usage. This leads to the problem of designing execution strategies that are both energy efficient, and yet have almost optimum performance. We consider two problems in this model and give essentially optimum possible algorithms for them. In the first problem, jobs with arbitrary sizes and deadlines arrive online and the goal is to maximize the throughput, i.e. the total size of jobs completed successfully. We give an algorithm that is 4competitive for throughput and O(1)competitive for the energy used. This improves upon the 14 throughput competitive algorithm of Chan et al. [10]. Our throughput guarantee is optimal as any online algorithm must be at least 4competitive even if the energy concern is ignored [7]. In the second problem, we consider optimizing the tradeoff between the total flow time incurred and the energy consumed by the jobs. We give a 4competitive algorithm to minimize total flow time plus energy for unweighted unit size jobs, and a (2 + o(1)) α/ln αcompetitive algorithm to minimize fractional weighted flow time plus energy. Prior to our work, these guarantees were known only when the processor speed was unbounded (T = ∞ ) [4]. © 2008 SpringerVerlag. 
Description  LNCS v. 5125 is conference proceedings of ICALP 2008 
Persistent Identifier  http://hdl.handle.net/10722/125719 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Lam, TW  en_HK 
dc.contributor.author  Lee, LK  en_HK 
dc.date.accessioned  20101031T11:47:55Z   
dc.date.available  20101031T11:47:55Z   
dc.date.issued  2008  en_HK 
dc.identifier.citation  The 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 613 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409420  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/125719   
dc.description  LNCS v. 5125 is conference proceedings of ICALP 2008   
dc.description.abstract  We consider online scheduling algorithms in the dynamic speed scaling model, where a processor can scale its speed between 0 and some maximum speed T. The processor uses energy at rate sα when run at speed s, where α > 1 is a constant. Most modern processors use dynamic speed scaling to manage their energy usage. This leads to the problem of designing execution strategies that are both energy efficient, and yet have almost optimum performance. We consider two problems in this model and give essentially optimum possible algorithms for them. In the first problem, jobs with arbitrary sizes and deadlines arrive online and the goal is to maximize the throughput, i.e. the total size of jobs completed successfully. We give an algorithm that is 4competitive for throughput and O(1)competitive for the energy used. This improves upon the 14 throughput competitive algorithm of Chan et al. [10]. Our throughput guarantee is optimal as any online algorithm must be at least 4competitive even if the energy concern is ignored [7]. In the second problem, we consider optimizing the tradeoff between the total flow time incurred and the energy consumed by the jobs. We give a 4competitive algorithm to minimize total flow time plus energy for unweighted unit size jobs, and a (2 + o(1)) α/ln αcompetitive algorithm to minimize fractional weighted flow time plus energy. Prior to our work, these guarantees were known only when the processor speed was unbounded (T = ∞ ) [4]. © 2008 SpringerVerlag.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  Linguistics   
dc.subject  Scheduling   
dc.subject  Translation (languages)   
dc.subject  Dynamic speed scaling   
dc.subject  Maximum speed   
dc.title  Scheduling for speed bounded processors  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=03029743&volume=5125&spage=409&epage=420&date=2008&atitle=Scheduling+for+speed+bounded+processors   
dc.identifier.email  Chan, HL: hlchan@cs.hku.hk  en_HK 
dc.identifier.email  Lam, TW: hresltk@hkucc.hku.hk  en_HK 
dc.identifier.email  Lee, LK: lklee@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.identifier.authority  Lam, TW=rp00135  en_HK 
dc.identifier.authority  Lee, LK=rp00140  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783540705758_34  en_HK 
dc.identifier.scopus  eid_2s2.049049100921  en_HK 
dc.identifier.hkuros  181812  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.049049100921&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  5125 LNCS  en_HK 
dc.identifier.issue  PART 1  en_HK 
dc.identifier.spage  409  en_HK 
dc.identifier.epage  420  en_HK 
dc.publisher.place  Germany  en_HK 
dc.description.other  The 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 613 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409420   
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Lam, TW=7202523165  en_HK 
dc.identifier.scopusauthorid  Lee, LK=12646190100  en_HK 