Design strategies for parallel iterative algorithms are presented. In order to further study different tradeoff strategies in design criteria for integrated circuits, A 10 × 10 Jacobi Brent-Luk-EVD array with the simplified μ-CORDIC processor is used as an example. The experimental results show that using the μ-CORDIC processor is beneficial for the design criteria as it yields a smaller area, faster overall computation time, and less energy consumption than the regular CORDIC processor. It is worth to notice that the proposed parallel EVD method can be applied to real-time and low-power array signal processing algorithms performing beamforming or DOA estimation. 1. Introduction We are on the edge of many important developments which will require parallel data and information processing. The transmission systems are using higher and higher frequencies and the carrier frequencies are increasing to 10？GHz and above. Because of the smaller wavelength more antennas can be implemented on a single device leading to massive MIMO systems. Parallel VLSI architectures will be needed in order to provide the required computational power for 10？GHz and above, massive MIMO, and big data processing [1, 2]. In parallel matrix computation at the circuit level, implementing an iterative algorithm on a multiprocessor array results in a tradeoff between the complexity of an iteration step and the number of required iteration steps. Therefore, as long as the algorithm's convergence properties are guaranteed, it is possible to adjust the architecture, which can significantly reduce the complexity with regard to the implementation. Computing the parallel eigenvalue decomposition (EVD) as a preprocessing step to MUSIC or ESPRIT algorithm with Jacobi's iterative method is used as an important example as the convergence of this method is extremely robust to modifications of the processor elements [3–6]. In [7], it was shown that Brent-Luk-EVD architecture with a modified CORDIC for performing the plane rotation of the Jacobi algorithm can be realized in advanced VLSI design. Based on it, a Jacobi EVD array is realized by implementing a scaling-free microrotation CORDIC ( -CORDIC) processor in this paper, which only performs a predefined number of CORDIC iterations. Therefore, the size of the processor array can be reduced for implementing a large-scale EVD array in parallel VLSI architectures. After that, several modifications of the algorithm/processor are studied and their impact on the design criteria is investigated for different sizes of EVD array ( to ). Finally, a
References
[1]
S. Aggarwal and K. Khare, “CORDIC-based window implementation to minimise area and pipeline depth,” IET Signal Processing, vol. 7, no. 5, pp. 427–435, 2013.
[2]
H. M. Ahmed, J. Delosme, and M. Morf, “Highly concurrent computing structure for matrix arithmetic and signal processing,” IEEE Computer Magazine, vol. 15, no. 1, pp. 65–82, 1982.
[3]
A. Ahmedsaid, A. Amira, and A. Bouridane, “Improved SVD systolic array and implementation on FPGA,” in Proceedings of the IEEE International Conference on Field-Programmable Technology, pp. 3–42, 2003.
[4]
R. Andraka, “Survey of CORDIC algorithms for FPGA based computers,” in Proceedings of the ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays (FPGA '98), pp. 191–200, February 1998.
[5]
I. Bravo, P. Jiménez, M. Mazo, J. L. Lázaro, and A. Gardel, “Implementation in FPGAS of Jacobi method to solve the eigenvalue and eigenvector problem,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '06), pp. 1–4, Madrid, Spain, August 2006.
[6]
R. P. Brent and F. T. Luk, “The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays,” SIAM Journal on Scientific and Statistical Computing, vol. 6, no. 1, pp. 69–84, 1985.
[7]
G. H. Golub and C. F. van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, Md, USA, 3rd edition, 1996.
[8]
J. G？tze and G. J. Hekstra, “An algorithm and architecture based on orthonormal μ-rotations for computing the symmetric EVD,” Integration, the VLSI Journal, vol. 20, no. 1, pp. 21–39, 1995.
[9]
J. G？tze, S. Paul, and M. Sauer, “An efficient Jacobi-like algorithm for parallel eigenvalue computation,” IEEE Transactions on Computers, vol. 42, no. 9, pp. 1058–1065, 1993.
[10]
A. Hakkarainen, J. Werner, K. R. Dandekar, and M. Valkama, “Widely-linear beamforming and RF impairment suppression in massive antenna arrays,” Journal of Communications and Networks, vol. 15, no. 4, pp. 383–397, 2013.
[11]
S. Klauke and J. G？tze, “Low power enhancements for parallel algorithms,” in Proceedings of the IEEE International Symopsium on Circuits and Systems, pp. 234–237, 2001.
[12]
Y. Liu, C.-S. Bouganis, and P. Y. K. Cheung, “Hardware architectures for eigenvalue computation of real symmetric matrices,” IET Computers and Digital Techniques, vol. 3, no. 1, pp. 72–84, 2009.
[13]
P. K. Meher and S. Y. Park, “CORDIC designs for fixed angle of rotation,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 2, pp. 217–228, 2013.
[14]
K. K. Parhi and T. Nishitani, Digial Signal Processing for Multimedia Systems, Marcel Dekker, 1999.
[15]
S. Purohit and M. Margala, “Investigating the impact of logic and circuit implementation on full adder performance,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 20, no. 7, pp. 1327–1331, 2012.
[16]
B. Ramkumar and H. M. Kittur, “Low-power and area-efficient carry select adder,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 20, no. 2, pp. 371–375, 2012.
[17]
F. Rusek, D. Persson, B. K. Lau et al., “Scaling up MIMO: opportunities and challenges with very large arrays,” IEEE Signal Processing Magazine, vol. 30, no. 1, pp. 40–46, 2013.
[18]
C.-C. Sun and J. G？tze, “VLSI circuit design concept for parallel iterative algorithms in nanoscale,” in Proceedings of the 9th International Symposium on Communications and Information Technology (ISCIT '09), pp. 688–692, Icheon, Republic of Korea, September 2009.
[19]
J. S. Walther, “A unified algorithm for elementary functions,” in Proceedings of the Spring Joint Computer Conference, pp. 379–385, 1971.
