GUSTO: An automatic generation and optimization tool for matrix inversion architectures

Abstract

Matrix inversion is a common function found in many algorithms used in wireless communication systems. As FPGAs become an increasingly attractive platform for wireless communication, it is important to understand the trade-offs in designing a matrix inversion core on an FPGA. This article describes a matrix inversion core generator tool, GUSTO, that we developed to ease the design space exploration across different matrix inversion architectures. GUSTO is the first tool of its kind to provide automatic generation of a variety of general-purpose matrix inversion architectures with different parameterization options. GUSTO also provides an optimized application-specific architecture with an average of 59% area decrease and 3X throughput increase over its general-purpose architecture. The optimized architectures generated by GUSTO provide comparable results to published matrix inversion architecture implementations, but offer the advantage of providing the designer the ability to study the trade-offs between architectures with different design parameters.

References

1. Abe, T., Tomisato, S., and Matsumoto, T. 2003a. A MIMO turbo equalizer for frequency-selective channels with unknown interference. IEEE Trans. Vehicular Technol. 52, 3, 476--482.
2. Abe, T. and Matsumoto, T. 2003b. Space-Time turbo equalization in frequency selective MIMO channels. IEEE Trans. Vehicular Technol. 469--475.
3. Bjőrck, A. and Paige, C. 1992. Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm. SIAM J. Matrix Anal. Appl. 13, 1, 176--190.
4. Bjőrck, A. 1994. Numerics of Gram-Schmidt orthogonalization. Linear Algebra Appl. 198, 297--316.
5. Cagley, R. E., Weals, B. T., Mcnally, S. A., Iltis, R. A., Mirzaei, S., and Kastner, R. 2007. Implementation of the Alamouti OSTBC to a distributed set of single-antenna wireless nodes. In Proceedings of the IEEE Wireless Communications and Networking Conference. IEEE. 577--581.
6. Edman, F. and Öwall, V. 2005. A scalable pipelined complex valued matrix inversion architecture. In Proceedings of the IEEE International Symposium on Circuits and Systems. 4489--4492.
7. Eilert, J., Wu, D., and Liu, D. 2007. Efficient complex matrix inversion for MIMO software defined radio. In Proceedings of the IEEE International Symposium on Circuits and Systems. 2610--2613.
8. Golub, G. H. and Loan, C. F. V. 1996. Matrix Computations 3rd Ed. John Hopkins University Press, Baltimore, MD.
9. Hangjun, C., Xinmin, D., and Haimovich, A. 2003. Layered turbo space-time coded MIMO-OFDM systems for time varying channels. In Proceedings of the IEEE Global Telecommunications Conference, 4, 1831--1836.
10. IEEE 802.11. LAN/MAN wireless LANS. IEEE Standards Association. http://standards.ieee.org/getieee802/802.11.html
11. IEEE 802.16. LAN/MAN broadband wireless LANS. IEEE Standards Association. http://standards. ieee.org/getieee802/802.16.html
12. Iltis, R. A., Mirzaei, S., Kastner, R., Cagley, R. E., and Weals, B. T. 2006. Carrier offset and channel estimation for cooperative MIMO sensor networks. In Proceedings of the IEEE Global Telecommunications Conference. 1--5.
13. Irturk, A., Benson, B., Mirzaei, S., and Kastner, R. 2008. An FPGA design space exploration tool for matrix inversion architectures. In Proceedings of the IEEE Symposium on Application Specific Processors (SASP).
14. Karkooti, M., Cavallaro, J. R., and Dick, C. 2005. FPGA implementation of matrix inversion using QRD-RLS algorithm. In Proceedings of the Conference Record of the 39th Asilomar Conference on Signals, Systems and Computers. 1625--1629.
15. Kusume, K., Joham, M., Utschick, W., and Bauch, G. 2005. Efficient Tomlinson-Harashima precoding for spatial multiplexing on flat MIMO channel. In Proceedings of the IEEE International Conference on Communications, vol. 3. 2021--2025.
16. Meng, Y., Brown, A. P., Iltis, R. A., Sherwood, T., Lee, H., and Kastner, R. 2005. MP core: Algorithm and design techniques for efficient channel estimation in wireless applications. In Proceedings of the 42nd Design Automation Conference. 297--302.
17. Singh, C. K., Prasad, S. H., and Balsara, P. T. 2007. VLSI architecture for matrix inversion using modified Gram-Schmidt based QR decomposition. In Proceedings of the 20th International Conference on VLSI Design. 836--841.
18. Zhou, L., Qiu, L., and Zhu, J. 2005. A novel adaptive equalization algorithm for MIMO communication system. In Proceedings of the Vehicular Technology Conference. 2408--2412.