Fifty years ago, the author and his students studied the analytic properties of network functions of nonuniform RC and LC transmission lines and obtained the necessary and sufficient conditions for a transcendental function to be a network function of such lines in both the frequency and time domains. They showed for example that the ABCD parameters of an RC line are entire functions of order Vz and genus zero, and the impulse response is a totally positive density function. These fundamental properties may not have any relevance to circuit design today, but they are ever-lasting truths about circuits.

This paper studies the steady-state analysis of a system of ODE-AE-CGE arising from simulation of MOS RF autonomous circuits in which the transistor plays as current generator and its current equations could adequately represent the transistor large-signal dynamic behavior. Gauss-Seidel relaxation is applied to decouple the system so that shooting method, which is used to find the periodic steady-state response, can be performed with low-order sensitivity matrix. This simplifies the solution process and results in a fast algorithm. We illustrate the new algorithm with the simulation of a typically voltage-controlled oscillator (VCO), the simulation results show good agreement with those obtained by MEDICI, a device simulator.

A new waveform bounding algorithm to obtain an upper and lower waveform bound of the time response of a class of RLC circuits is presented. The algorithm produces a sequence of waveforms which converge to the true solution monotonically from above and below. The key step is the choice of the initial guess in the relaxation process. A new method to obtain an initial guess that guarantees monotonic convergence is given. Numerical examples are included to confirm the theoretical results.

We present waveform relaxation of linear integral-differential equations which occur in circuit simulation. We give sufficient conditions for convergence and numerical experiments to verify the theoretical results.

We explore what is needed to improve and automate the process of designing a broadband ATM switch, i.e., determining the "optimal" switch parameters given hardware costs and constraints on quality of service. We present a cost model for implementation with CMOS integrated circuits, based on some prototype designs that include both input and output buffering, and combine this with a simple method for rough performance analysis to allow quick design evaluation. Experiments are presented for a range of specifications, based on an automated exhaustive search algorithm and a framework for using nonlinear integer optimization to improve efficiency in the future is developed.

In this paper the non-linear and complex relationship between packet loss probability and average packet delay for an input/output buffered ATM switch is studied thoroughly using our previously published analysis model. The main contribution is insight into the behavior of the switch and better understanding of the buffer size trade-offs under various traffic conditions speed-up factors, and buffer sizes. For different traffic conditions and buffer sizes, several distinct regions are identified and the behavior of the switch in those regions is explained. The results presented here can provide the basis for an optimum VLSI design methodology for input/output-buffered switches.

In this paper, we propose a new and efficient approach to the computation of the transient response of lossy VLSI interconnects with arbitrary initial potential and current distributions and nonlinear terminations. The complete solution of the lossy transmission line equation with arbitrary initial conditions is given by linear system theory. In the new model, the initial distributions are incorporated into the waveform generators in the generalized characteristic model, which saves a lot of CPU time and computer memory. The accuracy and efficiency of our simulation method is substantiated by the exact analytical solutions.>

Two analytically derived approximations of /spl radic/s are presented. One is based on Newton's algorithm to find the square root of a positive number and the second is derived from the input impedance of a cascade network of symmetric lattices in which the series impedance is progressively increasing and the shunt impedance is progressively decreasing. A rational function of order 9 gives an approximation with a relative error of less than 1% over a frequency range of 3 1/2 decades; one of order 17 covers 8 1/2 decades.>

A system of coupled transmission lines with frequency-dependent parameters is decoupled into separate, uncoupled lines by a linear transformation, in which each element, being a function of frequency, is modeled as a transfer function of a lumped circuit. Each decoupled line is modeled by its characteristic 2-port. Lumped models of the characteristic impedance and the propagation function are given. For lines with skin effects, we present a new lumped model of /spl radic/s which is scalable, exact at zero frequency and accurate over a wide frequency range. The model of the entire system of coupled lines can be implemented in SPICE using existing circuit elements.>

The p-n junction depletion capacitance models of the SPICE and ADVICE circuit simulators are regional models that have discontinuities in high-order derivatives. This limits the order of integration that can be used for transient analyses, and can limit both the size of time steps that can be used during transient analyses and the accuracy of distortion analyses. In addition, the SPICE and ADVICE depletion capacitance models unphysically predict that the depletion charge increases without bound as applied forward bias increases. An improved depletion capacitance model that overcomes these problems is presented. The model is charge-based, single-piece, and C/sub infinity /-continuous, and has a finite maximum junction depletion charge under forward bias.>

A circuit analysis method, the hierarchical waveform relaxation technique, that uses multilevel decomposition and relaxation techniques is presented. Sufficient conditions for the convergence of the process are discussed, and a dynamic circuit restructuring technique that uses the concept of sensitivity based subcircuit merging and repartitioning within the hierarchical framework to improve the robustness of the simulation algorithm as well as the speed of convergence is presented. The algorithm is implemented in the circuit simulation program PYRAMID, and test results are compared with those obtained by other methods of analysis. The comparison indicates that this method produces better results than had previously been possible for a large range of circuits of practical interest, particularly strongly coupled digital bipolar and FET circuits containing bidirectionality and feedback, and it is demonstrated that the relative improvement of the method scales with the size of the circuit.>

An algorithm for computing the transient response of a coupled, dispersive multiconductor system terminated in nonlinear loads is presented. The characterization of the multiconductor system is based on full-wave analysis using the spectral domain approach, rather than the usual TEM approximation. To compute the transient response of such a system, a bilevel waveform relaxation method is used. Waveform relaxation is applied to compute a time-domain solution at the input and output interfaces. The waveforms are then transformed into the frequency domain to compute the updates induced by the multiconductor system and are transformed back to the time domain for the next set of relaxation at the interfaces. Techniques for convergence are discussed. Examples of ECL, CMOS, and GaAs circuits connected by coupled lines are given for illustration.>

