Lexikon

Approximate Computing

Motivation

Approximate Computing (AC) ist ein neu entstehendes Entwurfsparadigma für Rechnersysteme. Mittels AC sollen Rechnersysteme energieeffizienter,  schneller und auch kleiner werden. Während eine minimierte Größe für mobile Geräte wichtig ist, wie zum Beispiel für Mobiltelefone oder drahtlose Sensoren, haben eine hohe Energieeffizienz und kurze Laufzeiten große Bedeutung für viele Rechnerkategorien, von batteriebetriebenen Geräten bis hin zu Servern, die riesige Datenmengen verarbeiten müssen.

Die Grundidee von AC ist es, den Anspruch an die Genauigkeit von Berechnungen zugunsten einer signifikanten Reduktion der Leistungsaufnahme und/oder der Laufzeit und/oder einer kleineren Chipfläche aufzugeben. Dieser Ansatz ist valide, da für viele Anwendungen ungefähre Resultate "gut genug" sind. Beispiele findet man insbesondere in der Audio-, Bild- und Videoverarbeitung sowie im Data Mining.

Das Neue an AC ist die Betrachtung aller Ebenen von Rechnersystemen, das heißt man setzt nicht nur an der Anwendungs- und Algorithmenebene an, sondern auch an den Ebenen der Programmiersprachen, Compiler, Betriebssysteme, Mikroarchitekturen und der Schaltkreise. Die zunehmenden Forschungsaktivitäten im Bereich AC umfassen Arbeiten zu all diesen Ebenen und manchmal sogar zu einer Kombination mehrerer Ebenen.

Der Nutzen und das Potential von AC lässt sich gut anhand der Arbeit „IMPACT: Imprecise adders for low-power approximate computing“ von Gupta et al. [1] zeigen, welche als eine der ersten Veröffentlichungen AC als eigenes Forschungsfeld postuliert hat. In dieser Arbeit werden Addiererschaltungen auf der Transistorebene so vereinfacht, dass sie im Vergleich zu einer exakten Implementierung wesentlich weniger Energie und Chipfläche benötigen. Die approximativen Arithmetikschaltungen werden dabei so entworfen, dass sich die Approximationsfehler nur in den niederwertigen Bits niederschlagen. Zur Bewertung werden die Addierer in den DCT und IDCT (Diskrete Cosinus-Transformation) Einheiten einer Hardwareumsetzung des JPEG Bildkompressionsverfahrens integriert. Dabei wurde gezeigt, dass nur unwesentliche – als Peak Signal to Noise Ratio (PSNR) messbare, aber optisch nicht wahrnehmbare – Qualitätseinbußen im Vergleich zu einer exakten Implementierung auftreten. Als Vergleich mit einer konventionellen Bitbreitenoptimierung wurde zusätzlich die Implementierung der DCT/IDCT Einheiten mit exakter Arithmetik aber reduzierter Bitbreite betrachtet. Diese Implementierungsalternative erzielt zwar vergleichbare Flächen- und Energieeinsparungen, führt aber zu einem wesentlich schlechteren PSNR und störenden visuellen Artefakten. Ein optischer Vergleich der exakten, bitbreitenreduzierten und approximierten Implementierungen ist in Abbildung 1 dargestellt. Gegenüber der exakten Lösung spart die approximierte Lösung 53% an elektrischer Leistung und 33% an Chipfläche.

Im Folgenden beschreiben wir die Entwicklung von AC und stellen die Unterschiede zu bzw. Gemeinsamkeiten mit verwandten Gebieten dar. Danach gehen wir auf den Entwurf von AC Systemen anhand ausgewählter Arbeiten ein und schließen mit einem Ausblick und einer Diskussion aktueller Forschungsfragen.

Entwicklung des Gebietes & Abgrenzung

Forschungsaktivitäten unter dem Schlagwort "Approximate Computing" sind relativ neu. Nach vereinzelten Veröffentlichungen in den letzten Jahren formt sich gerade erst eine internationale wissenschaftliche Gemeinschaft für dieses Gebiet. So fand dieses Jahr der zweite Workshop zum Thema AC an der angesehenen ASPLOS Konferenz statt und auch im Rahmen der jährlichen Konferenz des EU Exzellenznetzwerkes HiPEAC wurde dieses Jahr der erste AC Workshop durchgeführt.

Wie bei jedem neuen Gebiet ist auch die wissenschaftliche Gemeinschaft in AC derzeit bemüht, sich in die existierende Forschungslandschaft einzuordnen. Fasst man den Begriff "Approximation" nur weit genug, kann man in der Tat viele bekannte Techniken und Ansätze diskutieren:

Auf der Ebene der Hardware ist die Quantisierung, die Grundlage der Verarbeitung kontinuierlicher Werte durch digitale Rechnersysteme mit endlicher Präzision, eine häufig verwendete Form einer deterministischen Approximation. Die Modellierung von Quantisierung und Rundungseffekten ist hinreichend untersucht und verstanden und wird zum Beispiel im VLSI-Entwurf für digitale Signalverarbeitungssysteme seit langem zur Ressourcenminimierung ausgenutzt. Die Präzision der Datentypen wird gerade so groß gewählt, dass vorgegebene Quantisierungsfehler nicht überschritten werden. Ein weiterer Ansatz ist die Verwendung von Funktionswerttabellen, die vorberechnete, approximierte Werte für aufwändig zu berechnende Funktionen abbilden.

Neben deterministischen Methoden existieren auch stochastische Ansätze der Approximation. Im Stochastic Computing werden Zahlen durch Bitströme repräsentiert, wobei sich der Zahlenwert beispielsweise durch die Wahrscheinlichkeit, eine 1 in dem Bitstrom zu lesen, darstellt. Dieser Ansatz führt zwar zu sehr einfachen, energieeffizienten Rechenwerken und besitzt eine inhärente Fehlertoleranz, leidet aber an sehr langen Berechnungszeiten und geringen praktisch erreichbaren Genauigkeiten. Im Probabilistic Computing wird das Verhalten von Schaltungskomponenten zum Beispiel unter thermischem Rauschen oder bei einer Reduktion der Versorgungsspannung als stochastischer Prozess modelliert. 

Auf der Ebene der Algorithmen ist das intensiv untersuchte Gebiet der Approximationsalgorithmen zu nennen. Hier versucht man Lösungen für schwere Probleme zu finden und dabei beweisbaren Schranken für die Lösungsqualität und die Laufzeit zu garantieren. Ebenso arbeiten viele Verfahren der Audio-, Bild- und Videoverarbeitung approximativ, weil sie aus Effizienzgründen die Genauigkeit an die Grenzen menschlicher Wahrnehmung anpassen. Eine spezielle Form der Approximation gibt es bei den Anytime-Algorithmen, die Lösungen iterativ verbessern, dabei aber jederzeit gestoppt werden können.

Der Anspruch des AC als neues Forschungsgebiet ergibt sich aus der Betrachtung approximativ arbeitender Hardware in Verbindung mit anderen Schichten von Rechnersystemen. Insofern könnte man AC von den existierenden Ansätzen der Approximation auf der Algorithmenebene oder dem Stochastic Computing abgrenzen, da alle diese Verfahren auf klassischen Rechnern mit exakt arbeitender Hardware ausgeführt werden. Ein wesentlicher Punkt bei AC ist, dass die Ungenauigkeit absichtlich herbeigeführt wird, um eine Optimierung bezüglich der Energieeffizienz, Ausführungszeit und der Formfaktoren zu erreichen. Obwohl es Querverbindungen und manche methodische Ähnlichkeiten gibt, steht dies im Gegensatz zu Ansätzen wie dem Probabilistic Computing oder zu Forschungen zur Zuverlässigkeit nanoelektronischer Technologien, bei denen es primär darum geht, existierende Abstraktionen der Rechnersysteme trotz der in Zukunft unvermeidlichen Ungenauigkeiten oder Unzuverlässigkeiten der Hardware aufrecht zu erhalten.

Entwurf von AC Systemen

Im Folgenden diskutieren wir den Entwurf von AC Systemen anhand dreier Beispiele.

Esmaeilzadeh et al. [2] präsentieren einen Ansatz, bei dem rechenintensive  Funktionen von Anwendungen durch die Auswertung eines künstlichen neuronalen Netzes ersetzt werden. Dazu identifiziert der Entwickler im Quellcode approximierbare Funktionen und markiert diese mit Compilerdirektiven. Der Compiler modifiziert darauf hin das Originalprogramm so, dass während der Ausführung Traces der Ein- und Ausgaben der Funktion erzeugt werden, welche dann zum Training des neuronalen Netzes dienen. Nach dem Training ersetzt ein Aufruf des neuronalen Netzes die ursprüngliche Funktion. Neben dem Compiler stellen die Autoren auch eine CPU Architektur vor, welche über einen Hardwarebeschleuniger für neuronale Netze verfügt. Für eine Auswahl von sechs Benchmark-Kernels aus den Bereichen Bildverarbeitung und maschinellem Lernen konnten die Autoren eine durchschnittliche Beschleunigung um den Faktor zwei und eine Reduktion der benötigten Energie um den Faktor drei erreichen, bei Inkaufnahme eines Approximationsfehlers von 3,4%–9,6%.

Die Arbeit von Venkataramani et al. [3] setzt auf der Schaltungsebene an und untersucht die Frage, wie digitale Schaltungen systematisch vereinfacht werden können, so dass eine gegebene Fehlerschranke nicht verletzt wird. Der verfolgte Ansatz identifiziert Signale in einer Schaltung, die stets ähnliche Werte annehmen, um dann alle diese Signale durch nur eines zu ersetzen. Dies kann zu teilweise großen Einsparungen in der benötigten Logik führen. 

Eine Auswertung mit Schaltkreisen des ISCAS Benchmarks zeigt, dass bei Inkaufnahme eines Fehlers von lediglich 0,5% eine Reduktion von 15%-25% in der benötigten Fläche und von 10%-28% in der benötigten Energie erreicht werden kann.

Die Arbeit von Klavik et al. [4] untersucht, wie Approximationen im Bereich des wissenschaftlichen Rechnens genutzt werden können, ohne dass damit ein Verlust der Genauigkeit des Endresultates verbunden ist. Dazu betrachten die Autoren die iterative Lösung eines linearen Gleichungssystems nach der conjugate gradients Methode. Der Ansatz formuliert die Lösung des Gleichungssystems als “iterative refinement”, wobei es in jeder Iteration zwei Operationen gibt. Erst werden numerisch aufwändig, aber mit niedriger Präzision die Fehlervektoren berechnet; dann werden numerisch weniger aufwändig, dafür mit hoher Präzision die Residuen berechnet, deren Genauigkeit über die Konvergenz des Verfahrens und den Fehler der Lösung bestimmt. Die Autoren zeigen, dass zwar im Vergleich zur klassischen Lösung mit durchgehend hoher Präzision bis zur Konvergenz mehr Iterationen notwendig sind, netto aber ein erheblicher Gewinn in Laufzeit und Energie von Faktor 4-5 erreicht wird. Eine weitere algorithmische Verbesserung des Verfahrens für Bandmatrizen steigert den Gewinn in Laufzeit und Energie auf den Faktor 10-60, abhängig von der Matrixstruktur. 

Aktuelle Forschungsfragen und Ausblick

Bisher wurden vor allem isolierte Ansätze im Bereich des AC vorgestellt, und nur wenige Arbeiten beschäftigen sich überhaupt mit mehreren Ebenen von Rechnersystemen, wie zum Beispiel [5,6]. Die aktuelle Diskussion innerhalb der wissenschaftlichen Gemeinschaft identifiziert die Erarbeitung von Grundlagen des AC und Forschung zu einer systematischen Entwurfsmethodik als wesentliche weitere Schritte. 

