Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81075
Title: Breaking Sequential Dependencies in FPGA-Based Sparse LU Factorization
Authors: Siddhartha
Kapre, Nachiket
Keywords: Computer Science and Engineering
Issue Date: 2014
Source: Siddhartha, & Kapre, N. (2014). Breaking Sequential Dependencies in FPGA-Based Sparse LU Factorization. 2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines, 60-63.
Abstract: Substitution, and reassociation of irregular sparse LU factorization can deliver up to 31% additional speedup over an existing state-of-the-art parallel FPGA implementation where further parallelization was deemed virtually impossible. The state-of-the-art implementation is already capable of delivering 3× acceleration over CPU-based sparse LU solvers. Sparse LU factorization is a well-known computational bottleneck in many existing scientific and engineering applications and is notoriously hard to parallelize due to inherent sequential dependencies in the computation graph. In this paper, we show how to break these alleged inherent dependencies using depth-limited substitution, and reassociation of the resulting computation. This is a work-parallelism tradeoff that is well-suited for implementation on FPGA-based token dataflow architectures. Such compute organizations are capable of fast parallel processing of large irregular graphs extracted from the sparse LU computation. We manage and control the growth in additional work due to substitution through careful selection of substitution depth. We exploit associativity in the generated graphs to restructure long compute chains into reduction trees.
URI: https://hdl.handle.net/10356/81075
http://hdl.handle.net/10220/39139
DOI: 10.1109/FCCM.2014.26
Rights: © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/FCCM.2014.26].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Conference Papers

Files in This Item:
File Description SizeFormat 
Breaking Sequential Dependencies in FPGA-Based Sparse LU Factorization.pdf217.81 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 20

3
Updated on Jul 16, 2020

Page view(s)

289
Updated on Jun 27, 2022

Download(s) 50

124
Updated on Jun 27, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.