The Complexity of Speed-Scaling

It seems to be a corollary to the laws of physics that, all else being equal, higher performance devices are necessarily less energy efficient than lower performance devices. Conceptually there is an energy efficiency spectrum of design points, with high performance and low energy efficiency on one end, and low performance and high energy efficiency on the other end. As in most technologies, there is not a universal sweet spot for computer chips that is best for all situations. For example, there are situations when there are critical tasks to be done, when performance is more important than energy efficiency, and there are situations when there are no critical tasks, when energy efficiency may be more important than performance. Speed-scalable processors aim to resolve this conflict by allowing the operating system to dynamically choose the performance to energy trade-off.\ud The resulting optimization problems involve scheduling jobs on such a processor and have conflicting dual objectives of quality of service and some energy related objective. This engenders many different optimization problems, depending on how one models the processor, the performance objective, and how one handles the dual objectives. \ud \ud In this thesis we map out a reasonably full landscape of all possible formulations, determining which assumptions drive computational tractability. Beyond identifying the individual computational complexities, we use algorithmics as a lens to study the combinatorial structure of such trade-off schedules. In particular, we give several general reductions which, in some sense, reduce the number of problems that are distinct in a complexity theoretic sense. We show that some problems, for which there are efficient algorithms on a fixed speed processor, are NP-hard. Finally, we present several primal-dual based polynomial time algorithms