Energieeffiziente Algorithmen

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Motivation

Energiekosten sind ein Hauptkostenpunkt bei der Nutzung vieler Computersysteme. Betreiber großer Serverfarmen verbrauchen tausende Gigawattstunden an elektrischer Energie. Die dabei entstehende Hitze muss abgeleitet werden, damit Hardware auf Betriebstemperatur bleibt und keine Schäden davon trägt. Energieeinsparungen führen direkt zu weniger Wärmeentwicklung und weniger Kosten.

In mobilen Systemen wie Laptops, Smartphones und vielen Bluetoothsystemen ist die Verfügbarkeit von elektrischer Energie begrenzt. Batterien haben nur begrenzte Speicherkapazität, sodass Energieeinsparung zu längeren Nutzungsdauern dieser Systeme führt.

Geschichte

• Das 1961 von Rolf Landauer formulierte Landauer-Prinzip liefert eine theoretische Untergrenze für den Energieverbrauch von irreversibel arbeitenden Computern.

• 1992 hat die United States Environmental Protection Agency das Energy Star Umweltzeichen für energiesparende Geräte eingeführt, das zu einer Verbreitung von Standby-Modi geführt hat.

• 2017 hat die EU den Energieverbrauch von vernetzten Geräten auf 3 bis 12 Watt im Standbymodus begrenzt.

Techniken

Power-down Strategien

Die meisten Systeme haben Energiespar- oder Standby-Modi. Der Energieverbrauch ist in diesen Modi geringer als im aktiven Betriebsmodus. Jedes System sollte bei Inaktivität in einen solchen Modus wechseln. Allerdings ist der Wechsel in den aktiven Betriebsmodus mit zusätzlichen Energieverbrauch gekoppelt. Die Frage, wann ein System bei unbekannter Länge der Inaktivität in Energiesparmodus wechseln sollte, lässt sich mit Online-Algorithmen lösen. O.B.d.A. kann man das Problem bei einem System mit zwei Modi wie folgt beschreiben.

Systeme mit zwei Modi

Im aktiven Betriebsmodus ist der Energieverbrauch $1{\tfrac {Energieeinheit}{Zeiteinheit}}$. Im Energiesparmodus ist der Energieverbrauch $0$. Der Energieverbrauch des Wechsels in den Betriebsmodus sei $\beta$. Der Energieverbrauch in den Energiesparmodus kann in der Regel vernachlässigt werden oder zum Wert $\beta$ addiert werden.

Eine kompetitive Analyse zeigt, dass der beste deterministische Algorithmus für das Problem immer dann in den Energiesparmodus wechselt wenn die Inaktivität β Zeiteinheiten andauert. Dieser Algorithmus hat im schlimmsten Fall den doppelten Energieverbrauch im Vergleich zu einem optimalen Algorithmus.

Das Problem lässt sich auf das Ski-Rental-Problem reduzieren und analog dazu untersuchen.

Systeme mit mehreren Modi

Für Systeme mit mehreren Energiespar-Modi lassen sich auch Online-Algorithmen nutzen, um den Energieverbrauch zu senken. Seien $m_{1},m_{2},...,m_{l}$die Betriebsmodi eines Systems mit $l$Modi. $r_{i}$sei der Energieverbrauch im Modus $m_{i}$. Die Modi werden so nummeriert, dass $r_{1}>r_{2}>...>r_{l}$gilt. $\beta _{i}$ist der Energiebedarf, um vom Modus $m_{i}$in den Betriebsmodus $m_{1}$zu wechseln. Irani et al. haben gezeigt, dass der Energieverbrauch eines optimalen Offline-Algorithmus für eine inaktive Phase der Länge $T$wie folgt ist

• $OPT(T)={\underset {1\leq i\leq l}{\min }}(r_{i}T+\beta _{i})$

Ein Online-Algorithmus der zu jeder jedem Zeitpunkt $t$einer inaktiven Phase den Modus $M_{OPT}(t)$wählt ist 2-kompetitiv.

Speed scaling

Aktuelle Mikroprozessoren lassen sich mit verschiedenen Geschwindigkeiten betreiben. Der Energieverbrauch steigt mit steigender Geschwindigkeit. Durch Drosselung der Geschwindigkeit lässt sich demnach Energie einsparen, allerdings zum Preis der geringeren Performance. Zu entscheiden, wann welcher Prozess mit welcher Prozessorgeschwindigkeit ausgeführt wird ist Aufgabe des Prozess-Schedulers. Abhängig vom Kontext gibt es eine Reihe von Algorithmen mit dem Ziel, den Energieverbrauch des Systems möglichst gering zu halten.

Benchmark

JouleSort wurde 2007 von Suzanne Rivoire, Mehul A-Shah, Parthasarathy Ranganathan und Christos Kozyrakis als Benchmark für energieeffiziente Computersysteme vorgeschlagen.

Die Aufgabe ist es, eine bestimmte Anzahl an 100-Byte Daten mit 10-Byte Schlüsseln zu sortieren. Geladen und gespeichert werden die Daten auf permanenten Speichermedien. Die Gesamtzahl der zu sortierenden Daten liegen bei 10⁸ (~ 10 GB), 10⁹ (~ 100 GB), 10¹⁰ (~ 1 TB) und 10¹² (~ 100 TB). Gewinner ist das System, das für das Sortieren den geringsten Gesamtenergiebedarf hat.

JouleSort konzentriert sich aufgrund der großen Datenmengen auf Ein- und Ausgaben auf einen nichtflüchtigen Speicher bei system Höchstauslastung. Hier zeigt sich deutlich der geringere Energiebedarf von Flash-Speichern im Gegensatz zu Festplatten.