DC Large-Scale Simulation of Nonlinear Circuits on Parallel Processors

• Autorzy: Udave D. E. C. , Ogrodzki J. , de Anda G. M. A.
• Języki publikacji: EN

Abstrakty

EN

Newton-Raphson DC analysis of large-scale nonlinear circuits may be an extremely time consuming process even if sparse matrix techniques and bypassing of nonlinear models calculation are used. A slight decrease in the time required for this task may be enabled on multi-core, multithread computers if the calculation of the mathematical models for the nonlinear elements as well as the stamp management of the sparse matrix entries is managed through concurrent processes. In this paper it is shown how the numerical complexity of this problem (and thus its solution time) can be further reduced via the circuit decomposition and parallel solution of blocks taking as a departure point the Bordered-Block Diagonal (BBD) matrix structure. This BBD-parallel approach may give a considerable profit though it is strongly dependent on the system topology. This paper presents a theoretical foundation of the algorithm, its implementation, and numerical complexity analysis in virtue of practical measurements of matrix operations.

Słowa kluczowe

EN

circuit simulation; parallel computation; DC analysis; circuit decomposition

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2012
• Tom: Vol. 58, No. 3
• Strony: 285--295
• Opis fizyczny: Bibliogr. 31 poz., wykr.

Twórcy

autor

Udave D. E. C.

autor

Ogrodzki J.

autor

de Anda G. M. A.

• Instituto Nacional de Astrofisica, Óptica y Electrónica, Calle Luis Enrique Erro 1, Santa Maria Tonantzintla, C. P. 72840 San Andres Cholula, Puebla, Mexico,

Bibliografia

