File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Scheduling for speed bounded processors

TitleScheduling for speed bounded processors
Authors
KeywordsLinguistics
Scheduling
Translation (languages)
Dynamic speed scaling
Maximum speed
Issue Date2008
PublisherSpringer 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, 6-13 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409-420 How to Cite?
AbstractWe 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 4-competitive 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 4-competitive even if the energy concern is ignored [7]. In the second problem, we consider optimizing the trade-off between the total flow time incurred and the energy consumed by the jobs. We give a 4-competitive 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 Springer-Verlag.
DescriptionLNCS v. 5125 is conference proceedings of ICALP 2008
Persistent Identifierhttp://hdl.handle.net/10722/125719
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.date.accessioned2010-10-31T11:47:55Z-
dc.date.available2010-10-31T11:47:55Z-
dc.date.issued2008en_HK
dc.identifier.citationThe 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 6-13 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409-420en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/125719-
dc.descriptionLNCS v. 5125 is conference proceedings of ICALP 2008-
dc.description.abstractWe 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 4-competitive 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 4-competitive even if the energy concern is ignored [7]. In the second problem, we consider optimizing the trade-off between the total flow time incurred and the energy consumed by the jobs. We give a 4-competitive 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 Springer-Verlag.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectLinguistics-
dc.subjectScheduling-
dc.subjectTranslation (languages)-
dc.subjectDynamic speed scaling-
dc.subjectMaximum speed-
dc.titleScheduling for speed bounded processorsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=5125&spage=409&epage=420&date=2008&atitle=Scheduling+for+speed+bounded+processors-
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-70575-8_34en_HK
dc.identifier.scopuseid_2-s2.0-49049100921en_HK
dc.identifier.hkuros181812en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-49049100921&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5125 LNCSen_HK
dc.identifier.issuePART 1en_HK
dc.identifier.spage409en_HK
dc.identifier.epage420en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 6-13 July 2008. In Lecture Notes in Computer Science, 2008, v. 5125, p. 409-420-
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats