Energieeffiziente Algorithmen
Energieeffiziente Algorithmen sind ein Forschungsgebiet der theoretischen Informatik, welches sich mit der Minimierung der benötigten Energie zur Durchführung komplexer Berechnungen befasst.
Ursprüngliches Forschungsobjekt war die Optimierung von Algorithmen hinsichtlich der Ausnutzung vorhandener Energiesparfunktionen in Mikrochips. Da moderne Mikroprozessorarchitekturen zunehmend an physikalische Grenzen hinsichtlich der Größe von Transistoren und ihrer Schaltgeschwindigkeit stoßen, trat in den letzten Jahre die Erforschung technisch-physikalischer Grundlagen hinzu, welche der Optimierung von Schaltkreisen für wichtige Instruktionen Grenzen setzen.
Ersteres Teilgebiet greift tief in die praktische Informatik hinein, während letzteres eng mit der technischen Informatik verbunden ist. Die Zuordnung zur Theoretischen Informatik entspringt der Entwicklung aus der Algorithmik.
Hintergrund und Motivation Bearbeiten
Der Energieverbrauch von Mikroprozessoren stellt seit Erfindung des modernen Computers einen limitierenden Faktor für dessen Leitungsfähigkeit dar. Einerseits, weil die benötigte Energiemenge verfügbar sein muss, andererseits weil die Hitzeentwicklung die praktische Einsetzbarkeit einschränkt und im Extremfall zur Zerstörung des Geräts führen kann. Bis kurz vor Ende des 20. Jahrhunderts war dies jedoch kein strukturelles Problem, da Computer fast ausschließlich in Situationen eingesetzt wurden, in denen die Kühlung und Energieversorgung keine große Herausforderung darstellten.
Mit der Verbreitung mobiler Computer, welche ihre Energie aus Akkus bezogen und aufgrund ihres Formfaktors auf große Kühlkörper verzichten mussten, wurde Energieeffizienz wieder zu einem relevanten Thema. Handys und Smartphones stellen noch strengere Anforderungen an den Energieverbrauch und werden überhaupt nicht mehr aktiv gekühlt. Auch das ab den 1990er-Jahren rasant wachsende Feld von Embedded-Systemen in Haushaltsgeräten, Fahrzeugen und anderen Gegenständen des täglichen Bedarfs wäre ohne sparsame Mikrocontroller nicht denkbar.
Bis Anfang der 2010er Jahre erreichten Verbesserungen im Softwaredesign sowie Fortschritte in der Fertigung und Selbstregulierung von Mikroprozessoren die notwendigen Effizienzsteigerungen, um die geforderte Rechenleistung bei geringem Energieverbrauch zur Verfügung zu stellen. Mittlerweile sind Mikroprozessoren jedoch derartig verbreitet, dass ihr Betrieb einen relevanten Anteil des Gesamtenergieverbrauchs der Menschheit ausmacht. Neben der Vielzahl von Endgeräten spielen hierbei insbesondere die globale Infrastruktur des Internets sowie Supercomputer zu Forschungszwecken und andere Hochleistungsrechenzentren eine Rolle.
Da zudem absehbar physikalische Grenzen bei der Entwicklung der Mikroprozessoren erreicht werden, rückte die Optimierung auf Seiten der Software und insbesondere auf Ebene der Algorithmen wieder in den Fokus.
Herausforderungen Bearbeiten
Algorithmen Bearbeiten
Ein großer Teil der weltweiten Rechenleistung wird in Echtzeitsystemen verwendet, die auf Nutzereingaben und andere externe Anforderungen reagieren. Ihre Bedürfnisse hinsichtlich Rechenleistung sind schlecht planbar, sodass mit probabilistischen Modellen gearbeitet wird. Da in vielen Fällen eine Bearbeitung binnen eines gewissen Zeitraums erforderlich ist (zum Beispiel bei der Auswertung von Sensordaten in Fahrzeugen oder medizinischen Geräten), lassen sich Leistungsspitzen und der damit verbundene Energieverbrauch nur bedingt vermeiden.
Große Rechenzentren stellen andere Anforderungen, vor allem hinsichtlich der Vorhersagbarkeit der Dauer von Berechnungen. Die Geschwindigkeit paralleler Berechnungen hängt maßgeblich von Flaschenhälsen ab, wenn also auf die Ergebnisse vorhergehender Berechnungsschritte gewartet werden muss.
Beide Felder sind den Scheduling-Problemen zuzuordnen und darin im Speziellen den Online-Algorithmen.[1]
Hardware Bearbeiten
Moderne Mikroprozessoren verfügen über viele Methoden, welche im Mittel eine Verbesserung der Ausführungsgeschwindigkeit mit sich bringen, dabei jedoch zu Schwankungen in der Ausführungsgeschwindigkeit führen, welche bei Scheduling-Problemen besonders problematisch sind. Dies betrifft insbesondere Sprungvorhersagen, welche ein System nicht-deterministisch machen. Falsche Vorhersage ziehen enorme Wartezeiten nach sich, weil Informationen aus langsameren Ebenen der Speicherhierarchie nachgeladen werden müssen.
Physik Bearbeiten
Das bereits 1961 formulierte Landauer-Prinzip liefert eine theoretische Untergrenze für den Energieverbrauch irreversibel arbeitender Computer. Sollten Mikroprozessoren jemals in die Nähe dieser Grenze kommen, sind außer durch vollständige Umstellung der Computer- und Softwarearchitektur auf reversible Systeme (welche Informationen nicht verwerfen, sodass Operationen rückgängig gemacht werden können), sowie die Anpassung von Algorithmen daran, kaum mehr nennenswerte Effizienzsteigerungen zu erwarten.
Strategien Bearbeiten
Speed Scaling Bearbeiten
Moderne Mikroprozessoren können mit unterschiedlich hohen Taktfrequenzen betrieben werden. Bei niedrigerer Taktung wird eine geringere elektrische Spannung benötigt, welche quadratisch in den Energieverbrauch einfließt. Es ist daher wünschenswert, Berechnungen mit möglichst gleichmäßiger Auslastung durchzuführen, da kurze Leistungsspitzen den Gesamtenergieverbrauch unnötig in die Höhe treiben. Andersherum senkt die korrekte Priorisierung von Prozessen den Energieverbrauch.[2]
Power-down Strategien Bearbeiten
Neben der Reduzierung der Taktfrequenz können die meisten Systeme auch ganz oder teilweise in Energiespar- oder Standby-Modi treten, in welchen sie weniger Energie verbrauchen, dabei jedoch auch eine deutlich reduzierte Leistung bieten oder gar „wieder aufgeweckt“ werden müssen, bevor sie Berechnungen durchführen können. Ein Wechsel zwischen den Modi verbraucht jedoch ebenfalls Energie. Ein verfrühter Wechsel in einen sparsameren Modus würde den Energieverbrauch daher insgesamt sogar erhöhen, wenn dieser wieder revertiert werden muss, bevor seine Kosten amortisiert wurden.
Dies auszunutzen stellt große Herausforderungen an die Organisation paralleler Systeme. Mittlerweile wurden angepassten Algorithmen gefunden, mit denen selbst im schlechtesten Fall nur doppelt so viel Energie verbraucht wird, wie eigentlich benötigt worden wäre.[3]
Reversible Algorithmen Bearbeiten
Die Erforschung reversibler Algorithmen steckt aufgrund der vernachlässigenswerten Verbreitung solcher Systeme noch ein Nischenthema dar. Erste Versuche und Modellierungen zeigten jedoch erfolgversprechende Ergebnisse.
Benchmark Bearbeiten
2007 wurde JouleSort als Benchmark für energieeffiziente Computersysteme vorgeschlagen. 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 Gesamtmenge der zu sortierenden Daten liegt zwischen etwa 10 GB und etwa 100 TB.[4]
Literatur Bearbeiten
- F.F. Yao. A.J. Demers, S. Shenker: A scheduling model for reduced CPU energy. In: Proc. 36th IEEE Symposium on Foundations of Computer Science. S. 374–382. 1995.
- Susanne Albers: Energy-Efficient Algorithms. In: Communications of the ACM, Band 53, Nummer 5, 2011. S. 88–96.
- Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi: Energy-Efficient Algorithms. MIT Computer Science and Artificial Intelligence Laboratory, Cambridge 30. Mai 2016 (englisch, arxiv.org [PDF; 539 kB; abgerufen am 4. September 2023]).
- Sandy Irani, Kirk Pruhs: Algorithmic problems in power management. In: SIGACT News, Band 36, Nummer 2, 2005. S. 63–76.
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- ↑ Thorsten Zitterell: Energieeffiziente Schedulingalgorithmen für Echtzeitsysteme. Institut für Informatik, Albert-Ludwigs-Universität Freiburg, Freiburg 3. November 2011 (d-nb.info [PDF; 1,2 MB; abgerufen am 5. September 2023]).
- ↑ Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott: A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State. 3. Juli 2014 (englisch, arxiv.org [PDF; 395 kB; abgerufen am 5. September 2023]).
- ↑ Sandy Irani, Sandeep Shukla, Rajesh Gupta: Online Strategies for Dynamic Power Management in Systems with Multiple Power-Saving States. In: ACM Transactions on Embedded Computing Systems. Band 2, Nr. 3, August 2003, S. 325–346 (psu.edu [PDF; 210 kB; abgerufen am 5. September 2023]).
- ↑ Suzanne Rivoire, Mehul A. Shah, Parthasarathy Ranganathan, Christos Kozyrakis: JouleSort: A Balanced Energy-Efficiency Benchmark. Juli 2007 (englisch, stanford.edu [PDF; 175 kB; abgerufen am 5. September 2023]).