Scheduling for speed bounded processors
LNCS v. 5125 is conference proceedings of ICALP 2008 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 mod...
| Main Authors: | , , , |
|---|---|
| Format: | Conference Object |
| Language: | English |
| Published: |
Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
2008
|
| Subjects: | |
| Online Access: | https://doi.org/10.1007/978-3-540-70575-8_34 http://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 http://hdl.handle.net/10722/125719 |
| Summary: | LNCS v. 5125 is conference proceedings of ICALP 2008 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 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. link_to_subscribed_fulltext 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 |
|---|