English

This thesis addresses implementations of the self-organizing map, an algorithm from the realm of artificial neural networks developed by Teuvo Kohonen. The algorithm is, just like its natural archetype, parallel in nature and thus well suited for parallel hardware implementation. The hardware option is useful in a range of applications dealing with huge amounts of data, real time requirements and a limited energy budget. An example with these requirements would be hyperspectral imaging of planetary surfaces on board of a satellite or drone. The research results regarding self-organizing maps in hardware are organized into several areas: On the processing element level, usually a number of different hardware specific adaptations of the algorithm are introduced, aiming towards a more efficient implementation. The discretization of input and output data is one of the most important adaptations, allowing for exchanging expensive floating point operations for cheaper integer operations, resulting in an overall reduction of resource consumption. At the same time, the algorithms functionality is modified, too: primarily the precision of input and output data is reduced; secondary effects are a result of the internal modifications accumulating throughout the calculations. To be able to evaluate these effects, a new metric is developed which allows for a better comparability of different implementations. Using a number of different datasets, the new metric is used to evaluate a number of different modifications. As a result, a set of minimal requirements for hardware implementations of the self-organizing map could be found. On the architectural level, an analysis discloses two independent degrees of parallelism which can be exploited independently. To be able to find a suitable hardware solution for a given task, a model for the estimation of the resource consumption of a hardware implementation (area, power, and latency) is developed on the basis of exemplary hardware implementations of the different architectures. Having acquired these values for a given task (for a given task an infinite number of hardware implementations can be evaluated), a method to find the best solution(s) has to be found. One way is to calculate the so called Pareto set, which consists of a number of points in the design space, which are not dominated by other points, meaning that no other implementation is better in all the characteristics (area, power, and latency). As this set can again be very large, a method for evaluating the points, the so called resource efficiency is introduced. Thus, an optimal implementation can be found for every task. To be able to test parts of the design and to create a prototypical implementation, two tools are introduced which allow for comfortable analysis of digital circuits in a semiautomatic environment. The first tool called HiLDE is a bridge between a digital, FPGAbased hardware implementation and a simulation environment such as Matlab/Simulink or ModelSim. It allows for the verification of the correctness of the implemented circuit while disregarding timing issues such as the critical path. On behalf of these, another tool called HiLDEGART is introduced to be able to observe and parameterize a hardware implementation running in its target environment in real time. As a number of hardware blocks have to be created for both of the tools, a versatile and powerful library for automatic code generation in VHDL called vMAGIC was created. These tools are used to create a prototypical implementation of the self-organizing map hardware in FPGA technology, allowing for a reliable evaluation of the architecture. The resulting data is compared with software based implementations running on several processor architectures. This comparison shows that even with a comparably small and non-optimal implementation, a hardware solution is faster even in comparison to current multi-core processor architectures. An extrapolation for future technologies shows that on the long run hardware is a feasible solution for high performance, low energy calculation of self-organizing maps.

Deutsch

Die vorliegende Arbeit befasst sich mit der Untersuchung verschiedener Implementierungen der sogenannten selbst-organisierenden Karten, einem Algorithmus aus dem Bereich der künstlichen neuronalen Netze von Teuvo Kohonen. Der Algorithmus ist, wie sein natürliches Vorbild, inhärent parallel und eignet sich somit für eine Abbildung in paralleler Hardware. Dies ist in vielen Anwendungsgebieten sinnvoll, da hier zum Teil sowohl harte Echtzeitanforderungen als auch Einschränkungen bzgl. des Energiebudgets existieren. Ein Beispiel hierfür ist die Analyse hyperspektraler Aufnahmen von Planetenoberflächen an Bord eines Satelliten oder einer Drohne. Die Untersuchungen gliedern sich in verschiedene Bereiche: Im Bereich der einzelnen Rechenelemente werden in der Regel hardwarespezifische Anpassungen wie etwa die Diskretisierung der Wertebereiche vorgenommen. Dadurch können an Stelle der in Software gewöhnlich verwendeten Gleitkommaberechnungen einfachere Ganzzahlberechnungen verwandt werden, was den Ressourcenbedarf der einzelnen Recheneinheiten drastisch reduziert. Gleichzeitig wird auch die Funktionalität des Algorithmus verändert: primär reduziert sich die Präzision der Zahldarstellung von Ein- und Ausgangsdaten, sekundäre Effekte entstehen durch die Akkumulation von Veränderungen innerhalb der Berechnungen. Um diese Effekte beurteilen zu können wird im Rahmen dieser Arbeit ein neues Maß erarbeitet, das eine bessere Vergleichbarkeit verschiedener Implementierungen ermöglicht. Dieses wird auf einige Beispieldatensätze angewandt um verschiedene hardwarespezifische Anpassungen hinsichtlich ihrer Auswirkungen zu bewerten. Auf Architekturebene stellt sich vor Allem die Frage nach der parallelen Implementierung des Algorithmus, denn eine Analyse zeigt effektiv zwei völlig unabhängige Freiheitsgrade, entlang derer parallelisiert werden kann. Um für eine bestimmte Anwendung die richtige Implementierung zu finden, wird auf Basis von exemplarischen Messungen ein Modell für den Ressourcenbedarf (Leistungsaufnahme, Latenz, Fläche) aufgestellt, bei dem unter Anderem Parameter wie die Anzahl der implementierten Rechenelemente und die Art der Parallelisierung frei wählbar sind. Für das oben beschriebene Anwendungsbeispiel wird dann die Pareto-Menge berechnet, deren Mitglieder dann mit Hilfe der sogenannten Ressourceneffizienz bewertet werden. So kann für jede Anwendung eine optimale Implementierung gefunden werden. Um die so gefundene Implementierung testen zu können werden zunächst zwei verschiedene Werkzeuge vorgestellt, die komfortable Analysen in einem teilautomatisierten Umfeld ermöglicht. Zunächst wird HiLDE vorgestellt, ein Werkzeug das die Kopplung zwischen einer Softwaresimulation (z.B. Matlab/Simulink oder ModelSim) und einer Hardwareimplementierung ermöglicht. Bei den mit HiLDE ermöglichten Tests wird ausschließlich die funktionale Korrektheit einer Implementierung getestet, Effekte die sich auf den kritischen Pfad beziehen werden außer Acht gelassen. Um auch diese Effekte berücksichtigen zu können wurde HiLDEGART entwickelt, ein Werkzeug das die Beobachtung und Parametrierung einer Implementierung in Echtzeit erlaubt. Da für beide Werkzeuge zahlreiche spezifisch angepasste Hardwarekomponenten benötigt werden, wurde mit der vMAGIC Bibliothek ein Werkzeug für die automatische Quellcodegenerierung für VHDL geschaffen. Um einen konkreten Vergleich zwischen Hardware- und Softwareimplementierungen herbeizuführen, wurde mit Hilfe dieser Werkzeuge eine prototypische Implementierung erzeugt und vermessen. Hierbei zeigt sich, dass auch für die vergleichsweise kleine und nicht optimal implementierte Variante eine Beschleunigung gegenüber aktuellen Mehrprozessorsystemen erzielt werden kann. Eine Extrapolation für zukünftige Technologien verdeutlicht die prinzipiellen Vorteile der gewählten Vorgehensweise.