Bei den Grundlagen geht es darum, die Effekte der unterschiedlichen Arten von Approximation formal zu modellieren und auf Basis dieser Modelle Methoden für die Analyse und Synthese von AC Systemen zu entwickeln. Im optimistischsten Fall könnte im Bereich der Analyse eine "Theorie des AC" entstehen, die auf der algorithmischen Ebene für neuartige formale AC Rechenmodelle Beweise über die Korrektheit, Approximation und Effizienz erlaubt. 

Methoden zur Synthese von AC Systemen legen den Grundstein für eine systematische Entwurfsmethodik mit einem möglichst hohen Grad an Automatisierung. Zum Beispiel wären Werkzeuge wünschenswert, die den Entwickler dabei unterstützen, für eine gegebene Anwendung zu bestimmen, welche der Funktionen auf welcher Ebene eines Rechnersystems am effizientesten approximiert werden können. Dazu gehört auch eine breitere Untersuchung von Anwendungsklassen, für die sich AC besonders gut eignet. Die anschließenden Werkzeugketten für die Kompilierung beziehungsweise die Hardwaresynthese und die Integration in Laufzeitsysteme müssen so entwickelt werden, dass diese Schritte vollautomatisch ablaufen. Im Bereich der Hardwareebene wäre zudem zu untersuchen, ob sich analoge und mixed-signal Komponenten für AC eignen. Analoge Schaltungen sind inhärent approximativ und in vielen eingebetteten Systemen ohnehin vorhanden, zum Beispiel als Frontends in Mobilfunksystemen. 

Zusammenfassend kann man feststellen, dass AC mit dem Anspruch, Approximation auf allen Ebenen eines Rechnersystems zu betrachten, ein neues Forschungsgebiet darstellt, welches aber auch eine Reihe von existierenden Ansätzen integriert. AC ist ein interdisziplinäres Gebiet, das Experten aus Elektrotechnik, Informatik und aus Anwendungsdomänen vereint. Um die aktuellen Forschungsfragen des AC erfolgreich zu bearbeiten und eine systematische Entwurfsmethodik zu entwickeln, braucht es ein Zusammenwirken von analoger und digitaler Schaltungstechnik, Rechnerarchitektur und  Betriebssystemen, Programmiersprachen und Compilerbau, sowie mittelfristig auch Beiträge aus der theoretischen Informatik und der Signal- und Systemtheorie. 

In Deutschland findet an der Universität Paderborn im Oktober dieses Jahres ein Workshop zum Thema Approximate Computing statt (http://approximate.uni-paderborn.de/), welcher von der GI Regionalgruppe OWL unterstützt wird.

Referenzen

[1] V. Gupta, D. Mohapatra, S. P. Park, A. Raghunathan, and K. Roy. IMPACT: imprecise adders for low- power approximate computing. In Proc. Int. Symp. on Low Power Electronics and Design (ISPLED), Seiten 409–414. 2011. IEEE.

[2] H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Neural acceleration for general-purpose approximate programs. Communications of the ACM, 58(1), Jan. 2015.

[3] S. Venkataramani, K. Roy, and A. Raghunathan. Substitute-and-simplify: A unified design paradigm for approximate and quality configurable circuits. In Proc. Design, Automation and Test in Europe Conf. (DATE), Seiten 1367–1372. EDA Consortium.

[4] P. Klavik, A. C. I. Malossi, C. Bekas, and A. Curioni. Changing Computing Paradigms Towards Power Efficiency, volume 372. Philosophical Transactions of the Royal Society, 2014.

[5] H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger. Architecture support for disciplined approximate programming. In Proc. Int. Conf. on Architectural Support for Programming Languages and Operating System (ASPLOS), Seiten 301–312.

[6] D. S. Nikolopoulos, H. Vandierendonck, N. Bellas, C. D. Antonopoulos, S. Lalis, G. Karakonstantis, A. Burg, and U. Naumann. Energy efficiency through significance-based computing. IEEE Computer, 47(7):82–85, Juli 2014.

Autoren und Copyright

Christian PlesslMarco Platzner
Institut für Informatik, Universität Paderborn

Peter J. Schreier
Institut für Elektrotechnik und Informationstechnik, Universität Paderborn

© Springer-Verlag Berlin Heidelberg 2015