Speed Scaling for Weighted Flow
Co-authorsNikhil Bansal and Clifford Stein
Intel's SpeedStep and AMD's PowerNOW technologies allow the the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed to run that job at. These policies must be online since the operating system does not in general have any knowledge about any jobs that may arrive in the future. We give an O(1)-competitive algorithm for weighted flow time. This result is a big step forward in terms of understanding speeding scaling in problems with flow objectives.