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

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

Algorithmen

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.

Hardware

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

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

Speed Scaling

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.

Power-down Strategien

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.

Reversible Algorithmen

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

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.

Literatur

• 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

• Forschungsprojekt „Algorithmen für Energieeffiziente Berechnungen“ der DFG