Vlsi structures and iterative analysis for large scale computation
Elena P. Papadopoulou · 1986
Problems of computation and development of VLSI structures are considered in relation to each other. In particular, two issues are addressed: (a) The development of components and algorithms for standard operations, suitable for VLSI implementation. (b) Large-scale computation, in our case the iterative solution of large least-squares problems, in a limited size VLSI architecture. On the subject of standard operations improved and new adders are presented that can be implemented in VLSI. The adders so designed are shown to be superior when compared to other existing ones. Moreover, an iterative multiplier that uses carry save adders is also presented. On the subject of large-scale computation the analysis of iterative techniques for least-squares problems is first addressed. New convergence results are obtained and explicit expressions, for the optimal parameters as well as for their corresponding optimal asymptotic rate of convergence are derived for the family of iterative schemes known as Accelerated Overrelaxation (AOR). Further, a new iterative scheme is determined which, for a class of least-squares problems, achieves the fastest known rate of convergence. Moreover, on the same subject, partitioning of our iterative algorithm and time-space expansion are used so that a parallel implementation of the iterative scheme is obtained, in a way that computation can be performed, in a fixed size VLSI architecture, independent of the size of the problem. For that purpose a new matrix-vector multiplication unit is introduced and a fixed size VLSI structure is presented, for performing one step of the iteration process.