Parallel LU factorization of sparse matrices on FPGA‐based configurable computing engines
- 20 February 2004
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 16 (4) , 319-343
Abstract
Configurable computing, where hardware resources are configured appropriately to match specific hardware designs, has recently demonstrated its ability to significantly improve performance for a wide range of computation‐intensive applications. With steady advances in silicon technology, as predicted by Moore's Law, Field‐Programmable Gate Array (FPGA) technologies have enabled the implementation of System‐on‐a‐Programmable‐Chip (SOPC or SOC) computing platforms, which, in turn, have given a significant boost to the field of configurable computing. It is possible to implement various specialized parallel machines in a single silicon chip. In this paper, we describe our design and implementation of a parallel machine on an SOPC development board, using multiple instances of a soft IP configurable processor; we use this machine for LU factorization. LU factorization is widely used in engineering and science to solve efficiently large systems of linear equations. Our implementation facilitates the efficient solution of linear equations at a cost much lower than that of supercomputers and networks of workstations. The intricacies of our FPGA‐based design are presented along with tradeoff choices made for the purpose of illustration. Performance results prove the viability of our approach. Copyright © 2004 John Wiley & Sons, Ltd.Keywords
This publication has 20 references indexed in Scilit:
- VIP: an FPGA-based processor for image processing and neural networks2002
- Quantitative analysis of floating point arithmetic on FPGA based custom computing machines2002
- Dataflow computation with intelligent memories emulated on field-programmable gate arrays (FPGAs)Microprocessors and Microsystems, 2002
- Reconfigurable Computing for Digital Signal Processing: A SurveyJournal of Signal Processing Systems, 2001
- Efficient sparse LU factorization with partial pivoting on distributed memory architecturesIEEE Transactions on Parallel and Distributed Systems, 1998
- New ordering methods for sparse matrix inversion via diagonalizationIEEE Transactions on Power Systems, 1997
- Parallel DSP algorithms on TurboNet: an experimental system with hybrid message-passing/shared-memory architectureConcurrency: Practice and Experience, 1996
- Efficient mapping algorithms for a class of hierarchical systemsIEEE Transactions on Parallel and Distributed Systems, 1993
- An efficient ordering algorithm to improve sparse vector methodsIEEE Transactions on Power Systems, 1988
- Mode ordering algorithms for sparse vector method improvementIEEE Transactions on Power Systems, 1988