Integrative, Hybrid and Complex Systems Purdue University Dan Jiao CAREER: From O(N) to O(M): Scalable Algorithms for Large Scale Electromagnetics-Based Analysis and Design of Next Generation VLSI Circuits
Intellectual Merit: As on-chip design scales into the nanometer regime, full-wave electromagnetics (EM) analysis has increasingly become essential due to reduced feature sizes that lead to subwavelength optical lithography, increased clock frequency, the transition from single core to multicore, and increased levels of integration. However, the design of next-generation integrated circuits results in numerical problems of very large scale, requiring billions of parameters to describe accurately. State-of-the-art EM analysis algorithms require computation and memory that scales with N, the number of unknowns. This research focuses on reducing the complexity of required computation and memory to scale with M, the number of design decision parameters, which is a much smaller value than the number of unknowns. This reduction in complexity is required to enable the EM analysis of next-generation very large-scale integrated (VLSI) circuits. Instead of solving the original matrix of O(N) as it is, we construct a reduced matrix that involves only the O(M) parameters needed for the circuit design decision, while incorporating the effects of other parameters. Moreover, the original and reduced system matrices possess, or can be formulated to possess, special structure, for example a sparse banded structure. The structure will be explored or created to reduce the complexity of the reduction and the solution of the reduced system matrix under the framework of semi-separable matrices.
Broader Impact: The project's education objectives are to effectively bridge the education in fields with that in circuits and to effectively introduce the human dimension into the integrated circuit-field education. Three education programs will be developed: (i) an undergraduate course in "Circuits and Fields," (ii) a graduate "High-Frequency Computer-Aided Design Studio," and (iii) a "Working-with-Differences Learning Community." Assessment tasks will evaluate the effectiveness of these programs. This research has the potential to contribute significantly to solving scalability problems with existing computational EM techniques for integrated circuit design. In addition, it has the potential to benefit a wide range of engineering applications in which large problem sizes are a bottleneck in preventing the successful design and analysis of advanced system
As on-chip design scales into the nanometer regime, full-wave electromagnetics (EM)-based analysis has increasingly become essential for four main reasons: (1) reduced feature sizes that lead to subwavelength optical lithography, (2) increased clock frequency, (3) the transition from single core to multicore, and (4) increased level of integration. However, the design of next-generation ICs results in numerical problems of very large scale, requiring billions of parameters to describe them accurately. State-of-the-art computational EM algorithms require O(N) or O(NlogN) computation with O(N) memory (N being the number of unknowns). This represents an impressive improvement as compared with conventional techniques. However, for the next generation VLSI design problem, even O(N) is prohibitively expensive. In addition, the current IC design community lacks the workforce well-equipped with the knowledge, ability, and skills in both circuits and fields. Therefore, in order for the VLSI revolution to continue uninterrupted, it is incumbent on the academy to develop algorithms of reduced complexity to overcome the large problem size as well as to educate a new generation of IC engineers with a strong background in both circuits and fields. In this research, we have overcome the large problem size of O(N) to achieve a complexity of O(M), with M<<N, in a rigorous fashion. Three classes of fast "from O(N) to O(M)" algorithms have been successfully developed . They have also been applied to solve difficult design problems encountered in very large-scale IC design in the full electromagnetic spectrum. This career project will go a long way towards addressing the scalability issue of existing computational EM techniques. In addition to IC design, it has the potential to benefit a wide range of engineering applications in which the large problem sizes have been the bottleneck preventing the successful design of advanced systems. It has enriched society and advanced engineering (1) by educating a new generation of engineers with solid knowledge, ability, and skills in both circuits and fields to drive the continual VLSI revolution; (2) by actively engaging women and under-represented minorities and developing outreach programs; (3) and finally, by sharing and disseminating knowledge and expertise within and outside the VLSI and EM community.