• [1] K. A. Gallivan, M.-C. Chang, I. N. Hajj, D. Smart, and T. N. Trick, “Parallel circuit simulation on supercomputers,” Proceedings of theIEEE, vol. 77, no. 12, pp. 1915-1931, 1989.
• [2] M. Günther, U. Feldmann, and J. ter Maten, “Modelling and discretization of circuit problems,” in Handbook of Numerical Analysis:Numerical Methods in Electromagnetics, W. H. A. Schilders and E. J. W. ter Maten, Eds. Amsterdam, The Netherlands: Elsevier Science, 2005, pp. 523-659.
• [3] X. Ye, W. Dong, P. Li, and S. Nassif, “Hierarchical multialgorithm parallel circuit simulation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 1, pp. 45-58, 2011.
• [4] E. R. Keiter, H. K. Thornquist, R. J. Hoiekstra, T. V. Russo, R. L. Schiek, and E. L. Rankin, “Parallel transistor-level circuit simulation,” in Simulation and Verification of Electronic and Biological Systems, P. Li, L. M. Silveira, and P. Feldmann, Eds. Heidelberg, Germany: Springer, 2011, pp. 1-21.
• [5] H. K. Thornquist and E. R. Keiter, “Advances in parallel transistor-level circuit simulation,” in Scientific Computing in Electrical Engineering SCEE 2010, B. Michielsen and J.-R. Poirier, Eds. Heidelberg, Germany: Springer, 2012, pp. 257-265.
• [6] C. Baker, E. Boman, M. Heroux, E. Keiter, S. Rajamanickam, R. Schiek, and H. Thornquist, “Enabling next-generation parallel circuit simulation with Trilinos,” in Euro-Par 2011: Parallel Processing Workshops, M. Alexander, P. D’Ambra, A. Belloum, G. Bosilca, M. Cannataro, M. Danelutto, B. D. Martino, M. Gerndt, E. Jeannot, R. Namyst, J. Roman, S. Scott, J. L. Traff, G. Valle, and J. Weidendorfer, Eds. Heidelberg, Germany: Springer, 2012, pp. 315-323.
• [7] H. Quian, Y. Deng, B. Wang, and S. Mu, “Towards accelerating irregular EDA applications with GPUs,” Integration, the VLSI Journal, vol. 45, no. 1, pp. 46-60, 2012.
• [8] T.-H. Weng, R.-K. Perng, and K.-C. Li, “On parallelization of circuit simulation SPICE3 using multithreaded programming techniques,” Journal of the Chinese Institute of Engineers, vol. 35, no. 2, pp. 259-267, 2012.
• [9] W. Ho Chung, D. A. Zein, A. E. Ruehli, and P. A. Brennan, “An algorithm for DC solution in an experimental general purpose interactive circuit design program,” IEEE Transactions on Circuits and Systems, vol. 24, no. 8, pp. 416-421, 1977.
• [10] D. A. Zein, “Solution of a set of nonlinear algebraic equations for general purpose CAD programs,” in Circuit analysis simulation and design. General aspects of circuit analysis and design, A. E. Ruehli, Ed. Amsterdam-New York-Oxford-Tokyo: North Holland, 1986.
• [11] J. Ogrodzki, Circuit simulation methods and algorithms. Boca Raton-New York-Tokyo: CRC Press, 1995.
• [12] J. M. Orthega and W. C. Rheinboldt, Iterative solution of Nonlinear Equations in several variables. New York: Academic Press, 1970.
• [13] J. I. Aliaga, M. Bollh¨offer, A. F. Martn, and E. S. Quintana-Orti, “Exploiting thread-level parallelism in the iterative solution of sparse linear systems,” Parallel Computing, vol. 37, no. 3, pp. 183-202, 2011.
• [14] H. Huang, L. Wang, E. J. Lee, and P. Chen, “An MPI-CUDA implementation and optimization for parallel sparse equations and least squares (LSQR),” Procedia Computer Science, vol. 9, pp. 76-85, 2012.
• [15] Y. Wang and H. Yang, “An adaptive LU factorization algorithm for parallel circuit simulation,” in Proceedings of 17Th Asia and South Pacific Design Automation Conference, 2012, pp. 359-364.
• [16] N. Rabbat, A. Sangiovanni-Vincentelli, and H. Hsieh, “A multilevel Newton algorithm with macromodeling and latency for the analysis of large-scale nonlinear circuits in the time domain,” IEEE Transactions on Circuits and Systems, vol. 26, no. 9, pp. 733-741, 1979.
• [17] N. Frohlich, B. M. Riess, U. A. Wever, and Q. Zheng, “A new approach for parallel simulation of VLSI circuits on a transistor level,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 45, no. 6, pp. 601-613, 1998.
• [18] M. Honkala, J. Roos, and M. Valtonen, “New multilevel Newton-Raphson method for parallel circuit simulation,” Proceedings of European Conference on Circuit Theory and Design, vol. 1, pp. 113-116, 2001.
• [19] J. G. Fijnvandraat, S. H. M. J. Houben, E. J. W. ter Maten, and J. M. F. Peters, “Time domain analog circuit simulation,” Journal of Computational and Applied Mathematics, vol. 185, no. 2, pp. 441-459, 2006.
• [20] F. F. Wu, “Solution of large scale networks by tearing,” IEEE Transactions on Circuits and Systems, vol. 23, no. 12, pp. 706-713, 1976.
• [21] M. Vlach, “LU decomposition and forward-backward substitution of recursive bordered block diagonal matrix,” in Proceedings of the IEEE International Symposium on Circuits and Systems, 1983, pp. 701-703.
• [22] D. Bukat, G. Centkowski, and J. Ogrodzki, “OPTIMA-1.1 - A hierarchical decomposition based analyser including user defined models,” in Proceedings of the European Conference on Circuit Theory and Design, 1991.
• [23] D. E. C. Udave, J. Ogrodzki, and M. A. G. de Anda, “A study of the parallel algorithm for DC large-scale simulation of nonlinear systems,” in Photonics Application in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2012, R. S. Romaniuk and K. S. Kulpa, Eds., 2012, Proceedings of SPIE, vol. 7503 (SPIE, Bellingham, WA).
• [24] D. E. C. Udave, J. Ogrodzki, and M. A. G. de Anda, “DC simulator of large-scale nonlinear systems for parallel processor,” in Photonics Application in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2012, R. S. Romaniuk and K. S. Kulpa, Eds., 2012, Proceedings of SPIE, vol. 7503 (SPIE, Bellingham, WA).
• [25] T. A. Davis and E. P. Natarajan, “Algorithm 907: KLU, a direct sparse solver for circuit simulation problems,” ACM Transactions on Mathematical Software, vol. 37, no. 3, 2010.
• [26] T. A. Davis, “Direct methods for sparse linear systems,” in SIAM Book Series on the Fundamentals of Algorithms. Philadelphia: SIAM, 2006.
• [27] K. Stanley, “KLU: a “Clark Kent” sparse LU factorization algorithm for circuit matrices,” in SIAM Conference on Parallel Processing for Scientific Computing (PP04), 2004.
• [28] SYNOPSYS ®, [HSPICE ®Reference Manual: Commands and Control Options], ver. A-2007.09, September (2007).
• [29] J. Levine, Flex & Bison. California: O’Reilly Media, 2009.
• [30] C. Van Reeuwijk, “Tm: a code generator for recursive data structures,” Software - Practice and Experience, vol. 22, no. 10, pp. 899-908, 1992.
• [31] “Intel ®Parallel Studio XE 2011 for Linux* - Documentation,” 20 June 2012, http://software.intel.com/en-us/articles/intel-parallel-studio-xe-forlinux-documentation/#inspector.