loading...
Flow Time Minimization under Energy Constraints
Yokohama January 23-January 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ASPDAC.2007.3580982007 Asia and South Pacific Design Au ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jian-Jia Chen, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan. r900
Kazuo Iwama, School of Informatics, Kyoto University, Yoshida-Honmachi, Kyoto, Japan. iwama@kuis.kyoto-u.ac.jp
Tei-Wei Kuo, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan. ktw@
Hseuh-I Lu, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan. hil@
Power-aware and energy-efficient designs play important roles for modern hardware and software designs, especially for embedded systems. This paper targets a scheduling problem on a processor with the capability of dynamic voltage scaling (DVS), which could reduce the power consumption by slowing down the processor speed. The objective of the targeting problem is to minimize the average flow time of a set of jobs under a given energy constraint, where the flow time of a job is defined as the interval length between the arrival and the completion of the job. We consider two types of processors, which have a continuous spectrum of the available speeds or have only a finite number of discrete speeds. Two algorithms are given: (1) An algorithm is proposed to derive optimal solutions for processors with a continuous spectrum of the available speeds. (2) A greedy algorithm is designed for the derivation of optimal solutions for processors with a finite number of discrete speeds. The proposed algorithms are extended to cope with jobs with different weights for the minimization of the average weighted flow time. The proposed algorithms are also evaluated with comparisons to schedules which execute jobs at a common effective speed.
Citation:
Jian-Jia Chen, Kazuo Iwama, Tei-Wei Kuo, Hseuh-I Lu, "Flow Time Minimization under Energy Constraints," asp-dac, pp.866-871, 2007 Asia and South Pacific Design Automation Conference, 2007
Usage of this product signifies your acceptance of the Terms of Use.