A New Pipelined Systolic Array-Based Architecture for Matrix Inversion in FPGAs with Kalman Filter Case Study
- PDF / 838,899 Bytes
- 12 Pages / 600.03 x 792 pts Page_size
- 19 Downloads / 200 Views
A New Pipelined Systolic Array-Based Architecture for Matrix Inversion in FPGAs with Kalman Filter Case Study Abbas Bigdeli, Morteza Biglari-Abhari, Zoran Salcic, and Yat Tin Lai Department of Electrical and Computer Engineering, the University of Auckland, Private Bag 92019, Auckland, New Zealand Received 11 November 2004; Revised 20 June 2005; Accepted 12 July 2005 A new pipelined systolic array-based (PSA) architecture for matrix inversion is proposed. The pipelined systolic array (PSA) architecture is suitable for FPGA implementations as it efficiently uses available resources of an FPGA. It is scalable for different matrix size and as such allows employing parameterisation that makes it suitable for customisation for application-specific needs. This new architecture has an advantage of O(n) processing element complexity, compared to the O(n2 ) in other systolic array structures, where the size of the input matrix is given by n × n. The use of the PSA architecture for Kalman filter as an implementation example, which requires different structures for different number of states, is illustrated. The resulting precision error is analysed and shown to be negligible. Copyright © 2006 Hindawi Publishing Corporation. All rights reserved.
1.
INTRODUCTION
Many DSP algorithms, such as Kalman filter, involve several iterative matrix operations, the most complicated being matrix inversion, which requires O(n3 ) computations (n is the matrix size). This becomes the critical bottleneck of the processing time in such algorithms. With the properties of inherent parallelism and pipelining, systolic arrays have been used for implementation of recurrent algorithms, such as matrix inversion. The lattice arrangement of the basic processing unit in the systolic array is suitable for executing regular matrix-type computation. Historically, systolic arrays have been widely used in VLSI implementations when inherent parallelism exists in the algorithm [1]. In recent years, FPGAs have been improved considerably in speed, density, and functionality, which makes them ideal for system-on-a-programmable-chip (SOPC) designs for a wide range of applications [2]. In this paper we demonstrate how FPGAs can be used efficiently to implement systolic arrays, as an underlying architecture for matrix inversion and implementation of Kalman filter. The main contributions of this paper are the following. (1) A new pipelined systolic array (PSA) architecture suitable for matrix inversion and FPGA implementation,
which is scalable and parameterisable so that it can be easily used for new applications (2) A new efficient approach for hardware-implemented division in FPGA, which is required in matrix inversion. (3) A Kalman filter implementation, which demonstrates the advantages of the PSA. The paper is organised as follows. In Section 2, the Schur complement for the matrix inversion operation is described and a generic systolic array structure for its implementation is shown. Then a new design of a modified array structure, called PSA, is proposed. In Section 3
Data Loading...
