This paper addresses algorithms for dynamically scaling CPU speed and voltage in order to save energy. Such scaling is useful and effective when the user will perceive the same performance, despite a slower CPU, as long as the task completes by some (soft) deadline. We show that it is possible to modify any scaling algorithm to minimize energy use without affecting perceived performance, and present a formula to do so. Because this formula specifies increased speed as the task progresses, we call this approach PACE (Processor Acceleration to Conserve Energy). This optimal formula depends on the probability distribution of the task's work requirement and requires that the speed be varied continuously. We therefore present methods for estimating the task work distribution and evaluate how effective they are on a variety of real workloads. We also show how to approximate the optimal continuous schedule with one that changes speed a limited number of times. Using these methods, we find we can apply PACE practically and efficiently. Furthermore, PACE is extremely effective: simulations using real workloads show that PACE can reduce the CPU energy consumption of classic algorithms by up to 49.5%, with an average of 20.6%, without any effect on perceived performance.