Gaussian belief propagation on a field-programmable gate array for solving linear equation systems
Electronics ; 10 (2021), 14. - Art.-Nr. 1695. - eISSN 2079-9292
Link to original publicationhttps://dx.doi.org/10.3390/electronics10141695
FacultiesFakultät für Ingenieurwissenschaften, Informatik und Psychologie
InstitutionsInstitut für Nachrichtentechnik
External cooperationsDeutsches Zentrum fuer Luft- und Raumfahrt e. V.
Document versionpublished version (publisher's PDF)
Solving Linear Equation System (LESs) is a common problem in numerous fields of science. Even though the problem is well studied and powerful solvers are available nowadays, solving LES is still a bottleneck in many numerical applications concerning computation time. This issue especially pertains to applications in mobile robotics constrained by real-time requirements, where on-top power consumption and weight play an important role. This paper provides a general framework to approximately solve large LESs by Gaussian Belief Propagation (GaBP), which is extremely suitable for parallelization and implementation in hardware on a Field-Programmable Gate Array (FPGA). We derive the simple update rules of the Message Passing Algorithm for GaBP and show how to implement the approach efficiently on a System on a Programmable Chip (SoPC). In particular, multiple dedicated co-processors take care of recurring computations in GaBP. Exploiting multiple Direct Memory Access (DMA) controllers in scatter-gather mode and available arithmetic logic slices for numerical calculations accelerate the algorithm. Presented evaluations demonstrate that the approach does not only provide an accurate approximative solution of the LES. It also outperforms traditional solvers with respect to computation time for certain LESs.
Subject headings[GND]: Message-Passing | Hardwarebeschleunigung
[LCSH]: Field programmable gate arrays
[Free subject headings]: solver for linear equation system | Gaussian belief propagation | factor graph | hardware acceleration
[DDC subject group]: DDC 004 / Data processing & computer science
LicenseCC BY 4.0 International
MetadataShow full item record
DOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-43077