TWO JAPANESE APPROACHES TO INTRODUCTION CIRCUIT SIMULATION We review research at Toshiba in vectorizing the circuit simulation Circuit simulation is heavily used in electronic design. It allows engineers to evaluate and alter design parameters to obtain high performance or cost effective utilization of parts. One of its most important applications is in the design of memory chips, because it is the only way that chip designers can study variations in metal oxide semiconductor (MOS) transistors. Naturally, the more detailed the design, the more computationally intensive the simulation. Even on supercomputers such as Cray, simulations can take hours, as it is often necessary to repeat computations with various parameter values. Since these simulations are done frequently, it is not surprising that large electronics companies are engaged in a variety of research to improve their simulation algorithms with respect to computer time, accuracy, and other performance characteristics. This report describes two different approaches taken by NEC and Toshiba, both large Japanese firms with substantial circuit design requirements. The authors of this report are numerical analysts, not circuit designers or computer architects, and the article reflects this orientation. by Toshiba's approach was developed by Iain S. Duff and David K. Kahaner Yoshinari Fukui Fukui begins with the well known program SPICE 2G6 (Ref 1) and rewrites it for Cray X/MP and Y/MP computers. He reports performance gains of up to 300 (see below) compared to old versions of public domain SPICE. Toshiba does not manufacture a supercomputer, but they have a great many circuit design problems that are usually run on one of their Crays. Fukui's work has already paid off for Toshiba, as the code is being used by engineers as a production tool. Nakata essentially rewrites the circuit simulation algorithms from scratch and runs them on a specially designed 64-node multiprocessor. He feels that vectorization has only limited potential for speed improvements and that the rate of vectorization will decrease as more detail is added to the circuit models because of growing numbers of conditional statements. The NEC project is the more experimental of the two but has the potential for greater payoffs in the future. On two models of dynamic random access memory (DRAM) circuits, Nakata reports parallel speedups of over 20 with 64 processors; he feels, however, that he can increase that by future improvements (see below). As a very large electronics organization, NEC has many circuit design problems. One of the specially NEC's work is spearheaded by the designed circuit simulation machines following researchers: has been installed in NEC's VLSI CAD Engineering Division. Toshiyuki Nakata C&C Systems Research Laboratories NEC Corporation 4-1-1 Miyazaki, Miyamae-ku Kawasaki, Kanagawa 213, Japan NAKATA@CSL.CS.NEC.CO.JP (044) 856-2127, Fax: 81-44-856-2231 Norio Tanabe VLSI CAD Engineering Div. NAKATA@CSL.CL.NEC.CO.JP The description and comments about these projects are based upon discussions with Fukui and Nakata, as well as reviews of published papers and preprints. In all cases we asked not to be told about any confidential activities. BRIEF REVIEW OF CIRCUIT SIMULATION The circuit to be modeled is specified by describing its components and their connectivity. Kirchoff's current and voltage laws are used to make statements about conservation and total current flow. These laws are static, that is, they hold at all times. In addition, there are equations describing the time rate of change of circuit voltage and current, due to conductance, capacitance, and inductive effects. The result is that circuit voltage and current are specified as the solution of a system of ordinary differential equations, Ay' = f where A is a large, sparse (many zero entries) matrix determined by the physical structure of the circuit. This system of differential equations must be solved to determine the evolving characteristics of the circuit. The equations are known to be "stiff" because of the large circuit time-constants, and hence can only be solved by special techniques. In particular, it is necessary to use implicit integration, such as backward Euler, or higher order backward differentiation (Gear) methods (Ref 2). This eventually results in a system of nonlinear equations to be solved for the solution y at each time step. The solution of these equations is done by iteration, usually employing Newton's method. At every time step, each iteration requires the solution of a system of linear equations. The matrix of the linear equations is formed by adding the identity to a scalar multiple of the Jacobian matrix. The latter is the matrix of partial derivatives of the right-hand side of the differential equations, denoted f above. Thus, the essential ingredients in performing transient circuit simulation analysis are (a) Setting up the problem. This includes formulating the matrix. It also includes computing equivalent conductances and current sources for linear reactive circuit elements. (b) Integration, including error con- (c) Solving the nonlinear equations operations as possible in parallel or in In practice, deriving the Jacobian matrix Many portions of the overall computation can be performed in parallel, in particular, the setup or assembly phase. Often the circuit is partitioned into subcircuits, each of which is independently calculated, with an iteration until the various parts converge. This is often called a "relaxation algorithm" (Ref3). However, if there is substantial feedback between circuit parts, convergence may not occur. Another approach is to subdivide the circuit but force the subcircuits to interact via a network whose parameters are determined anew at each iteration. Nakata calls this "modular simulation" (Ref 4). SPEEDING UP The two major approaches to increasing the performance of circuit simulation programs are (1) to take advantage of the partitioning suggested by the physical circuit in order to perform certain functions in parallel, and (2) to take advantage of the structure of the Jacobian matrix to perform as many Nakata and Tanabe have concentrated on rearranging the circuit simulation algorithm to take advantage of those aspects of it that have inherent parallelism. They have designed the algorithm to allocate subcircuits to different processors, each of which independently performs a simulation using local memory. The determination of the interconnection between various subcircuits must be performed, serially, at every iteration by one “interconnection" processor. This processor is locked until all the subcircuits are finished. The actual algorithm is recursive, so there is a tree of such processors. The essential function of the interconnection processor is to solve a system of linear equations. The size of the interconnection matrix is determined by the number of interconnections. For |