edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Antonios Antoniadis
Titel: Scheduling algorithms for saving energy and balancing load
Gutachter: Susanne Albers; Christoph Dürr; Andrzej Lingas
Erscheinungsdatum: 16.08.2012
Volltext: pdf (urn:nbn:de:kobv:11-100203798)
Fachgebiet(e): Informatik
Schlagwörter (ger): Algorithmen, Plannung, Energieeffizient, Lastbalancierung, Average Rate, Optimal Available, speed-scaling, power-down, sleep-state, Intervalfärbung
Schlagwörter (eng): algorithm, scheduling, energy-efficient, load-balancing, Average Rate, Optimal Available, speed-scaling, power-down, sleep-state, interval coloring
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung - Keine Bearbeitung (CC BY NC ND)
Zitationshinweis: Antoniadis, Antonios: Scheduling algorithms for saving energy and balancing load; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 16.08.2012, urn:nbn:de:kobv:11-100203798
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Diese Arbeit beschäftigt sich mit Scheduling von Tasks in Computersystemen. Wir untersuchen sowohl die in neueren Arbeiten betrachtete Zielfunktion zur Energieminimierung als auch die klassische Zielfunktion zur Lastbalancierung auf mehreren Prozessoren. Beim Speed-Scaling mit Sleep-State darf ein Prozessor, der zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann, auch in einen Schlafmodus übergehen. Unser Ziel ist es, den Energieverbrauch zu minimieren. Wir zeigen die NP-Härte des Problems und klären somit den Komplexitätsstatus. Wir beweisen eine untere Schranke für die Approximationsgüte für eine spezielle natürliche Klasse von Schedules. Ferner entwickeln wir eine Familie von Algorithmen, die gute Approximationsfaktoren liefert, und zeigen, dass diese sogar Lösungen liefert, die optimal für die zuvor erwähnte Klasse von Schedules sind. Anschließend widmen wir unsere Aufmerksamkeit dem folgenden Termin-basierten Scheduling-Problem. Es seien mehrere Prozessoren gegeben, wobei jeder einzelne Prozessor zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann. Ziel ist es wie zuvor, den Energieverbrauch des erzeugten Schedules zu minimieren. Für den Offline-Fall entwickeln wir einen optimalen Polynomialzeit-Algorithmus. Für das Online-Problem erweitern wir die zwei bekannten Ein-Prozessor-Algorithmen Optimal Available und Average Rate. Wir zeigen, dass diese den gleichen bzw. einen um die additive Konstante von eins vergrößerten kompetiven Faktor haben. Bei der Lastbalancierung auf mehreren Prozessoren betrachten wir Offline-Load-Balancing auf identischen Maschinen. Unser Ziel ist es, die Current-Load für temporäre Tasks mit identischem Gewicht zu minimieren. Wir zeigen, dass eine Lösung mit maximaler Imbalance von eins immer existiert und entwickeln einen effizienten Algorithmus, der solche Lösungen liefert. Zum Schluss beweisen wir die NP-Härte von zwei Verallgemeinerungen des Problems.
Abstract (eng):
This thesis studies problems of scheduling tasks in computing environments. We consider both the modern objective function of minimizing energy consumption, and the classical objective of balancing load across machines. We first investigate offline deadline-based scheduling in the setting of a single variable-speed processor that is equipped with a sleep state. The objective is that of minimizing the total energy consumption. Apart from settling the complexity of the problem by showing its NP-hardness, we provide a lower bound of 2 for general convex power functions, and a particular natural class of schedules. We also present an algorithmic framework for designing good approximation algorithms. Furthermore, we give tight bounds for the aforementioned particular class of schedules. We then focus on the multiprocessor setting where each processor has the ability to vary its speed. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. Regarding the online problem and a natural class of power functions, we extend the two well-known single-processor algorithms Optimal Available and Average Rate. We prove that Optimal Available has the same competitive ratio as in the single-processor case. For Average Rate we show a competitive factor that increases by an additive constant of one compared to the single-processor result. With respect to load balancing, we consider offline load balancing on identical machines, with the objective of minimizing the current load, for temporary unit-weight jobs. The problem can be seen as coloring n intervals with k colors, such that for each point on the line, the maximal difference between the number of intervals of any two colors is minimal. We prove that a coloring with maximal difference at most one is always possible, and develop a fast polynomial-time algorithm for generating such a coloring. Lastly, we prove that two generalizations of the problem are NP-hard.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
PDF: 22 Zugriffe PDF: 30 Zugriffe PDF: 33 Zugriffe PDF: 12 Zugriffe Startseite: 13 Zugriffe PDF: 37 Zugriffe Startseite: 17 Zugriffe PDF: 45 Zugriffe Startseite: 8 Zugriffe PDF: 45 Zugriffe Startseite: 15 Zugriffe PDF: 34 Zugriffe Startseite: 13 Zugriffe PDF: 38 Zugriffe Startseite: 6 Zugriffe PDF: 34 Zugriffe Startseite: 12 Zugriffe PDF: 47 Zugriffe Startseite: 10 Zugriffe PDF: 50 Zugriffe Startseite: 5 Zugriffe PDF: 34 Zugriffe Startseite: 17 Zugriffe PDF: 30 Zugriffe Startseite: 10 Zugriffe PDF: 41 Zugriffe Startseite: 6 Zugriffe PDF: 34 Zugriffe Startseite: 5 Zugriffe PDF: 42 Zugriffe Startseite: 2 Zugriffe PDF: 46 Zugriffe Startseite: 1 Zugriffe PDF: 54 Zugriffe
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Monat Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Startseite         13 17 8 15 13 6 12 10 5 17 10 6 5 2 1
PDF 22 30 33 12 37 45 45 34 38 34 47 50 34 30 41 34 42 46 54

Gesamtzahl der Zugriffe seit Sep 2012:

  • Startseite – 140 (9.33 pro Monat)
  • PDF – 708 (37.26 pro Monat)
 
 
Generiert am 18.04.2014, 05:21:02