title: Approximate and Reconfigurable Precision Instruction Set Processors for Tightly Coupled Processor Arrays
title: Instruktionssatz-Prozessorarchitekturen mit Approximation und Rekonfigurierbarer Genauigkeit für Eng Gekoppelte Prozessorfelder
Creators: name: Brand, Marcel
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024
Subjects: subject: Tightly Coupled Processor Arrays
subject: Orthogonal Instruction Processing
subject: Anytime Instructions
subject: Vector Processing
subject: Reconfigurable Precision
subject: Programmable Accuracy
subject: Very Long Instruction Word Processor
subject: Coarse-grained Reconfigurable Arrays
subject: DDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::004 Informatik

description: With the decline of Moore’s law, the trend of processor architecture design shifts from powerful single-core processors to compensating for the stagnating increase of single-core frequency with the parallelism provided by many- and multi-core systems. For the increasing degree of parallelism, it also becomes more and more important to have access to small processing elements that are not only energy efficient but have a compact instruction set and use the costly instruction memory efficiently. This thesis presents a set of novel processor architectures that can be particularly beneficial when used in loop accelerator architectures like Tightly Coupled Processor Arrays (TCPAs) to not only save hardware but also energy and time under constraints for computational accuracy. Already the current generation of processor-array-on-chip architectures, e.g., coarse-grained reconfigurable or programmable arrays, include more than 100s or even 1,000s of processing elements. Thus, it becomes essential to keep the on-chip configuration/instruction memories of each processing element as small as possible. Even compilers must take into account the scarceness of available instruction memory and create the code as compact as possible. However, compilers for Very Long Instruction Word (VLIW) processors have the well-known problem that they typically produce lengthy codes, especially for pipelined instruction sequences. Barely utilized Functional Units (FUs) as well as repeating operations of single FUs inside pipelined instruction sequences may lead to unnecessary or redundant code. Techniques like software pipelining can be used to improve the utilization of the FUs, yet with the risk of code explosion due to the overlapped scheduling of multiple loop iterations or other control flow statements. The proposed Orthogonal Instruction Processing (OIP) processor architecture by Brand et al. shows that the size of pipelined code of compute-intensive loop programs can be reduced significantly compared to the size of an equivalently pipelined VLIW program. The general concept of OIP is to have each FU process a microprogram orthogonally to each other but share control flow and access to the peripheral infrastructure. Contrary to VLIW processors, each FU is equipped with its own instruction memory, branch unit, and program counter. Each FU has access to shared register files and the flags from all functional units inside the processor. The synchronization of the microprograms may necessitate the repeated execution of single instructions for a fixed number of cycles. This can be encoded in the branch instruction and capsuled by only a single instruction to prevent redundant code. To utilize OIP processors to their full potential, they have to be programmed in a way that minimizes the idle time of FUs (e.g., due to data dependencies) and maximizes throughput. To solve this resource-constrained modulo scheduling problem, techniques based on mixed integer linear programming have been proposed. The necessary hardware extensions of OIP do not produce an overhead of resources, especially of needed instruction memory, compared to VLIW processors. Therefore, the architecture in conjunction with a set of benchmark applications has been analyzed and evaluated regarding program size, memory size, and overall architecture cost (based on a cost model by Müller et al.) in relation to VLIW processors. It could be shown that OIP produces no computational or memory overhead as soon as the program size of the OIP application is at least 50% less than the VLIW application. The necessary code size reduction is not only achieved for all investigated benchmarks, but depending on the application, the code size can even go down to 4.6% compared to its VLIW counterpart. Thus, expensive instruction memory can be saved which reduces the area and power requirements of an OIP processor in comparison to a VLIW processor with an equal number of functional units. Besides memory requirements, many relevant applications from domains like image processing or machine learning are compute-intensive. But not always do they rely on perfectly accurate results, e.g., even though reasonably inaccurate computations of Convolutional Neural Networks (CNNs) may influence the exact probabilities of each class, they rarely change the final decision. With this motivation in mind, Anytime Instruction Processing (AIP) has been defined and investigated, a concept for programmable accuracy floating-point computations. AIP gives a programmer or compiler control over the accuracy of computed floating-point (FP) operations. The accuracy of the computations is encoded on bit granularity into the instruction, which leads to the executed operation only computing that many most significant bits (MSBs) and may even terminate earlier than when it had been computed at full accuracy. This is achieved by encoding an intended accuracy into the instruction’s opcode which specifically defines how many most significant mantissa bits of the FP operation shall be computed. Thus, only errors in the resulting mantissa are to be expected, while the resulting exponent and sign are computed accurately. An anytime division capitalizes on the fact that divisions are classically already computed MSB first and is implemented by a non-restoring division that can terminate early based on the instructed accuracy. Implementations for the typically non-MSB first operations of addition and multiplication were presented in. One implementation uses on-line arithmetic to compute the addition or multiplication of the mantissa MSB first, and the alternative uses a bitmasking scheme to mask the least significant bits that should not be computed. In on-line arithmetic, a recurrence equation is derived for an operation in which the dependencies between two consecutive result bits are removed (e.g., the carry chain of an addition). Without those dependencies, each result bit can be computed independently of all others, enabling MSB first computation. By computing MSB first, on-line arithmetic also provides a high potential for pipelining: the execution of consecutive on-line instructions can start as soon as the first digit of the preceding instruction has been computed. Furthermore, operating in a redundant number format can help to reduce the complexity of the recurrence equation and the number of iterations required. Thus, binary operations in on-line arithmetic are usually performed in the redundant Signed Digit Radix-2 (SDR2) number format. The redundant FP number format SDFP has been defined based on SDR2 and enables the use of on-line arithmetics in anytime instructions. An alternative implementation of anytime additions and multiplications, the bitmasking approach, is based on masking the operand bits that do not contribute to the specified a MSBs of the result mantissa. In case of a multiplication, this masking is applied to the partial products, instead of directly to the operands to reduce a possible error. Compared to on-line arithmetic, computations may have a higher error, but the hardware overhead is negligible. After integrating the anytime instruction paradigm into the C++ arbitrary precision framework Aarith, this framework was then used to evaluate the error behavior of anytime addition, multiplication, and division operations. Power and area were evaluated through the use of synthesis and simulation tools. The experiments clearly show a favor of computing iterative applications with anytime instructions. It is shown that the computation of an iterative Jacobi solver can on average save up to 39% of energy with a computational error of below 0.1% when compared to single-precision FP computations. Further, the applicability of anytime instructions for CNNs has been specifically investigated by setting an individual accuracy per layer of the inference of a ResNet-18 CNN implementation. It could be shown by a design space exploration that by using AIP, the energy of the inference can be reduced by up to 62%, again, compared to single-precision FP computations. Besides the programmable accuracy provided by anytime instructions, reconfigurable-precision floating-point functional units have been investigated that not only provide different floating-point formats that can be selected dynamically but also vectorization and sub-word parallelism to potentially increase the performance of applications even further. In summary, by using the concepts presented in this thesis implemented into the novel OIP processor architecture, it is possible to save not only hardware area and instruction memory but also tremendously energy and time when executing loop applications under constraints for computational accuracy, in specific circumstances even without reducing the result accuracy.
description: Mit dem Nachlassen des Moor'schen Gesetzes geht der Trend bei der Entwicklung von Prozessorarchitekturen von leistungsstarken Single-Core-Prozessoren hin zu Multi-Core-Systemen auf einzelnen Chips um die stagnierende Rechenleistung mit Rechenparallelität zu kompensieren. Daher wird es immer wichtiger, kleine Prozessoren im Portfolio von Rechnerarchitekturen zu haben, die trotz allem leistungsstark sind, eine effiziente Programmkodierung unterstützen und den vorhandenen Speicher für Instruktionen und Daten so effizient wie möglich nutzen. In dieser Arbeit werden Konzepte und Implementierungen für einen flexiblen, neuartigen Prozessor vorgestellt, der effizient in Schleifenbeschleunigerarchitekturen wie Tightly Coupled Processor Arrays (TCPAs) mit dem Ziel eingesetzt werden kann, Hardware, Energie und Laufzeit einzusparen. Das orthogonale Rechnen innerhalb eines einzelnen Prozessors (Orthogonal Instruction Processing, oder OIP), Instruktionen, mit denen man programmierbar genau rechnen kann (Anytime Instructions) sowie funktionale Einheiten mit rekonfigurierbarer Präzision von Gleitkommazahlen gehen diese Probleme an. Bereits die aktuelle Generation von Prozessor-Array-auf-einem-Chip-Architekturen, zum Beispiel Coarse-Grained Reconfigurable Arrays (CGRAs), umfassen bereits mehr als Hundert oder sogar Tausende von Prozessorelementen. Daher ist es unerlässlich, die Konfigurations- und Befehlsspeicher der einzelnen Prozessoren so klein wie möglich zu halten. Auch Compiler müssen mit den kleinen Speichern umgehen können, weswegen dies beim Architekturdesign berücksichtigt werden muss. Für „Very Long Instruction Word“-Prozessoren (VLIW-Prozessoren) haben Compiler beispielsweise das Problem, dass sie typischerweise länglichen Programmcode erzeugen. Kaum genutzte Funktionseinheiten sowie sich wiederholende Operationen einzelner FUs in Befehlssequenzen können zu unnötigem oder redundantem Code führen. Die vorgeschlagene OIP-Prozessorarchitektur zeigt, dass die Programmgröße von rechenintensiven Schleifenprogrammen im Vergleich zur Größe eines äquivalenten VLIW-Programms enorm reduziert werden kann. Das allgemeine Konzept von OIP besteht darin, dass jede Funktionseinheit ein Mikroprogramm orthogonal ausführen kann, aber den Kontrollfluss und die Infrastruktur mit den übrigen Funktionseinheiten teilt. Im Gegensatz zu VLIW-Prozessoren ist jede funktionale Einheit mit einem eigenen Befehlsspeicher, einer Einheit für Sprungentscheidungen und einem Programmzähler ausgestattet. Die notwendigen Hardware-Erweiterungen von OIP führen durch die Einsparung von Befehlsspeicher nicht dazu, dass OIP-Prozessoren teurer als VLIW-Prozessoren werden, sondern eher zum Gegenteil. Es wird gezeigt, dass die OIP-Hardwareerweiterungen keinen Overhead für Speicher oder Fläche erzeugen, sobald die Codegröße eines OIP-Programms mindestens um 50% geringer ist als ein vergleichbares VLIW-Programm. Bei manchen Anwendungen kann die Reduktion der Programmgröße sogar nur noch 4,6% des VLIW-Pendants betragen. So kann teurer Speicher eingespart werden. Das Konzept der programmierbaren Genauigkeit durch Anytime-Instruktionen macht sich die Tatsache zunutze, dass bei vielen Algorithmen nicht jede Operation mit voller Genauigkeit berechnet werden muss. Dadurch kann man einen Kompromiss zwischen Verarbeitungszeit, Genauigkeit und Stromverbrauch finden und ausnutzen. Anytime-Instruktionen erweisen sich als besonders nützlich bei der Berechnung von iterativen Algorithmen wie das Berechnen einer Quadratwurzel oder dem Lösen von Gleichungssystemen mittels des Jacobi-Algorithmus. Aber auch in anderen Anwendungsbereichen zeigen sich Vorteile. So kann zum Beispiel im Vergleich zu regulären Gleitkommaoperationen der Energieverbrauch bei der Inferenz von Convolutional Neural Networks (CNNs) um bis zu 62% gesenkt werden, ohne die Fehlerquote der Klassifizierung zu erhöhen. Neben der programmierbaren Genauigkeit, die durch Anytime-Instruktionen bereitgestellt wird, haben wir Gleitkommafunktionseinheiten mit rekonfigurierbarer Präzisions untersucht. Diese können nicht nur verschiedene Gleitkommaformate dynamisch auswählen, sondern durch Vektorisierung Sub-Wort-Parallelität bereitstellen, wobei der Durchsatz von Anwendungen erhöht werden kann. Zussammengefasst lässt sich sagen, dass durch den Einsatz der in dieser Arbeit vorgestellten Konzepte, implementiert in dem neuartigen OIP-Prozessor, für eine vielzahl von Applikationen nicht nur Laufzeit, sondern auch Energie eingespart werden kann, ohne die Qualität der Ergebnisse merklich, wenn überhaupt, zu verschlechtern.