A novel algorithm to compute the transient response of a coupled, dispersive multiconductor system terminated in nonlinear loads such as transistors is developed. The characterization of the multiconductor system is obtained from a full-wave analysis based on the spectral domain approach, and it is suitable for circuit simulation. The transient response of such a system is computed by a bi-level waveform relaxation method. The solution process consists of two steps. One is to obtain a time domain solution at the input and output interfaces by local waveform relaxation, and the second is to transform the waveforms into the frequency domain and obtain the necessary updates for the next global relaxation step. The method allows the interconnects to be separated from the rest of the system so that both the nonlinear termination circuit and the multiconductor system can be analyzed in the most efficient way. The method has been applied to multiconductor systems terminated in MOS, ECL (emitter coupled logic), and GaAs transistors and it is shown that reflections and couplings can create logic errors in the system. The program that implements the algorithm is written in C.>

An algorithm is presented which partitions a gate matrix into a number of matrices such that the total area and the aspect ratio of the circumscribing rectangle are improved. The algorithm is based on the min-cut algorithm. The gain function and the balance condition are redefined for the gate matrix problem. The time complexity of the algorithm is O(t)+O( mod N/sub I/ mod /sup 2/), where t is the number of gate-net intersections, and N/sub I/ the subset of nets that intersect long gates. A novel gate-sequencing algorithm, designed for assigning gates in the partitioned gate matrices simultaneously, is introduced. By using the simultaneous-gate-sequencing algorithm, the partitioned gate matrices are connected by sharing gates. Since the same column is used for a gate shared by adjacent matrices, the layout does not require extra routing area. Experimental results show significant improvement over the layout without partition. For the three examples used in a previous paper, the area reduction ranges from 11-41%. The aspect ratio improves from 2.63, 4.00, and 2.59 to 1.04, 1.22, and 1.28, respectively.>

A two-stage approach to gate matrix layout is described. The approach consists of: the determination of an optimal gate sequence and an assignment of nets to rows such that the nets are realizable. The gate sequence algorithm is based on T. Asano's approximate search (1981). Modifications are made to it to take into account constraints of transistor sizing, serial subcircuit conflicts, input/output (I/O) gates, and I/O nets. The zone-net assignment algorithm assigns nets to a minimum number of rows determined by the gate sequence and provides a means to resolve vertical conflicts in the layout. Power connections are implemented using the power nets and possible added power rows. Results of examples show that the approach can achieve a considerable improvement compared to earlier algorithms, while satisfying additional constraints.>

A heuristic algorithm is presented that partitions a gate matrix into two matrices so that the total area and the aspect ratio of the circumscribing rectangle are improved. The algorithm is based on the min-cut algorithm, with the gain function and balance condition redefined for the gate matrix problem. The time complexity of the algorithm is O(t)+(n* mod G/sub L/ mod *LB), where t is the number of transistors, n the number of nets, mod G/sub L/ mod the number of long gates, and LB the maximum number of nets on a gate. Experimental results show significant improvement over the layout without partition. For three examples the area reduction ranges from 20% to 30%. The aspect ratio improves from 2.59, 2.63 and 4.00 to 1.11, 1.16, and 1.18, respectively.>

A hierarchical waveform-relaxation-based method for analysis of bipolar, MOS, and GaAs FET circuits is presented. By analyzing the circuit in a hierarchical manner, a faster solution has been obtained for circuits exhibiting strong bidirectionality and feedback than has previously been possible. The technique has been applied to a wide variety of digital and mixed analog/digital circuits, and circuits containing over 18000 transistors have been analyzed. Results obtained for a variety of circuits show up to two orders of magnitude improvement in computation time compared to conventional circuit simulation techniques and up to one order of magnitude improvement compared to the standard waveform-relaxation technique.>

We formulate the state equations for tme- and frequency-domain aalysis of switched-capacitor networks (SCN's) using charges associated with topologically identifiable structures in a network as network variables. The method effectively combines variable elimination to reduce matrix sizes with redundancy elimination to reduce memory requirements for many-phases SCN's. The frequency-domain analysis equations are formulated in such a way that computation can be done in a simple iterative manner akin to time-domain analysis but without using discrete Fourier transform. Two speed-up algorithms based on the proposed formulation for input and output sampling are presented.

A graph-theoretic description of the problem of layout of CMOS circuits in the style of gate matrix in minimum area is presented. The problem is formulated as one of finding two assignment functions f and h such that the layout L(f, h) requires the minimum number of rows of the gate matrix. The function f maps the distinct gates of the transistors to the columns of the gate matrix and the function h maps the nets of the circuit to the rows such that all of the vertical diffusion runs which connect nets on different rows are realizable. A two-stage approach to the problem is described which first obtains a layout without regard to the vertical constraints and then rows are permuted to satisfy the constraints. Detailed algorithms and examples are given. The gate matrix layout of a 118-transistor circuit was obtained in 9 s on a mainframe computer.

The solution process of Ax = b is modeled by an acyclic directed graph in which the nodes represent the arithmetic operations applied to the elements of A, and the arcs represent the precedence relations that exist among the operations in the solution process. Operations that can be done in parallel are identified in the model and the absolute minimum completion time and lower bounds on the minimum number of processors required to solve the equations in minimal time can be found from it. Properties of the model are derived. Hu's level scheduling strategy is applied to examples of sparse matrix equations with surprisingly good results. Speed-up using parallel processing is found to be proportional to the number of processors when it is 10-20 percent of the order of A.