On the Approximation of Arithmetic Functions and Logic Synthesis of Approximate Very Large Boolean Networks

Language
en
Document Type
Doctoral Thesis
Issue Date
2022-09-12
Issue Year
2022
Authors
Echavarria Gutiérrez, Jorge Alfonso
Editor
Abstract

Approximate computing exploits perceptual inaccuracies of the human senses, error-resilient applications, and noisy input data to produce more power-efficient architectures with greater performance than those achieved by traditional paradigms. Objectives usually conflicting and, consequently, hard to achieve. This novel research area is used in use cases where these objectives cannot be optimized simultaneously by conventional techniques without tradeoffs. It investigates hardware and software that reason and generate results in estimates instead of absolutely precise figures whilst satisfying such multi-objective simultaneity. Approximate computing has consequently become one of the most promising paradigms in computer science. As appropriately pointed out by Xu et al. [XMK16]:

Computing has entered the era of approximation

As shown by the reported findings in each of the subsequent chapters, this unique field of investigation has proven to be an efficient vehicle for achieving substantial trade-offs between accuracy and resource, power-consumption, and delay reductions. This dissertation, divided into two major parts, focuses on the design and evaluation of approximate hardware, more specifically, I) digital arithmetic circuits and II) very large Boolean networks. Particularly, Part I details the mathematical descriptions of two novel elementary approximate arithmetic units, namely: 1) An approximate adder tailored for field-programmable gate array architectures first proposed in [BEZ+16]. The proposed arithmetic unit integrates a segmented carry chain with self-healing capabilities, according to the most significant bit of the least significant carry chain segment. This approach was subsequently generalized in [EWB+16] for any given number of observable bits from the least significant part of the addition. And 2) a sequential approximate multiplier first proposed in [EWK+20b] with a shortened critical path along its combinatorial components. Part II, on the other hand, introduces two approximate logic synthesis methodologies of: 1) Small-scale Boolean designs, as first proposed in [EWT18b] and later tailored for field-programmable gate array target architectures in [EWT18a]. And 2) very large Boolean designs, by their decomposition into networks made of smaller Boolean functions, as presented in [EWT21].

Naturally, designs of approximate software or approximate hardware are expected to model the accuracy degradation observed by their approximate algorithms and architectures. Whenever a fully accurate evaluation is infeasible, however, an estimation of the error model shall be given. Following this principle, this dissertation offers an insight into the mathematics required to fully model the error behaviour of approximate designs. More specifically, it presents probabilistic techniques and algorithms first investigated in [EWP+18] and [EWK+20a] for evaluating fundamental error metrics that can be computed in polynomial time. Whilst the former work targets approximate arithmetics, the latter's main focus is on approximate Boolean digital circuits. Moreover, for those metrics that cannot be evaluated in polynomial time, proof of their membership to the so-called #P-complete class, as first shown in [EWK+22], is also provided.

Finally, covering varied usage scenarios from self-adapting image processing to fault tolerance via modular redundancy, this dissertation presents use cases first published in [PBE+17; ESB+18a] and [TEB+21] that respectively use the proposed approximate arithmetic units and Boolean logic approximation techniques showcasing their benefits when applied to real-world applications.

Abstract

„Approximate Computing“ ist ein Entwurfsparadigma, bei dem Ungenauigkeiten der menschlichen Wahrnehmung, sowie die Resistenz von Anwendungen gegenüber Fehlern und Rauschen in den Eingabedaten ausgenutzt werden, um energieeffizientere Architekturen mit höherer Leistung als mit herkömmlichen Paradigmen zu erzielen. Zielgrößen stehen üblicherweise zueinander im Konflikt. „Approximate Computing“ wird in Anwendungsfällen genutzt, bei denen die Zielgrößen durch konventionelle Techniken nicht gleichzeitig ohne Tradeoffs optimiert werden können. Dieser neuartige Forschungsbereich untersucht Hardware und Software, die Ergebnisse in Schätzungen statt in absolut präzisen Zahlen liefern und eine Optimierungstechnik darstellen, die es erlaubt, mehrere eigentlich zueinander im Konflikt stehende Zielgrößen gleichzeitig zu optimieren. „Approximate Computing“ ist folglich zu einem der vielversprechendsten Paradigmen in der Informatik geworden, wie es etwa auch von Xu et al. in [XMK16] formuliert wird: „Computing has entered the era of approximation“.

