Presented by
M.V.SUBBA LAKSHMI
B.MOUNIKA

---

[attachment=10321]
A VLSI DESIGN CONCEPT FOR PARALLEL ITERATIVE ALGORITHMS
Abstract:
Modern VLSI manufacturing technology has kept shrinking down to the nanoscale level with a very fast trend.
Integration with the advanced nano-technology now makes it possible to realize advanced parallel iterative algorithms directly which was almost impossible 10 years ago. In this paper,
we want to discuss the influences of evolving VLSI technologies for iterative algorithms and present design strategies
from an algorithmic and architectural point of view. Implementing an iterative algorithm on a multiprocessor array,there is a trade-off between the performance/complexity of processors and the load/throughput of interconnects. This is due to the behavior of iterative algorithms. For example, we could simplify the parallel implementation of the iterative algorithm(i.e., processor elements of the multiprocessor array) in any way as long as the convergence is guaranteed. However, the modification of the algorithm (processors) usually increases the number of required iterations which also means that the switch activity of interconnects is increasing. As an example we show that a 25×25 full Jacobi EVD array could
be realized into one single FPGA device with the simplified μ-rotation CORDIC architecture.
1 Introduction
Modern VLSI manufacturing technology has kept shrinking down to Deep Sub-Micron (DSM) with a very fast trend
and Moore’s law is expected to hold for the next 10 years (Gelsinger, 2008). Now, since the DSM nano-technology allows the integration of an ever-increasing number of IP macro-cells on a single silicon die, parallel multiprocessor platforms have received great attention and have been realized into several state-of-the-art applications (e.g., Dual-Core CPU, MPSoC and Parallel Computing) (Vangal et al., 2007; Wolf, 2004; Vitullo et al., 2008). 10 years ago, for 0.35μm technology, design engineers were focusing on reducing the area size. Later, when it came Correspondence to: C. C. Sun to 0.13μm technology they paid huge efforts to improve the signal delay and reduce the power consumption. As the VLSI
manufacturing technology keeps shrinking down into 65 nm,the design methodology for nano-circuits poses new challenges: area requirements of the wire interconnections are increasing explosively in relation to the area of processor elements, bus transmission bottleneck in the million transistors SoC designs, and leakage current is now dominating the
power consumption (Sainarayanan et al., 2007; Stine et al.,2007). These changes bring us to analyze the impacts on parallel iterative algorithms as VLSI technology keeps evolving. As long as the convergence properties of the iterative algorithms are guaranteed, it is possible to modify/simplify the architecture during the iteration steps and reduce the computational complexity significantly with regard to the implementation.
However, this simplification will usually cause an increased number of iterations for convergence. Therefore, it actually becomes a trade-off problem between the performance/ complexity of the hardware, the load/throughput of interconnects and the overall energy/power consumption due
to the behavior of parallel iterative algorithms.Computing the Eigenvalue Decomposition (EVD) with the parallel Jacobi method is used as an example since the convergence of this methodology is very robust to modification of the processor elements. Finally, a VLSI design concept for parallel iterative algorithms is presented which takes into account the influence of the modifications on area, timing delay and power consumption.The paper is organized as follows: in Sect. 2 we will first describe the design concepts for parallel iterative algorithms. After that, we will further clarify the definition of the serial and parallel Jacobi method, respectively, in Sect. 3. Then,in Sect. 4 the design issues of the Jacobi EVD array and
their suitability for different hardware implementations are discussed, which lead to the simplified μ-rotation CORDIC
processor. Section 5 shows the experimental and syntheses results. Section 6 concludes this paper.Published by Copernicus Publications on behalf of the URSI Landesausschuss in der Bundesrepublik Deutschland e.V. 96 C. C. Sun and J. G¨otze: A VLSI design concept for parallel iterative algorithms
2 Design concept and implementation issues
A design concept for parallel iterative algorithms, is presented taking into consideration the influences of different
VLSI technologies in terms of area, power and timing delay.Implementing an iterative algorithm on a multiprocessor array, there is a trade-off between the complexity of an iteration step (assuming that the convergence of the algorithm is retained) and the number of required iteration steps. For example,suppose we have a hardware platform, which requires an iteration step of the iterative algorithm to be executed K times in order to obtain the convergence.The iteration step is executed in parallel on the platform. If we simplify the processors in order to improve the logical utilization of the platform, the number of required iterations usually increase from K to K+L. It also means that the switch activity of interconnects between these processor elements is increasing due to the behavior of iterative algorithm. How to find a superior solution to balance the design criteria is the major
issue of this paper, especially for low-power or limited-area devices. In this paper, we selected the Jacobi EVD method as a typical iterative algorithm since the convergence of this methodology is very robust to modification of the processor elements (Brent and Luk, 1985; Gotze et al., 1993; Goetze and Hekstra, 1995; Klauke and Goetze, 2001). We have investigated the influences in DSM design with different sizes of multiprocessor
arrays (i.e., 4×4, 16×16 and 25×25). After that, several modifications of the algorithm/processor were studied
and their impacts on different FPGA devices were investigated (e.g., Xilinx Virtex series in 0.22μm, 0.15μm and
65 nm). According to these analyses, we present an efficient strategy to comply with the design criteria, especially in balancing the number of iterations and the computational complexity.
3 Eigenvalue decomposition
An Eigenvalue decomposition of a real symmertric n×n matrix A is obtained by factorizing A into three matrices
A=Q ^ QT , where Q is an orthogonal matrix (QQT=I ) and ^ is a diagonal matrix which contains the eigenvalues of
A.