Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
ger: 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{R}_{\geq0}\to\mathbb{R}_{\geq0}$ modelliert, welche die Geschwindigkeit auf den Energieverbrauch abbildet. Die vorliegende Arbeit betrachtet verschiedene Varianten des ursprünglichen Speed-Scaling Modells. Forschungsrelevante Ergebnisse sind in den Kapiteln 3 bis 6 zu finden und erstrecken sich über die im Folgenden beschriebenen Aspekte: (a) Kapitel 3 und 4 betrachten verschiedene Price-Collecting Varianten des Originalproblems. Hier dürfen einzelne Deadlines verfehlt werden, sofern eine jobabhängige Strafe gezahlt wird. (b) In Kapitel 5 wird statt des klassischen Deadline-Schedulings eine Linearkombination der durchschnittlichen Antwortzeit und des Energieverbrauchs betrachtet. (c) Das letzte Kapitel betrachtet ein Resource-Constrained Scheduling Modell, in dem sich die Prozessoren zusammen eine gemeinsame, beliebig aufteilbare Ressource teilen.
eng: 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.