Go to page
 

Bibliographic Metadata

Title
Stochastic Computing and its Application to the Sparse Kaczmarz Algorithm / Author Daniel Wiesinger
AuthorWiesinger, Daniel
CensorHuemer, Mario
Thesis advisorHuemer, Mario
PublishedLinz, 2018
DescriptionX, 95 Seiten : Illustrationen
Institutional NoteUniversität Linz, Masterarbeit, 2018
LanguageEnglish
Document typeMaster Thesis
Keywords (EN)Stochastic computing / Kaczmarz / Sparse estimation
URNurn:nbn:at:at-ubl:1-23498 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Stochastic Computing and its Application to the Sparse Kaczmarz Algorithm [6.49 mb]
Links
Reference
Classification
Abstract (German)

Stochastic computing beschreibt eine wiederaufkommende Art des Rechnens, bei der Zahlen als Wahrscheinlichkeiten dargestellt werden. Eine Realisierung durch zufällige Bitströme ermöglicht hardware-effiziente Berechnungen mit hoher Fehlertoleranz. Dies ebnet den Weg für effiziente, Bitfehler-robuste Implementierungen, die auf fehlerhafter Hardware, in stark verrauschten Umgebungen oder mit unzuverlässigen aufkommenden Technologien betrieben werden können. Das Ziel dieser Arbeit ist es, den Stand der Technik des Rechenparadigmas zu erfassen und damit eine ausgewählte Anwendung, den Scaled Sparse Kaczmarz Algorithmus, zu realisieren. Zu Beginn stellen wir die wichtigsten Konzepte von stochastic computing wie auch dessen Baublöcke (z.B. Addierer und Multiplizierer) vor. Dabei verwenden wir eine neuartige, gewichts-basierte Betrachtungsweise, die das Design und die Analyse stochastischer Systeme vereinfacht. In unseren Untersuchungen identifizieren wir herkömmliche Addierbausteine als wesentliche Limitierung praktischer Implementierungen. Sie skalieren ihr Ergebnis entweder oder verwenden herkömmliche binäre Zahlendarstellungen, die die Anfälligkeit gegenüber Bitfehlern erhöhen. Wir lösen diese Probleme durch die Einführung neuartiger Schieberegister-basierter unskalierter Addierer, neuartiger Hochskalierer und einer neuartigen Skalarprodukt-Implementierung. Durch ihre einzigartigen Konzepte übertrifft diese Skalarprodukt-Implementierung herkömmliche Implementierungen signifikant, sofern Genauigkeitsanforderungen und die Eingangsvektorlänge hinreichend hoch/groß sind. Im zweiten Teil der Arbeit wird der Scaled Sparse Kaczmarz Algorithmus als stochastic computing System implementiert. Dieser entspricht einer skalierten Variante der Fast Linearized Bregman Iteration, einem hocheffizienten Optimierungs-Algorithmus, der für die Schätzung dünnbesetzter Vektoren verwendet wird. Auf dem Weg zur endgültigen Implementierung lösen wir mehrere herausfordernde Probleme, wie eingebrachte Skalierungsfaktoren und die statistische Abhängigkeit von Bitströmen. Wir synthetisieren das Design und präsentieren bit-echte Simulationsergebnisse, die mit jenen einer double-precision Gleitkomma Referenz verglichen werden. Die Ergebnisse zeigen gute Übereinstimmung, was zeigt, dass sich selbst mächtige Schätzalgorithmen für dünnbesetzte Vektoren als ein stochastic computing System realisieren lassen.

Abstract (English)

Stochastic computing is a re-emerging computing paradigm, that expresses numbers as probabilities. By realizing them in the form of random bitstreams, it enables hardware-efficient calculations with high fault-tolerance. This paves the way for efficient, bit-flip-robust implementations, that can be operated on faulty hardware, in very noisy environments or with unreliable emerging technologies. The aim of this work is to provide a state-of-the-art overview of the computing paradigm and to apply it to a selected application, the Scaled Sparse Kaczmarz algorithm. We first present relevant concepts of stochastic computing as well as its building blocks (e.g. adders and multipliers). For this, we introduce a novel weight-based viewpoint, that simplifies the design and investigation of stochastic computing systems. Based on our investigations, we identified state-of-the-art adders to be a major limiting factor for practical implementations. They either inherently apply a scaling factor on their result or use conventional binary number representations, that make them vulnerable against bit flips. We solve these issues by introducing novel shift-register-based non-scaled adders, novel upscalers and a novel scalar product implementation. With its unique concepts, the scalar product implementation significantly outperforms state-of-the-art implementations, if accuracy requirements and input vector lengths are sufficiently high/large. In the second part of this work, we implement the Scaled Sparse Kaczmarz algorithm via stochastic computing. It is a scaled variant of the Fast Linearized Bregman iteration, a highly-efficient optimization algorithm, that is used for sparse estimation. On the way to the final implementation, we solve several challenging issues, such as introduced scaling factors and statistical dependence of bitstreams. We synthesize the design and present bit-true simulation results, that are compared to those of a double-precision floating-point reference. There is a good agreement of the results, demonstrating, that even powerful algorithms for sparse estimation can be realized as a stochastic computing system.

Stats
The PDF-Document has been downloaded 29 times.