Efficient Implementations of Matrix Inversion on 2D Array Architecture

Matrix inversion is one of the most common operations in many signal-processingalgorithms. It plays a vital role in Multiple-Input and Multiple-Output (MIMO) systems, beamforming, image recovery, phased-array radar and sonar, 3G wireless communication, and Worldwide Interoperability for Microwave Access (WiMAX). Performing the inversion of large matrices accurately is challenging due to its large computational cost. The thesis presents efficient implementations of matrix inversion using the Gauss- Jordan method and the Gram-Schmidt method which consists of computation of the QR Decomposition of the matrix followed by backward elimination and matrix multiplications. The targeted matrix size is 4 × 4 with complex values for the Gauss- Jordan method, and real values using the Gram-Schmidt method. Both methods can be easily scaled to handle large-sized matrices with the same data flow. The two matrix inversion methods are mapped onto a Domain Adaptive Processor (DAP) developed by researchers at the University of Michigan to meet the needs of signal processing workloads. It consists of 64 Processing Elements (PEs) connected in a 2D array. Each PE is further divided into sub-PEs capable of loading, storing, and performing mathematical computations for real and complex numbers. The hardware code for DAP implementation was configured using a combination of handcrafted Comma Separated Values (.csv) files and an auto code generation tool. This tool was developed by researchers at ASU to handle instruction redundancies and perform instruction-level parallelism to generate VLIW code for DAP. Both implementations were evaluated and compared based on latency, throughput, and precision. The thesis also covers scaling requirements for a set of input ranges and different routing methods. These are necessary for both algorithms to achieve high throughput with minimal instruction count.