IEEETRANSACTIONSONCIRCUITSAND SYSTEMS,VOL.CAS-3l;NO.

l,JANUARY1984 103

[2691 ?95:, Besicovitch, Almost Periodic Functions. New York: Dover, Irwin W. Sandberg (S’54-M’SS-SM’73-F’73)
was born in Brooklyn, NY, on January 23,1934.
~2701 I. W. Sandberg, “Volterra-like expansions for solutions of nonlin- He received the B.E.E., M.E.E., and D.E.E., de-
ear integral equations and nonlinear differential equations,” IEEE grees from the Polytechnic Institute of Brooklyn,
Trans. Circuits Syst., vol. CAS-30, Feb. 1983. Brooklyn, NY, in 1955, 1956, and 1958, respec-
12711 7’ “Theorems on the computation of the transient responseof
nonlinear networks containing transistors and diodes,” Bell Syst. tively (Westinghouse Fellow 1956, Bell Tele-
Tech. .I., vol. 49, pp. 1739-1776, Oct. 1970. phone Laboratories Fellow 1957-1958).
~2721 E. B. Lee and L. Markus, Foundations of Optimal Control Theory. Since 1958 he has been employed by Bell
New York: Wiley, 1968. Laboratories, Murray Hill, NJ, where he pre-
WI I. W. Sandberg and A. N. Willson, Jr. “Some theorems on proper- sently is a Distinguished Member of Technical
ties of DC equations of nonlinear networks,” Bell System Tech. J., Staff in the Mathematics and Statistics Research
vol. 48, pp. l-34, Jan. 1969. Center. He has been concerned with analysis of radar systemsfor military
12741 Widrow, J. M. McCool, M. G. Larimore, and R. J. Johnson, Jr.,
B. defense, synthesis and analysis of active and time-varying networks, with
“Stationary and nonstationary learning characteristics of the LMS
adaptive filter,” Proc. IEEE, vol. 64, pp. 1151-1162, Aug. 1976. several studies of properties of nonlinear systems, and with some prob-
WI R. F. Brown, Compartmental system analysis: State of the art,” lems in communication theory and numerical analysis. His more recent
IEEE Trans. Biomed. Eng., vol. 27, pp. l-11,, Jan. 1980. interests have included compartmental models, the theory of digital
[2761 M. Zakai, ‘I On the optimal filtering of diffusion processes,”Z. jtir filtering, global implicit-function theorems, and functional expansions for
Wahrscheinlichkeitstheorieund uenv. Geb., vol. 11, pp. 230-243, nonlinear systems. He is a former Vice Chairman of the IEEE Group on
1969. Circuit Theory, and a former Guest Editor of the IEEE TRANSACTIONSON
P771 V. E. Benei, “Exact finite dimensional filters for certain diffusions CIRCUIT THEORY Special Issue on Active and Digital Networks.
with nonlinear drift,” Stochastics,vol. 5, p . 65-92, 1981. Dr. Sandberg is a member of the American Association for the Ad-
[2781 D. J. Hill and P. J. Moylan, “Gener 2 instability results for vancement of Science, Eta Kappa Nu, Sigma Xi, Tau Beta Pi, and the
interconnected systems,” SIAM J. Contr. Opt., vol. 21, no. 2, pp.
256-279, Mar. 1983. National Academy of Engineering.

A Historical Review of Circuit Simulation

DONALD 0. PEDERSON, FELLOW, IEEE

Absrracr-Within the Circuits and Systems (CAS) Society, develop- I. INTRODUCTION

ments in computer-aided circuit analys/s and circuit design commenced in
VER TWO-THIRDS of the IEEE’s first century had
the early 1950’s using the earliest digital computers. Initially,
computer-aidedcircuit analysis of linear circuits was used in design optimi-
zation, design centering, and in determining the effects of parasitics on
0
passed before the digital computer was used in the
analysis of electrical circuits. A computer consisting of
circuit performance. Although this use of computer-aided circuit analysis
electromechanicalrelays was programmed in the very early
has continued, computer-aideddesign (CAD) and circuit design automation
within the CAS Society are now principally concerned with problems 1950’s to solve the algebraic equilibrium-condition equa-
tions of a linear electrical network in the sinusoidal steady
associatedwith the overall design and evaluation of very large circuits and
systems. state [23]. With “rapid” analysis available, it was possible
This paper is a review of a major thread of CAD activity which hasto employ optimization techniques to achieve excellent
occurred within CAS from the earliest and remains of major interest. This
designs of electric filters [l]. From this relatively late start
thread involves computer-aided circuit analysis (circuit simulation) and its
use in CAD systems. Fortunately, several excellent review papers havefrom the standpoint of digital computers, there has been a
appeared within the past year or two to document well the technical steadily increasing use of computers in the analysis, evalua-
tion and testing of electric and electronic circuits and
milestones, as well as the problems of interest at the present time. It is
possible then, in this paper, to concentrate on the developments in our
systems.
present capability of circuit simulators, stressing the significant trends,
noting some early developmentswhich did not become major aspects,and
The phrase that best characterizesthe circuits and sys-
observing the interchange between theory and practice. tems of today is large scale. To illustrate the large-scale
problem, consider today’s very-large-scale-integrated
Manuscript received September 6, 1983. (VLSI) circuit [16], [39], which may consist of hundreds of
The author is with the Department of Electrical Engineering and thousands of separatecomponents, principally transistors.
Computer Sciencesand the Electronics Research Laboratory, University
of California, Berkeley, CA 94720. In the electrical design of a VLSI circuit, in contrast to the

0098-4094/84/0100-103$01.00 01984 IEEE

104 VOL. CAS-31, NO. 1, JANUARY 1984
IEEETRANSACTIONSON CIRCUITSAND SYSTEMS,

electrochemical processing and material aspects, there is In the gate-array approach, also &led a master-slice
involvement with computer and digital system operation technique [12], circuit modules in IC are placed at specific
and design, functional, logical, electrical, and physical de- grid locations. Placementand routing programs are used to
sign, verification, and testing. One must first study the achieve the intercomrection of the modules and implement
overall function to be achievedwith respect to the required the completeIC design. A large number of commercially
data- or signal-handling process and to partition the func- available designsystemsare now available for the gate-array
tion into smaller entities. Next, each subfunction is de- technology. The standard-cell and gate-array design meth-
signed to achieve the logic requirements. At the electrical odologies are often referred to as semi-customdesign meth-
level, a sequenceof designsof small segmentsis made with ods.
particular attention to the electrical interaction of these At many locations, both industrial and academic,circuit
parts. This is followed by the physical design, i.e., the and system researchershave attacked the PCB and IC
actual layout, of the patterns of metal, semiconductor, and placement and routing problem and have contributed sig-
insulating material by which the components and the inter- nificant results. The interested reader is referred to an
connections are achieved. At each step of the design pro- excellent review article on layout by Soukup [70]. In a
cess, procedures (computer aids) must be developed to recent paper, Newton has examined the broad range of
achieve verification of the electrical, logic, and functional layout problems for VLSI circuits [54].
behaviors of the segments.Computer aids are also critical
in devising test sequencesin terms of electrical and logical
input sequencesto assurethat the circuit as manufactured II. EARLYTHEORETICAL,ALGORITHMIC,AND
is performing as designed. PROGRAMDEVELOPMENTS
Many of these design and evaluation activities are or As mentioned above, from the early 1950’s, circuit and
have become the province of other IEEE Societies. It is system researchershave always been interested in the theo-
possible then to restrict the scope of this paper to a topic retical problems of computer-aided circuit analysis, optimi-
which has always been central to the CAS Society, viz., zation, and automated design, In many cases,results from
computer-aided circuit analysis, now referred to as circuit applied mathematical physics and mathematics have been
simulation. identified and used to advantage.
Many excellent review papers have recently appearedon The problem of the “best” way to formulate circuit
circuit simulation, cf., [26] and optimization [8], [59], which equations had to be addressedearly. The common mesh-
are major topics of interest within the CAS Society, as well equation formulation was not well suited for evaluation
as on logical and functional design and testing which with the digital computer of those days. The capacitive
appear in other journals of the IEEE. An excellent tutorial elements as well as the high-resistance sources were
introduction to circuit simulation is also available [66]. The troublesome with this formulation. In early work, Bashkow
main focus of this paper is the history of the computer-aided looked at alternate forms of a complete description of an
analysis of electronic circuits. The principal sections of this electrical network and devised the A matrix [2]. This in
paper constitute the author’s overview of the emergenceof part emanated out of his studies of dynamical systems as
circuit simulation with particular attention to severalof the described in Whittaker and Watson. The A matrix is
critical decisions and developmentswhich had to be made. widely accepted as the forerunner of the state-variable
Because of the CAS Society interest, a short section is description of an electrical network and was used in the
included on the topic of optimization. early years of CAD as the basis of equation formulation in
Within CAS, another significant research interest con- CAD programs [38]. With subsequentdevelopments,how-
cerns graphs and graph theory. The researchersin this area ever, it became clear that the state-variable approach,
have seen application possibilities in the placement and although very significant for theoretical studies, is not the
routing programs for printed circuit PC boards and now best basis for computer programs for circuit analysis. As
ICs. Placement and routing techniques for ICs have been brought out below, the modified-nodal and sparse-tableau
based upon the use of “standard cells” and “gate arrays.” formulations are better. For one who has observed the
For the former, sets of basic circuits (building blocks) of developments in this field throughout the 30 years of its
standard height and various widths are predesigned elec- existence,the fierce disagreementsof just ten years ago on
tronically and physically. Each block accomplishes a this subject make for interesting and frustrating memories.
sp,ecificelectronic or logical function. These standard cells A decadeafter the first use of relay digital computers for
are placed or fixed on avenues with routing channels circuit analysis, one of our first CAD experts, the late
between the avenues.The problem, then, is to choose the Frank Branin, came into our field from chemistry. He was
best location for each standard cell on the best avenueand interested both in the description of large electrical net-
then to route the interconnections between the cells. Feller works and also how computer programs can be written in
(of RCA, with the MP2D program and its predecessors) such a way to achieve adequatecomputer analysis [7]. His
was one of the first to produce a workable system, one first efforts led to the Program TAP [4]-[6], [9]. Becauseof
which is still in use [21]. Similarly, Gummell and his staff the inevitable problems with a new software system, TAP
achieved a successful system at Bell Labs-the LTX sys- was never released into the public domain. Nonetheless,
tem [57], [58]. TAP formed the basis for two very important early CAD
PEDERSON: HISTORICAL REVIEW OF CIRCUIT SIMULATION 105

programs, ECAPl from IBM and Norden [31] and the was difficult. The assembly language subroutines were
PREDICT program from a different division of IBM [30]. rewritten in Fortran at Berkeley in 1968-1969. Subse-
Both of these programs again suffered the usual fate of quently, a new program in Fortran based upon the same
first-generation software systems-they were hard to use, choice of techniques and algoithms was written by Jenkins
were very unfriendly, had tendenciesto nonconvergencein and Fan in 1969-1970. This work evolved into the TIME
the solution of the equations, and so forth. program at Motorola [34] and the SINC program at
The successesand failures of the first programs led to Berkeley.
new programs, in part becauseof the critical need to study At approximately the same time as the TRAC develop-
problems associatedwith radiation effects in electronics for ments, Shichman at Bell Labs [64] proposed a second-order
military systems.The PREDICT program led to SCEPTRE, implicit-integration schemethat proved very effective and
which for almost 20 years has been used successfully, produced better performance relative to the revised TRAC.
principally for aerospaceneeds[42]. Another new program The program which he wrote as a vehicle to investigate this
based on the initial efforts was Malmberg’s NET1 from the scheme was CIRPAC [68], [69]. The superiority of using
Los Alamos National Laboratory [40]. Both SCEPTRE the second-orderintegration schemewas clear. It was soon
and NET1 at that time used explicit-integration and/or evident that Gear, working with large-scale systems and
predictor-corrector techniques in the solution of the in- numerical integration techniques, had also evolved com-
tegro-differential equations of the nonlinear systems of parable backward integration schemes-variable-order,
interest. These systems were usually very stiff types with variable-timestep implicit integration routines [22].
very large numbers of widely varying eigenvaluesat any Shichman and Gear’s second-orderroutines were seen to
equilibrium point of interest. Therefore, if the computer be substantially the same. Although higher order implicit
solution was possible at all, the time consumed in the integration schemescan be used, the range of applicability
solution was extremely large becauseof the very small time is much smaller and their usehas in circuit simulation been
steps that were necessary to maintain stability of the limited.
numerical methods. Howard at Berkeley, in 1967,before the above programs
were available to him, encountered a problem with a
seemingly simple, four-transistor, nonlinear circuit which
III. IMPLICIT INTEGRATION, NODAL ANALYSTS, AND needed to be solved with respect to not only the dc state
EARLY NONLINEAR DC PROGRAMS but how it was effected by temperature.Hand analysis and
At least two independent paths of investigation arose ifi evaluation proved exhaustive. Working in an interactive
responseto the time-constant problem. At Autonetics, now mode, on what would now be considered less powerful
a division of Rockwell Corporation, a group of circuit and than a modem microcomputer, he wrote a program in
electronic device experts working with applied mathemati- terms of a set of nodal equations, modeling the transistors
cians used alternative approaches to those of the initial with a simple Ebers-Moll nonlinear model, linearitig the
CAD programs. In retrospect, one can say that a kinder- equations at the equilibrium point of interest and using
garten approach was employed. But I hasten to add that Newton-Raphson and excursion-limiting -techniques to
such an approach was not chosen becauseof naivity. In iterate to a solution. The result was the BIAS program
contrast to a state-variable formulation for electric equa- which was subsequently expanded and rewritten by
tions, a conventional, datum-node analysis technique was McCalla in 1969into the BIAS3 program [44]. This nonlin-
used. Simple circuit schemessuch as the inclusion of 1-Q ear dc program was releasedinto the public domain. It had
resistors and the use of Norton equivalents avoided prob- extensiveuse not only at Berkeley, but also at a number of
lems with floating-voltage sourcesand the like. Inductances locations on three continents. The experience with this
were either neglected or were treated separately. In addi- simple program, as well as with TRAC and CIRPAC, had
tion, a simple implicit integration scheme,the Backward- a major effect at Berkeley on the next generation of circuit
Euler Method, was used. In implicit integration, the set of simulators.
integro-differential equations become, for a time step at a
time point, a set of static algebraic equations, i.e., a set of
dc equations, the solution of which is straightforward [43]. IV. THE SPARSE TABLEAU
The program which resulted from this effort and these In contrast to ‘the developments at Berkeley in the late
decisionswas TRAC. TRAC has had an effect comparable 1960’s, which included a high component of engineering
to that of TAP; it had a large effect on subsequentcom- heuristics, an independent effort starting from a theoretical
puter-aided circuit analysis [35]. base took place at IBM Research. Hachtel and his col-
Transportability was another early recognizeddifficulty. leagues at Yorktown were aware of the difficulty of net-
TRAC did not seewide usageexcept for special aerospace work equation formulation as it applied to computer
concernsinvolved in defenseelectronic contracts. One rea- programming and developed an elegant, award-winning,
son for the limited use was the fact that the code was not complete description, called the Sparse-Tableau[25]. From
transportable to other machines; severalkey routines were the start, they neglected the usual, classical concentration
written in the assemblylanguageof a particular computer. on obtaining the most concisematrixes. Instead, they placed
Transportability to other machines, even of the same type, in evidence all element descriptions and connections in
106 VOL. CAS-31, NO. 1, JANUARY 1984
IEEETRANSACTIONSON CIRCUITSAND SYSTEMS,

elementary form, very suitable for programming, and the memory considerations and computer run time speed of
all-important aspect of the sparsity of the connection ma- the sparsity of the matrix of the linearized elementsvalues
trix. of the circuit; pivoting to maintain sparsity (usually a
Program ASTAP was developed at IBM based on the Markowitz [41] or Berry reordering [3], Newton-Raphson
sparse-tableau representationof the electrical network [32], linearization modified with excursion limiting, and LU
[74]. In addition, very sophisticated methods were included solution of the equations. Further, after very extensive use
to obtain compiled machine code for the network descrip- in instructional courses with hundreds of students and
tion in order to achieve the fast repeated analysis suitable many thousands of accesses,a hardware description lan-
for statistical analysis of the circuit as parameters and guage, i.e., an input circuit language, evolved which was
elements are changed. Variable-order, variable-step im- relatively “friendly” from the standpoint of the new user.
plicit integration schemeswere employed, as well as suit- Similarly, because batch operation was needed, and the
able methods to linearize the nonlinear equations at an fact that simple graphics were unavailable at that time,
equilibrium point.. ASTAP has come into worldwide use simple inexpensivemeanswere used to achieveline-printer
within the IBM Corporation. It has also been made avail- plots of the output response for easy evaluation of the
able for a fee outside IBM, although its usage outside of simulated circuit performance, as well as circuit and device
IBM has not been extensive primarily because of the parameter values at a chosen operating or initial point.
computer cost of simulations. With these features, the programs could be considered not
just analysis programs, but electrical circuit simulators. A
“dry lab” had been achieved.
V. MODIFIED-NODAL ANALYSIS (MNA) After very extensive use by undergraduate and graduate
In 1969-1970, Rohrer initiated a graduate student proj- students in class-assignedproblem sets, the CANCER pro-
ect, with approximately ten students, into the investigation gram evolved into Nagel’s SPICE1 program [48]. SPICEl,
of circuit analysis using digital computers. Based on his as well as SLIC and SINC, were placed into the public
work at Fairchild, as well as the results working with domain. All have benefited from the availability of these
graduate researchstudents, all aspectsof the problem were simulators. Very importantly, feedback from usage has
studied: network formulation, linearization, integration been an important aid in the continual development and
techniques, sparse-matrix techniques, gaussian elimination fine tuning of this type of program and for the increased
and LU decomposition, pivoting techniques, etc. The re- applicability of these programs to new circuit applications
sults of this project, i.e., the collection of conclusions and and types.
coded routines, formed the CANCER program [47]. The Nagel, in his doctoral studies, studied thoroughly all of
major components of this program will be brought out the experience of the prior ten years with this type of
shortly. circuit simulator and investigated the possibilities of im-
In parallel to the CANCER project was the development provement in making different choices. In particular, he
by McCalla of the SLIC program [33]. SLIC was based studied thoroughly the synergism aspectsof proper choice
upon the BIAS program and included new linear circuit of all of the components and techniquesneededin a circuit
analysis developmentsand new nonlinear device modeling. simulator. In early 1975, SPICE2 emerged,which has be-
A particular feature, now incorporated in most simulators, come a worldwide CAD tool [49], [13].
was the determination of the dc state of the circuit fol- It must be stressed that the early workers found that
lowed by the evaluation and printout of all bias dependent programs which achieve CAD are complex software sys-
parameters of the transistors. tems in their own right. Although there has been a need for
The interaction among the several circuit simulation theoretical and practical investigations in all of the algo-
projects involving SINC, CANCER, and SLIC at the same rithmic aspectsof a CAD design procedure, there has also
location was extremely fruitful. It should be noted that the been a need to concentrate on the overall software system.
programs incorporated floating voltage sources, induc- The set of “best” algorithms and techniques may not, and
tances, etc., as side constraints. That is, the conventional usually does not, lead to the best software system. Rather,
nodal analysis procedure was modified. one must determine the best set of algorithmic procedures
The modified-nodal-analysis technique was developedin in order to be able to achieve a program package that is
a formal sensesimultaneously by Ho and his colleaguesat optimal or at least well conditioned in itself. These choices
IBM [28], [29]. This technique was included in the ICD were made in the popular, well-used programs ASTAP and
program written in APL. ICD is an excellent interactive SPICE2.
program for on-line simulation and circuit design [28], [29], It is interesting to compareASTAP and SPICE2. ASTAP
[761. has a slow setup time to achieve fast repeated analysis.
The circuit simulators cited above (in those days they SPICE2 achievesfast circuit input checking with the small
were sometimescalled third-generation simulators) shared analysis time penalty of MNA. The former is very advanta-
common features: a modified form of nodal analysis, mod- geous for the repeated use in statistical analysis. Fast
ified to be able to take care of voltage sources, floating turnaround time at low cost is important for initial design
sources, and inductive elements; a first- or second-order evaluation since 80 percent of simulation runs fail at input
backward integration technique; advantage was taken for time.
PEDERSON: HISTORICAL REVIEW OF CIRCUIT SIMULAnON 107

VI. OTHER CONTRIBUTIONS has emanated stories concerning the success of circuit
The circuit simulators described above, e.g., ASTAP and simulation in isolating significant problems. This has led to
SPICE, do not of course constitute the only successfuland the use of circuit simulators with dedicated computers for
important efforts in this field in the past two decades.As the analysis of very large circuits.
mentioned earlier, the author is concentrating on the pro- Many workers and many schemeshave been involved in
grams with which he is most familiar and which are the improvement in simulation speed. Epler, at TI, has
representative of the developments which have occurred. noted that a factor of five improvement can be achieved
For completeness,however, mention must be made of the over an early releaseof the SPICE program by “tuning”
excellent work in circuit simulation done at the University the software to the system[20]. McCalla, Nagel, and Cohen,
of Illinois, Urbana, under Trick. Wing at Columbia Uni- in their work over ten years with SPICE and SLIC, have
versity has also made many fundamental investigations also observed this kind of improvement by tuning. Their
and has led program development efforts. Director and his use of compiled machine code for central portions of the
students at Florida and CMU have made major contribu- program also decreasedrun time. Newton, in the’ mid-
tions, as have Engl at Aachen and DeMan at Leuven, in 1970’s, noted, in developing a special interactive circuit
Europe. Spence’searly work in interactive CAD must be simulator for an early desktop computer, that he could
mentioned. At Bell Labs, major results have been produced achieve large ratios of improvement by very carefully not-
by Scharfetter, Dowell, Kozemchak, and Nagel. The ing capabilities of the computer [50]. Starting from an
ADVICE program is Nagel’s latest version of SPICE. initial straightforward use of high-level language, he was
The work at Autonetics (now Rockwell) did not stop able to achieve a factor of 20 improvement in speed.This
with the TRAC program. There has been a continual effort type of improvement, although not as large, has also been
there, particularly by Bastian, which led to the SYSCAP observed recently with interactive circuit simulators used
programs. Similarly, the Air Force has continued to spon- on presently available desktop computers [24].
sor investigations and developments with SCEPTRE. In An early speedimprovement technique that proved very
Japan, many significant developmentsin circuit simulation effective has been called the bypass scheme.In bypass, the
have been made, particularly in industrial concerns [71]. terminal voltages of all electronic devices are monitored
from time-point to time-point. If there has been little
change, the evaluation of the device is bypassed.Since for
VII. LARGE-SCALE CIRCUITS circuits of 100 transistors or less the device evaluation time
Initially, the SPICE-type programs were thought to be consumes80 percent of the analysis time, the improvement
limited to a maximum circuit size of a few hundred ele- can be significant in many IC simulations.
ments and devices.It was believed that simulation of larger In addition to the (heuristic) bypass scheme,theoretical
circuits would limit the patience of the designer with efforts have also contributed significant speed-up.Branin,
respect to computer run time and exhaust his available following along the lines of the early work of Kron, and
financial resources.It was believed that the designer of a which started Branin in our CAD activities, introduced
large system would always partition the circuit into branch-tearing techniques to circuit simulation [4], [37].
manageable segments, and this has been certainly true. Other significant work has involved node-tearing tech-
Nonetheless, for the large-scale circuits and systems of niques and latency [60], [65], [75]. The technical aspectsof
interest, particularly VLSI circuits, the interaction between these developments are well reviewed in the simulation
the partitions has almost always been significant. One can summary of October.1981 [26].
not always assumethat all parasitic aspectsand significant
delays have been included or estimated correctly. Thus, it VIII. DEDICATED AND VECTOR COMPUTER
has been necessaryfor design and evaluation purposes to INVESTIGATIONS
simulate larger and larger circuits. This has ,beenparticu- Investigations to improve circuit simulation speed have
larly true of circuits consisting of large regular arrays such also centered on the computer itself. Since different ma-
as RAM and ROM memory circuits. chines given different limitations or lead to different choices
Two simultaneous developmentsin the past have aided of the algoithms for simulation, tailor-made, nonportable
the above task. First, faster, larger mainframe computers programs can be developed. For a particular dedicated
have become available and less costly; thus, cost-effective computer, Program SPUDS by Cohen was the result of an
simulation of large circuits is possible. Second, and as investigation which started with the simulation results using
brought out below, developmentshave been made with the a high-level language [14]. He then investigated what
circuit simulators themselveswhich have provided signifi- speed-upscan be obtained with assemblylanguageroutines.
cant speed-up, i.e., less run time. It should also be men- Finally, he developedspecial-purposemicro-coded instruc-
tioned that the interaction problems in LSI and VLSI tions from the available machine repertoire that were par-
circuits, as mentioned above, have been so severe that it ticularly suited to the tasks of circuit simulation. For the
has been essential in spite of the cost to make large new sparse-matrix solution instructions, speed improve-
numbers of long simulation runs, of the order of days of ments of 20 were obtained. However, overall simulation
mainframe computer time, to ascertain the cause of criti- performance with Program SPUDS for reasonable size
cal-path delays. From every maior electronics comnanv I -~---I
circuits was only a factor of three improvement in relation
 108 VOL. CAS-31, NO. 1, JANUARY 1984
IEEETRANSACTIONSON CIRCUITSAND SYSTEMS,

to a tuned simulator written in a high-level languageusing simulator. But the different I/O requirements have always
adequatecompilers. been a major problem. Different programs developed by
Other developmentshave utilized vector computers [27]. different groups or individuals evolve with nonidentical
Most large circuits make highly repetitive use of a few input and output formats. Input file preparation or transla-
basic circuits and the use of a small number of distinct tion is awkward and very time-consuming and cost-produc-
electronic device models. Thus, it is conceivable that a ing. The “standards” which have evolved by common
vector processor can be employed where these individual usageare often not general enough to satisfy the needsfor
subscircuits and device types can be processedin parallel new programs or applications.
in the vector mode. The CLASSIE Program, by Vladi- The study of numerical limitations of timing analysis has
mirescu, is one result of such an investigation [72], [73]. led to new types of accurate and fast circuit simulation.
Due to typical circuit sparsenessand the gather-scatter The relaxation iteration can be continued to convergence
problem [lo], vector schemes do not provide too large either in space(over the circuit nodes) or in time to achieve
improvements in simulation speed.Approximately up to a as accurate a solution as that provided by conventional
factor of ten improvement over SPICE2 in circuit simula- circuit simulation employing the same electronic models
tion speed can be obtained for highly repetitive large [55]. The major advantage of relaxation-based approaches
circuits. is the ability to exploit time sparsity, using the event-driven
In other recent efforts, circuit simulator SPICE has been selective trace techniques first developed for logic simula-
used with array processors.Again, by exploiting the vector tors. For large circuits, over 90 percent of the transistors
mode of analysis, factors of five in improved performance may not require re-solution at a time point: These new
can be obtained over that performance obtained on a iterated timing analysis programs can be predicted to be-
super-minicomputer [15], [67]. come the circuit simulators of the near future.
In major new investigations, special-purpose routines Even with recent improvements in the speed of circuit
necessary in circuit simulation are being designed into simulators, it is generally impractical to simulate entire
hardware (ICs). In these developments, the nonportability VLSI circuits at the electrical level. Critical ‘timing paths,
aspect is taken to the limit, and the “micro code” of the usually containing less than 5000 transistors, are identified
computer is being optimized for the task at hand. _ by the circuit designer and fed to a simulator. Unfor-
tunately, errors can occur when the designer chooses the
IX. TIMING AND RELAXATION-BASEDSIMULATION wrong timing path for simulation or ignores a complex
. Timing Simulation is circuit simulation in which ap- interaction between a number of paths. Since the 1960’s,
proximations are purposely introduced with relaxed accu- digital logic designershave beenusing “ timing verification”
racy to achieve greatly improved simulation speed. In a programs [36], [46], [45] to identify critical paths in com-
sense,timing simulation has been with us from the begin- plex logic systems such as main-frame computers. These
ning of CAD. Individual workers have programmed rudi- programs assign a delay to each logic gate and perform a
mentary circuit analysis schemes to solve a problem at critical-path analysis of the network to identify potential
hand. Often times, these seemingly crude programs were problems. Recently, these techniques have been applied
sufficient for significant developments within IC compa- successfully at the circuit level as well [56]. Using simple
nies. A systematic approach to this topic, however, was RC models for rise and fall times at each circuit node,
started approximately ten years ago by Gummel and his these timing verifiers can predict critical path delays to
coworkers at Bell Laboratories, in the process of develop- within 10 percent for constrained IC design styles. Once
ing an integrated set of software tools (one of the first) for the critical paths have been identified, the circuits on the
the electrical and physical design and verification of an critical path are prepared for input to a circuit simulation
integrated circuit design methodology. His program MO- program to check the timing predictions of the timing
TIS was a significant development which led to a con- verifier. Initial results with timing verification at the circuit
tinued development in other places on many continents level are promising and timing verifiers will certainly be-
- [ll]. come an important addition to the CAD toolbox.
In the initial MOTIS-type programs, internal feedback Shortly after the development of timing simulation,
of devices,although present, is assumednegligible. Thus, a mixed-mode or hybrid simulation emerged.In mixed-mode
relaxation-based matrix solution technique; such as the simulation, a portion of a large circuit is simulated, say in
Gauss-Jacobi or the Gauss-Seidelmethod, can be used to electrical activity, while simultaneously another portion of
achievevery fast circuit simulation. The key to the simplifi- the circuit is being simulated in a different mode, say logic.
cation is the taking of only one step of the relaxation For example, it is possible to have the majority of a large
iteration at each time point. The simplification provides circuit being simulated in terms of logic levels while an
accurate results if feedback is negligible. Of course, the interacting and related subportion of the complete circuit is
assumptions may not hold well, and the simulation results being simulated in a timing or circuit simulation mode.
may be inaccurate. It has been necessary,then, in timing With respect to logic and timing simulation, significant
simulation when greater accuracy is required to introduce developments have occurred. In Leuven, DeMan and his
methods to achieve more accurate simulation. ‘A possible coworkers [17], [18], and at Berkeley, Newton and his
procedure at this stageis to move to a conventional circuit coworkers [51]-[53], have developedthe DIANA and SPL-
PEDERSON: HISTORICAL REVIEW OF CIRCUIT SIMULATION 109

ICE Programs, respectively. Of course, other levels and design. Circuit analysis with digital computers has been a
groupings of simulation can also be achieved. At CMU, steady activity throughout the last thirty years, and im-
Director and his -students have developed the Program portant developments have been accomplished. Although
SAMSON [61], [62]. It is possible for two-dimensional adequatecircuit simulators are now available, still as needs
device simulation to occur simultaneously with the circuit have arisen and been identified, investigations have con-
simulation of the connection of the devices[19]. In Europe, tinued; new programs have been written, and new results
North America, and Japan, significant activities of mixed- are being achieved.Even at this point with the very capable
mode simulation are in progress at most centers of CAD tools available, one can see the emergence of iterative
activity. Thesemixed-mode simulators are just coming into timing analysis, a new class of tool, which will aid the
use in VLSI design. design of large-scalecircuits and systems.
Circuit-design optimization was the driving force for the
X. OPTIMIZATION initial circuit-analysis programs. This topic remains a criti-
As brought out earlier, the application of the first cir- cal one in CAS to achieve optimum design performance,
cuit-analysis programs was for repeated analysis under manufacturability, and tolerancing, particularly for nonlin-
control of another program to choose the best circuit ear time-dependentcircuits.
element values to achieve overall specifications, i.e., an It is clear, as one reviews the continued development of
optimization package evolved. The initial work concerned computer aids for circuit and system design, there has been
the design of electrical filters, in the sinusoidal steady state. a significant effort, both of those working in theory and in
Work in computer optimization has continued through the computer program development. CAD is now one of the
years and significant results and conclusions have been most significant and meaningful areas for those of us
achieved in the problem areas of design centering, toler- identified with the CAS Society. This aspect is recognized
ance optimization, and parasitic inclusion. In addition to in many ways. First, the CAS Society has formed a new
the passive filter problem, design solutions for which have journal, the IEEE TRANSACTION ON COMPUTER-AIDED DE-
existed for some time, optimization programs have been SIGN OF INTEGRATED CIRCUITS AND SYSTEMS, now in its
modified and expanded to achieve the optimum design of third year of publication. Further, one of the standing
new and important active filtering techniques. committees of the CAS is CANDE, concerned with all
Of course, there is a limit to what can be accomplished aspects of CAD. The CANDE committee sponsors an
directly in the frequency domain. In spite of transform important workshop each year, and its members take an
techniques (useful for linear circuits), optimization, toler- active role in organizing sessionsat the annual ISCAS and
ancing, and design-centeringtechniques are needed in the at new conferencessuch as the 1982 ICCC and the 1983
time domain directly and, of course, for nonlinear circuits. ICCAD. It can be anticipated that the concentration of
There is still a critical need for optimization efforts in the effort within the CAS Society on CAD, and the parade of
time domain in spite of the significant results to this point. new results, will continue into the foreseeablefuture.
The optimized design of nonlinear transient circuits is still
very much an open question. Fortunately, becauseof the ACKNOWLEDGMENT
nature of binary, digital circuits in which the use of and Becauseof the very wide range of CAD activities by the
design for two static states stops the propagation of errors members of the CAS Society, and because of the all-
throughout a circuit, effective design up to the present can encompassing nature of CAD, it has been necessary in
be achieved solely on the basis of the proper inclusion of writing this paper to make several difficult choices. Many
parasitics to estimate the significant timing paths. major aspectsof CAD could have been stressedin place of
An excellent recent review paper on circuit-design opti- those chosen.Even though some topics are of prime inter-
mization points out how, in the past few years, signifi- est to other IEEE societies and, in a sense,are covered in
cantly improved performance has been obtained in the the publications of these societies, still, many members of
design of large systems because of the improved perfor- the CAS Society would have preferred a concentration on
mance of the simulation packages on the one hand and, thesetopics. They, naturally, will be distressed.Even within
even more importantly, the developmentof new techniques the thread of CAD activity concerning computer-aided
to specify the performance and cost functions to be opti- circuit analysis, it has been necessaryto make difficult and
mized [8]. Performance results from these automated de- awkward choices concerning what contributions and what
signs give a significant improvement over what has been decisions to stress. Shortly after this thread was chosen, a
able to be achievedby skilled IC designers.Another review next major decision concerned a restriction to the CAD
paper oriented toward general systemsis also available for most important for large-scalecircuits. This, then, did not
the reader interested in the latest status on techniques[59]. permit me to mentiorrmany important topics of simulation
such as pole-zero techniques, sensitivity and sensitivity
XI. SUMMARY calculation, the adjoint technique, the steady-statesimula-
With the availability of the digital computer, whether tion of circuits including oscillators, etc. The omission of
relay or electronic, circuit and system investigators and these topics within computer-aided circuit analysis will
designershave utilized these computers, and the programs distress other CAS Society members. But in order to keep
which run on them, as tools to achievecircuit analysis and the paper in manageablesize and topic for an historical
110 IEEETRANSACTIONS
ON CIRCUITSAND SYSTEMS,
VOL. CAS-31,NO. 1, JANUARY1984

review, these decisions have been painfully made. These Pederson, and H. DeMan, Eds. Groningen, the Netherlands:
Sijthoff & Noordhoff, 1980, pp. 113-174.
have been solely my responsibility. But I do wish to 1191 W. L. Engl, R. Laur, and H. K. Dirks, “Medusa-A simulator for
acknowledge the significant help that I received from the modular circuits,” IEEE Trans. Computer-Aided Design of ZCAS,
vol. CAD-l, no. 2, pp. 85-93, Apr. 1982.
reviews and criticisms by I. E. Getreu, M. J. McCalla, A. B. Epler, Texas Instruments Co., private communication, 1982.
R. Newton, and A. Sangiovanni-Vincentelli. I am pleased ty A. Feller, A. Smith, P. Ramondetta, and T. Lombardi, “High speed
CMOS/SOS using standard cells,” RCA Engineer, pp. 36-40, Dec.
to acknowledge the support that has been given our CAD 1974/Jan. 1975.
group at Berkeley by many agenciesand firms. In particu- WI C. W. Gear, “Numerical integration of stiff ordinary differential
equations,” Dept. Comput. Sci., Univ. of Illinois, Urbana, Rep. 221,
lar, I wish to mention the financial support given over the 1967.
years by the Army Research Office, lately under Grant v31 R. S. Graham, “Relay computer for network analysis,” Bell Labs.
Rec.. vol. 31. nn. 152-157. Anr. 1953.
DAAG29-81-K-0021, the National Science Foundation, [241 R. S. Gyurc’s~~~~&&~~,~~~ Ma, T. Yee, and D. 0. Pederson,
recently under Grant ECS-8310442,and the Semiconduc- “BIAS-B/P: circuit simulators for desktop computers,” in IEEE
f’ro;., I983 Custom Integrated Circuits C&f., pfi. 354-358, May
tor Research Corporation. Industrial firms that have
provided both technical cooperation and financial support (251 G. D. Hachtel, R. K. Brayton, and F. G. Gustavson, “The sparse
tableau approach to network analysis and design,” IEEE Trans.
include Bell Labs, Digital Equipment Company, Hewlett- Circuit Theory, vol. CT-18, p 101-113, Jan. 1971.
Packard, Tektronix, and Texas Instruments. And finally, I WI G. D. Hachtel and A. L. l angovanm-Vincentelli, “A survey of
third-generation simulation techniques,” Proc. IEEE, vol. 69, pp.
acknowledge the tremendous contributions that have been 1264-1280, Oct. 1981.
made by the many researchstudents and researchersin the [271 S. D. Hamm and S. R. Beckerich, “VAMOS: Circuit simulation
program for a vector computer,” in Proc. ZCCAD Conf, Sept. 1983.
many locations where circuit simulation has been devel- WI C. W. H?, A. E. RuehIi, P. A. Brennan, and D. A. Zem, “Interac-
oped. In many of these academic and industrial locations, tive circuit analysis and design using APL,” in Proc. 1975 ZSCAS,
users of our circuit simulation programs have been the ~291 ??&6-~!9fi. Ruehli and P. A. Brennan “The modified nodal
willing or unwitting guinea pigs to use and to improve appro&h to network’ aimlysis,” IEEE Tr&s. Circuits Syst., vol.
CAS-25, pp. 504-509, June 1975.
these software products. [301 “Automated digital computer program for determining responsesof
electronic systems to transient nuclear radiation (BREDICT),” IBM
REFERENCES ;g;;; Gmdance Center, Oswego, NY, IBM Fde 64-521-5, July
111 M. R. Aaron, “The use of least squares in system design,” IRE [311 “1620 electronic circuit analysis program [ECAP],” [‘1620-EE-02X]
Trans. Circui? Theo
“2, vol. CT:3, pp. 224-231, 1956.. User’s Manual, IBM Application Program File H20-0170-1, 1965.
121 T. R. Bashkow, e A matnx, new network descnption,” Truns. ~321 “ASTAP-Advanced statistical analysis program,” IBM Program
IRE Trans. Circuit Theoty, vol. CT-4, pp. 117-119, 1957. Product Document SH20-1118-0,IBM Data ProcessingDiv., White
131 R. D. Berry, “An optimal ordering of electronic circuit equations or Plains, NY, 1973.
a sparse matrix solution,” IEEE Truns. Circuit Theoty, vol. CT-18, [331 T. E. Idleman. F. S. Jenkins. W. J. McCaIla. and D. 0. Pederson.
pp. 40-50, Jan. 1971. “SLIC-A similator for line& integrated circuits,” IEEE J. Solid:
[41 F. H. Branin, Jr., “The relation between Kron’s method and the State Circuits, vol. SC-6, pp. 188-204, Aug. 1971.
classical methods of network analysis!” in,ZRE WESCON Conv. [341 F. S. Jenkins and S. P. Fan, “TIME-A nonlinear dc and time-
Rec., pt. 2, pp. 3-28, 1959. Also avadable as Tech. Rep. 00.686, domain circliit simulation program,” IEEE J. Solid State Circuits,
IBM Development Laboratory, Poughkeepsie,NY, 1959. vol. SC-6, pp. 188-192, Aug. 1971.
[51 F. H. Branin, Jr., “DC analysis portion of PETAP-A program for [351 E. D. Johnson, C. T. KIeiner, L. R. McMurray, E. L. Steele, and
analyzing transistor switching circuits,” IBM Development Lab., F. A. Vassallo, “Transient radiation analysis by computer program
Poughkeepsie,NY, Tech. Rep. 00.701, 1960. (TRAC),” Autonetics Div,, North American Rockwell Corp.,
[61 F. H. Branin, Jr., “DC and transient analysis of networks using a Anaheim, CA, Tech. Rep. Issued by Harry Diamond Labs., June
digital computer,” in IRE Znt. Conv. Rec., pt. 2, pp. 236-256, Mar. 1968.
1962. [361 T. I. Kirkpatrick and N. R. Clark, “PERT as an aid to logic
[71 F. H. Branin, Jr., “Computer methods of network analysis,” Proc. design,” IBM J. Res. Develop., pp. 135-141, Mar. 1966.
IEEE, vol. 5, pp. 1787-1801, Nov. 1967. [371 G. Kron, “A set of principles to interconnect the solutions of
PI R. K. Brayton, G. D. Hachtel, and A. L. Sangiovanni-Vincentelli, physical systems,” J. Appl. Phys., vol. 24, pp. 965-980, 1953.
“A survey of optimization techniques for integrated-circuit design,” [381 E. S. Kuh and R. A. Rohrer, “The state-variable approach to
Proc. IEEE, vol. 69, no. 10, pp. 1334-1361, Oct. 1981. network analysis,” Proc. IEEE, vol. 53, p 672-686, Jul 1965.
[91 N. G. Brooks and H. S. Long, “A program for computing the 1391 W. Lattin, “VLSI design methodology: 2l e problem of t Kle 80’s for
transient response of transistor switching circuits-PETAP,” IBM microprocessor design,” in Proc. 16th Design Automation Conf.,
Development Lab., Poughkeepsie,NY, Tech. Rep. 00.700, 1959. (San Diego, CA), pp. 548-549, June 1979.
[lOI D. A. Cab&an, “Multi-level vectonzed sparse solution of LSI 1401 A. F. MaImberg, F. L. Cornell, and F. N. Hofer, “NET-l network
circuits,” in Proc. ZEEE Znt. Con/. Circuits and Computers, New analysis program,” Los AIamos Scientific Lab., Los Alamos, NM,
York, Oct. 1980. Tech. Rep. LA-3119, 7090/94 Version, Aug. 1964.
Pll B. R. Chawla, H. K. Gummel, and P. Kozak, “MOTIS-An MOS I411 H. M. Markowitz, “The elimination form of the inverse and its
timing simulator,” IEEE Trans. Circuits Syst., vol. CAS-22, pp. application to line& programmitig,” Management Sci., vol. 3, pp.
901-909, Dec. 1975. 255-269, A r. 1957.
WI K. A. Chen, M. Feuer, K. H. Khokhani, N. Nan, and S. Schmidt, ~421 H. W. Mat i ers. S. R. Sedore. and J. R. Seuts. “Automated dieital
“The chip layout problem: An automatic wiring procedure,” in computer prog&m for deter&ing responses‘of electronic cir&its
Desi n Automation Conf. Proc., pp. 298-302, June 1977. to transient nuclear radiation (SCEPTRE),” IBM Space Guidance
P31 E. c!ohen, “Program reference for SPICE2,” Univ. of California, Center, Oswego, NY, IBM File 66-928-611,Feb. 1967.
Berkeley, ERL Memo ERL-M592, June 1976. I431 W. J. McCaIla and D. 0. Pederson, “Elements of computer-aided
1141 E. Cohen, “Performance limits of integrated circuit simulation on a analysis,” IEEE Trans. Circuit Theory, vol. CT-18, pp. 14-26, Jan.
dedicated minicomputer system,” Univ. of California, Berkeley, _, ,*.
1971
ERL Memo UCB/ERL M81/29, May 1981. 1441 W. J. McCaIIa and W. G. Howard, Jr., “BIAS-3: A program for the
1151 C. Cole, “Attaching an array processor in the UNIX environment,” nonlinear dc analvsis of bioolar transistor circuits.” IEEE J. Solid-
Univ. of California, Berkeley, ERL Memo UCB/ERL M83/23, State Circuits, voc SC-6, no. 1, pp. 14-19,,Feb. 1971.
April 1983. 1451 J. McClure, “Frequency domain simulation of very large digital
WI H. DeMan, “Computer aided design for integrated circuits: Trying systems,” in Proc. IEEE Znt. Symp. Circuits and Systems,Houston,
to bridge the gap,” IEEE J. Solid-State Circuits, vol. SC-14, pp. TX, pp. 424-430, Apr., 1980.
613-621, June 1979. [461 T. M. McWilliams, “Verification of timing constraints in large
P71 H. DeMan et. al., “DIANA: Mixed mode simulator with a hard- digital systems,” in Proc. IEEE Znt. Symp. Circuits and Systems,
ware description language for hierarchical design of VLSI,” in Houston, TX, pp. 415-423, Apr., 1980.
IEEE ZCCC”80 Conf. Proc., Rye, NY, pp. 356-360, Oct. 1980. [471 L. Nagel and R. A. Rohrer, “ Computer analysis of nonlinear
WI H. DeMan, G. Amout, and P. Reyneart, “Mixed mode circuit circuits, excluding radiation (CANCER),” IEEE J. Solid-State Cir-
simulation techniques and their implementation in DIANA,” in cuits, vol. SC-6, pp. 166-182, Aug. 1971.
Computer Design AidF for VLSI Circuits, P. Antognetti, D. 0. [481 L. W. Nagel and D. 0. Pederson, “Simulation program with in-
PEDERSON: HISTORICAL REVIEW OF CIRCUIT SIMULATION
111

tegrated circuit emphasis,” in Proc. 16th Midwest Symp. Circ. [671 L. J.‘Shanbeck and R. S. Norm, “QSPICE: An application of array
Theory, Waterloo, Canada, Apr. 1973. processors to CAD simulation of IC circuits,” in Proc. IC-CAD
(491 L. Nagel,, “SPICEZ: A computer program to simulate semiconduc- Conf., Sept. 1983.
tor circmts,” Univ. of California, Berkeley, ERL Memo UCB/ERL WI H. Shichman, “Computation of dc solutions for bipolar transistor
M75/520, May 1975. networks,” IEEE Transr Circuit Theory, vol. CT-16, pp. 460-466,
[501 A. R. Newton and G. L. Taylor, “BIASL.25 An MOS circuit Nov. 1969.
simulation program for a programmable calculator,” in Tenth An- [691 “The integration system of a nonlinear network-analysis
nual Asilomar Conf. Circuits, Systems,and Computers,pp. 280-283, program,” IEEE Trans. Circuit Theory, vol. CT-17, pp. 378-386,
Nov. 1976. Aug. 1970.
[511 A. R. Newton, “The simulation of large-scale integrated circuits,” [701 J. Sot&up, “Circuit Layout,” Proc. IEEE, vol. 69, pp. 1281-1304,
yJr+i; of California, Berkeley, ERL Memo No. ERL-M78/52, July Oct. 1981.
[711 T. Sudo, T. Ohtsuki, and S. Goto, “CAD systems for VLSI in
~521 “Techniques for the simulation of. large-scale integrated Japan,” Proc. IEEE, vol. 71, Jan. 1983.
circuits,” IEEE Trans. Circuits Syst., vol. CAS-26, pp. 741-749, [721 A. Vladimirescu and D. 0. Pederson,“A computer program for the
Sept. 1979. analysis of LSI circuits,” in Proc. IEEE Int. Symp. on Circuits and
[531 A. R. Newton, “Timing, logic, and mixed mode simulation for large Systems, Chicago, IL, Apr. 1981.
MOS integrated circuits,” in Computer Design Aids for VLSI, P. [731 A. Vladimirescu, “LSI circuit simulation on vector computers,”
Antognetti, D. 0. Pederson,and H. DeMan, Eds. Groningen, The Univ. of California, Berkeley, ERL Memo, UCB/ERL M82/75,
Netherlands: Siithoff & Noordhoff. 1980. DD. 175-240. Oct. 1982.
[541 A. R. Newton, -“A survey of computer ‘ids for VLSI layout,” in [741 W. T. Weeks et al., “Algorithms for ASTAP-A network analysis
1982 Symp. on VLSI Technology,no. 82, pp. 72-75, Sept. 1982. program,” IEEE Trans. Circuit Theory, vol. CT-20, pp. 628-634,
[551 A. R. Newton and A. L. Sangiovanni-Vincentelli, “Relaxation Nov. 1973.
based electrical simulation,” IEEE Trans. Electron Devices, vol. [751 P. Yang, “An investigation of ordering, tearing, and latency algo-
ED-30, Sept. 1983, and IEEE Trans. Computer-Aided Design - of. rithms for the time-domain simulation of large circuits,” Univ. of
ICAS, to be published. Illinois, Urbana, Tech. Rep. R-891, Aug. 1980.
[561 J. K. Ousterhout. “CRYSTAL: A timine analner for nMOS VLSI [761 D. A. Zein. C. W. Ho. and A. J. Gruodis. “A new interactive circuit
circuits,” in 3rd Cal. Tech. Conf: on VLSI, p .*57-70, 1983. design program,” in Proc. IEEE Int. Symp. Circuits and Systems,
I571 G. Persky, D. N. Deutsch, and D. G. SchweP ert, “LTX-A system Houston, TX, pp. 913-917, 1980.
for the directed automation design of LSI circuits, in Proc. 13th
Design Automation Conf., 1976. -
[581 G. Perskv, D. N. Deutsch. and D. G. Schweikert. “LTX-A
minicomputer-based system for automatic LSI layout,” .I. Design +
Automation and Fault-Tolerant Computing, vol. 1, no. 3, pp. 217-255,
May 1977.
I591 E. Polak, “Semi-infinite optimization in engineering design,” in Donald 0. Pederscm(S’49-A’51-M’56-F’64) re-
Lecture Notes in Economics and Mathematical Systems, vol. 215, ceived the B.S. degree from North Dakota State
Semi-Infinite Programming and Applications, A. V. Fiacco and K. 0. University in 1948, and the M.S. and Ph.D.
Kortanek, Eds., Berlin, New York, Tokyo: Springer-Verlag, 1983.
N. B. Rabbat, A. L. Sangiovanni-Vincentelli, and H. Y. Hsleh, “A degrees from Stanford University in 1949 and
WI 1951, respectively.
multilevel newton algorithm with macromodeling and latency for
analysis of large-scale nonlinear networks in the time domain,” From 1951 to 1953 he was a ResearchAssoci-
IEEE Trans. Circuits Systs., vol. CAS-26, Sept. 1979. ate in the Electronics ResearchLaboratory, Stan-
I611 K. A. Sakallah and S. W. Director, “An event driven approach for ford University. He worked at Bell Telephone
mixed gate and circuit level simulation,” in Proc. IEEE Int. Symp. Laboratories, Inc. and was also a lecturer at New
Circuits and Systems,pp. 1194-1197, May 1982. JerseyInstitute of Technology from 1953 to 1955.
PI K. A. Sakallah and S. W. Director, “SAMSON: A mixed circuit In 1955 he joined the University of California,
logic level simulator,” to be published.
[631 R. A. Saleh, J. E. Kleckner, and A. R. Newton, “Iterated timing Berkeley. He is now a Professor in the Department of Electrical Engineer-
analysis in SPLICEl,” in Proc. ICCAD Conf., Sept. 1983. ing and Computer Sciences,engagedin researchin integrated circuits and
Fe41 I. W. Sandberg and H. Shichman, “Numerical integration on sys- computer-aided integrated circuit design, and is the Chairman of the
tems of stiff nonlinear differential equations,” Bell Syst. Tech. I., Department. From 1960-1964 he was Director of the Electronics Re-
vol. 47, pp. 511-527, Apr. 1968. search Laboratory.
[651 A. L. Sangiovanni-Vincentelli, L-K. Chen, and L. 0. Chua, “A new Dr. Pedersonis a member of Sigma Xi and Eta Kappa Nu. In 1964 he
tearing approach-Node-tearing nodal analysis,” in Proc. IEEE was a Guggenheim Fellow. He was the ‘recipient of the 1969 IEEE
Int. Symp. Circuits and Systems, p 143-147 Apr. 1977. Education Medal. In 1974 he was elected to the National Academy of
[W A. L. Sangiovanm-Vincentelli, ” Krcuit simulation ” in Computer Engineering. He was awarded an honorary Doctor of Applied Scienceby
Design Aids for VLSI Circuits, P. Antognetti, D. 0.’ Pederson, and
H. DeMan, Eds. The Netherlands: Sijthoff & Noordhoff, 1980, the Katholieke Universiteit, Leuven, Belgium, in 1979, In 1982 he was
pp. 19-112. elected to the National Academy of Sciences.