Energy-efficient scheduling algorithms

Titelaufnahme

Links

Dateien

Klassifikation

Zusammenfassung

Diese Dissertation beschäftigt sich mit dem Entwurf und der Analyse energieeffizienter Schedulingalgorithmen, insbesondere für sogenannte Speed-Scaling Modelle. Diese stellen das theoretische Pendant zu Techniken wie AMDs PowerNOW! und Intels SpeedStep dar, welche es erlauben die Geschwindigkeit von Prozessoren zur Laufzeit an die derzeitigen Bedingungen anzupassen. Theoretische Untersuchungen solcher Modelle sind auf eine Arbeit von Yao, Demers und Shenker [FOCS:1995] zurückzuführen. Hier kombinieren die Autoren klassisches Deadline-Scheduling mit einem Prozessor der Speed-Scaling beherrscht. Es gilt Jobs verschiedener Größe fristgerecht abzuarbeiten und die dabei verwendete Energie zu minimieren. Der Energieverbrauch des Prozessors wird durch eine konvexe Funktion $P:\mathbb

Abstract

This thesis studies the design and quality of energy-efficient scheduling algorithms, especially with respect to speed scaling. Speed scaling finds practical application in techniques like Intel's SpeedStep and AMD's PowerNOW, which allow a processor to change its speed during runtime. This way, it may use low, energy-efficient speeds during the majority of time and only enter a less energy-efficient mode when the workload becomes too high to guarantee a sufficient quality of service. Theoretical investigations of such models were initiated by Yao, Demers, and Shenker [FOCS:1995]. They combined deadline scheduling with speed scaling, striving to schedule all jobs while minimizing the total energy consumption.The results presented in this thesis align with the rich body of literature on variants of this model. The main results are presented in four parts (Chapters 3 to 6). Parts one and two study different price-collecting variants of the original problem, where the scheduler may miss deadlines if it pays a job-specific penalty. Part three replaces the deadline constraints by the flow time objective. The last part introduces a new type of resource constrained scheduling. While it does not directly consider energy, it might be a first step towards a theoretical model where the energy source is shared between several processors.

Inhalt

Statistik

Lizenz-/Rechtehinweis