Wie die Ergebnisse dieser Arbeit zeigen, hat sich dieses einzigartige Untersuchungsgebiet als effizientes Mittel erwiesen, um wesentliche Kompromisse zwischen Genauigkeit und Ressourcen, Stromverbrauch und Verzögerungsreduzierungen zu erzielen. Diese in zwei Hauptteile unterteilte Dissertation konzentriert sich auf den Entwurf und die Bewertung von approximativer Hardware, genauer gesagt, I) digitalen arithmetischen Schaltungen und II) sehr großen Booleschen Netzwerken. Insbesondere enthält Teil I die mathematischen Beschreibungen von neuartigen approximativen Schaltungen zweier elementarer arithmetischen Funktionen, nämlich: 1) Ein approximativer Addierer, der auf FIELD-PROGRAMMABLE GATE ARRAYs (FPGAs) zugeschnitten ist, zuerst veröffentlicht in [BEZ+16]. Die vorgeschlagene arithmetische Einheit integriert eine in ein niederwertiges und ein höchstwertiges Segment aufgeteilte Übertragungskette. Außerdem bietet der vorgeschlagene Ansatz die Fähigkeit zur „Selbstheilung“ durch eine Übertragsvorhersage anhand des höchstwertigsten Bits des niederwertigen Segments. Dieser Ansatz wurde anschließend in [EWB+16] für eine frei wählbare Anzahl beobachtbarer Bits aus dem niederwertigsten Teil der Addition verallgemeinert. Daneben wird 2) ein approximativer sequentieller Multiplizierer vorgestellt, der erstmals in [EWK+20b] vorgeschlagen wurde. Er bietet einen verkürzten kritischen Pfad entlang seiner kombinatorischen Komponenten, wodurch sich seine Latenz erheblich reduzieren lässt. Teil II dieser Dissertation stellt zwei approximative Logiksynthesemethodologien vor: 1) Für die Approximation kleiner boolescher Designs, wie zuerst in [EWT18b] vorgeschlagen und später in [EWT18a] auf FPGA-Zielarchitekturen zugeschnitten wurden. Und 2) für die Approximation sehr großer boolescher Designs, die dazu in Netzwerke aus kleineren booleschen Funktionen zerlegt werden, wie in [EWT21] dargestellt.

Natürlich wird von Entwurfstechniken für approximative Software und approximative Hardware erwartet, dass sie die Genauigkeitsverschlechterung modellieren, um den Fehler quantifizieren zu können, der aufgrund der approximativen Algorithmen und Architekturen auftreten kann. Wenn eine vollständig genaue Berechnung jedoch nicht möglich bzw. zu komplex ist, muss das Modell eine Schätzung des Fehlers ermöglichen. Diesem Prinzip folgend bietet diese Dissertation einen Einblick in die Mathematik, die erforderlich ist, um das Fehlerverhalten von approximativen Designs vollständig zu modellieren. Insbesondere werden probabilistische Techniken und Algorithmen vorgestellt, die erstmals in [EWP+18] und [EWK+20a] untersucht wurden, durch welche grundlegende Fehlermetriken in polynomieller Zeit berechnet werden können. Darüber hinaus wird für diejenigen Metriken, die nicht in Polynomialzeit ausgewertet werden können, auch der Nachweis ihrer Zugehörigkeit zur sogenannten #P-vollständigen Klasse, wie erstmals in [EWK+ 22] gezeigt, erbracht. Die oben genannten Methoden und Architekturen werden als Open Source angeboten, um sie allgemein verfügbar zu machen, ihre schnelle Übernahme in Industrie und Wissenschaft voranzutreiben und gleichzeitig die richtigen Mittel für zukünftige Vergleiche bereitzustellen.

Abschließend stellt diese Dissertation verschiedene Anwendungsszenarien von selbstanpassender Bildverarbeitung bis hin zu Fehlertoleranz durch modulare Redundanz vor und präsentiert Anwendungsfälle, die erstmals in [PBE+17; ESB+18a] und [TEB+21] veröffentlicht wurden und die jeweils die vorgeschlagenen approximativen arithmetischen Funktionen und Logiksynthesetechniken zur Approximation sehr großer Boolescher Netzwerke verwenden und deren Vorteile aufzeigen, wenn sie auf reale Anwendungen angewendet werden.

DOI
Faculties & Collections