An error-controlled methodology for approximate hierarchical symbolic analysis

ISCAS 2000 - IEEE International Symposium on Circuits and Systems, May 28-31, 2000, Geneva, Switzerland An Error-Controlled Methodology for Approximate Hierarchical Symbolic Analysis 0. Guerra, J.D. Rodriguez-Garcia, E. Roca, F. V. Fernindez and A. Rodriguez-Vizquez Instituto de Microelectrhica de Sevilla, Centro Nacional de Microelectr6nica, Sevilla, SPAIN Phone: +34 955056666, FAX: +34 955056686 E-mail: { guerra, jdavid, eli, pacov, angel} @imse.cnm.es Abstract* Limitations of existing approaches for symbolic analysis of large analog circuits are discussed. To address their solution, a new methodology for hierarchical symbolic analysis is introduced. 'lke combination of a hierarchical modeling technique and approximation strategies, comprising circuit reduction, graph-based symbolic solution of circuit equations and matrix-based error control, provides optimum results in terms of speed and quality of results. 1. Introduction Symbolic analyzers are aimed to analyze circuits in which part or all their parameters are symbols. The generated expressions provide the keys to understanding the intricate mechanisms underneath the circuit operation. Its applications to providing insight in interactive circuit design, generating behavioral models for library characterization, generating design equations for synthesis or optimization tasks, are well-known [I]. A major problem in the application of these techniques was the exponential growth of the complexity of the symbolic expressions with the circuits sizes. Different solutions have been proposed to palliate this problem. On the one hand, Simplification Before (SBG) and During (SDG) Generation approaches [2]-[4] have extended the analyzable circuit sizes and have made the symbolic expressions interpretable but are still insufficient for very large circuits. Hierarchical analysis techniques constitute an alternative to analyze very large circuits although reported techniques do not incorporate approximation capabilities, making interpretation and fast evaluation of the results a problem [5]-[7]. Recently, new techniques based on Determinant Decision Diagrams have been proposed, which are able to represent the exact circuit behavior in a compact, although uninterpretable, form t81 ,PI. The methodology presented in this paper is built on the ideas in [IO] to formulate and implement a hierarchical analysis methodology able to incorporate the circuit reduction and dominant contribution strategies contained in SBG and SDG techniques. The paper is organized as follows. Section 2 reviews and compares existing symbolic analysis techniques. Section 3 describes the hierarchical modeling methodology while Section 4 introduces the approximate analysis strategy. Finally, Section 5 presents experimental results to assess the quality of the methodology. 2. Review of previous approaches 2.1. Approximate flat analysis techniques The first approximation approaches were based on Simplification After Generation (SAG) techniques, that prune the least significant symbolic terms once the exact expression has been computed. * This work has been supported by the ESPRIT Project #21812 (AMADEUS) and the Spanish C.I.C.Y.T. under contract TIC97-0580. Although the interpretability was greatly improved, the initial generation of the exact expression exhausted the computer resources even in case of medium size circuits [I]. To solve both, the interpretability and the excessive consumption of computer resources, two new ideas were introduced: SBG techniques, which simplify the system of circuit equations (at the matrix or the graph level) before being solved; and SDG techniques, which calculate directly an approximated solution of the system of circuit equations, containing ,only the dominant contributions [2]-[4]. 2.2. Hierarchical analysis techniques Traditionally, a three step approach has been used (see M.M. Hassoun's "Hierarchical Symbolic Analysis of Large Analog Circuits" - Chapter 5 in [I] for a detailed review): Division of the circuit in subblocks (circuit partitioning). Characterization of the lowest level blocks in terms of their inputs and outputs (terminal block analysis). Iterative characterization of blocks in terms of their inputs and outputs by performing operations on the charaterizations of the constituent subblocks (middle block analysis) For terminal and middle block analysis, three approaches have been reported: Coates flowgraph, Mason flowgraph and direct network methods. The Coates flowgraph method requires to build the Coates graph, which is then partitioned [5]. Partitioning defined by the user is not possible. Besides, since the Coates graph does not correspond with circuit nodes and branches, partitioning information cannot be directly mapped to the circuit level. Mason signal flowgraph techniques use reduction techniques on Mason's graphs to yield a description of each block in terms of its input and output nodes only [6]. Finally, a combination of the blocks is made applying the same reduction techniques to get a description for the entire circuit. The direct network method operates by reducing the Modified Nodal Analysis (MNA) matrix, representing each subcircuit into a Reduced ModiJied Nodal Analysis matrix, which only depends on terminal nodes of the block. Afterwards, a successive recombination of such matrices is performed to obtain a reduced matrix representing the entire circuit 271. 2.3. DDD-based analysis techniques The technique is based on the representation of the symbolic expressions by means of Determinant Decision Diagrams, that are signed rooted acyclic graphs with two terminal vertices. This representaion is built from the matrix that models the circuit, exploiting the sparsity and sharing of product terms [8], therefore it finds its main advantage in case of repetitive topologies (like ladderstructured networks). 2.4. Comparative discussion Although there is not a precise limit for the applicability of approximate Rat analysis techniques (it depends on the circuit 0-7803-5482-6/99/$10.00 02000 IEEE 111-133 size, model complexity, circuit connectivity, tightness of error specifications), such boundary exists. Beyond, alternative methods are needed; in particular, those exploiting the inherent hierarchy in the constructive process of large circuits. The hierarchical Coates flowgraph method will not deserve consideration due to its inability to handle pre-partitioned circuits. Neither the direct network method, nor the Mason flowgraph method incorporate approximation techniques. This exceedingly hampers their application to large practical circuits which is corroborated by the fact that reported experimental results use extremely simple block models; i.e. filters using ideal models for the opamps. DDD-based methods represent circuit behavior in a compact form. Although, such compact structure is uninterpretable and CPU-intensive to build, their main advantage is their fast numerical evaluation. When they are used to generate approximate (interpretable) symbolic expressions [8] they are not competitive to existing SBG and SDG approaches. They have also been applied to hierarchical analysis in a similar fashion to the Direct Network method and using DDDs to represent matrix determinants [9]. However, no error-controlled approximation of symbolic expressions extracted from such DDD has been reported. 3. Hierarchical modeling methodology In our methodology, blocks are partitioned (defined by the user or automatically performed) in several hierarchical levels. This hierarchical structure can be represented as an inverted tree, as the example in Fig. 1 shows. Figure 1. Example of inverted tree representation. Leaf nodes (terminal blocks) are modeled by the substitution of constituent devices by their corresponding models. Non-leaf nodes (middle blocks) are modeled using a (trans)admittance description as Fig. 2 illustrates for a three-terminal block. Conceptually, each (trans)admittance is a function of the models at the immediate hierarchical level. An analogous description results when subblock matrices are combined in the Direct Network approach [7], but such methodology prevents the application of error-controlled approximation strategies. f Figure 2. (Trans)admittance description of blocks. The methodology presented herein generates approximated expressions for the needed (trans)admittances of each middle block as a function of the (trans)admittances of the sub-blocks at the following level down the hierarchy (device models in case of teiminal blocks). 4. Approximation strategy Our approximate analysis methodology follows the flow diagram in Fig. 3. It starts from a hierarchical circuit description and information on the network function to calculate, magnitudelphase error constraints and frequency intervals. Hierarchically-decomposed Circuit Internal Block Size Checking Partition Figure 3. Module structure. The Circuit Reduction module performs node contractions and device removals whose contribution to the global circuit behavior is negligible. The error introduced by these circuit transformations is carefully controlled by using algorithms based on interval analysis techniques to guarantee that error specifications are not violated within the specified frequency range [4]. Circuit equations must be solved to control magnitude/phase errors. This is a numerical process and is therefore more efficiently performed by using an A4NA matrix formulation and sparse matrix techniques for its solution. This circuit reduction technique is applied to the complete flat circuit, although the predefined partitions are formally kept, so that they can be rebuilt when the reduction process is finished. Since very efficient sparse matrix techniques are used in the error evaJuation, no significant advantage is gained from applying the reduction technique to the component blocks separately. Moreover, a separate application to each block would require an error propagation mechanism at this early stage of the analysis process. This necessarily yields more conservative results (less reduced circuits) and, comequently, has a negative impact on the global performance of the analysis methodology. The effect of the circuit reduction is not only the size reduction of the terminal blocks but also the elimination of many of the modeling (trans)admittances of the middle blocks. After the circuit reduction process, the hierarchical structure is reconstructed and Block Checking step starts. If a simplified block contains a too small number of devices or internal nodes, analyzing it as an independent block becomes very inefficient. Then, it is advisable to join the block to its best neighbor or incorporate it into the immediately upper hierarchical level. On the contrary, even after the circuit reduction, some block may still contain too many nodes and devices for an efficient symbolic expression generation. In this case, an internal partitioning is provided which finds optimal blocks for the subsequent expression generation module. The internal partitioning mechanism provides the solution for the case in which no pre-defined blocks are given. After the circuit 111- 134 reduction step, the circuit at hand is internally partitioned to generate a number of blocks that enables an optimal result in terms of computational time and expression complexity. To preserve user requirements, both processes: interconnection and partitioning, can be controlled by the user. Once the hierarchical block structure has been rebuilt and checked, a circuit where blocks are modeled in terms of the (trans)admittances is built up. Then, appropriate analysis algorithms generate approximate symbolic expressions for each (trans)admittance of each block in the structure as a function of the component devices of that block. Analogous analysis algorithms are applied to obtain the desired network function (defined by the global input/output signals of the circuit) in terms of the (trans)admittances modeling the blocks at the uppermost hierarchical level. When symbolically analyzing a block, a set of network equations (topological and constitutive relationships) has to be solved. For the approximate symbolic solution of a set of linear equations, graph methods have proven to be superior [4]. Efficient techniques available for flat circuits (based on the two-graph method) can be used at each hierarchical level, as terminal blocks are flat interconnections of basic circuit elements, and the same happens in middle blocks once the component subblocks are replaced by the corresponding (trans)admittances. The operation of the error-controlled term generation is shown in Fig. 4. Initially, a frequency value is chosen. Each element has its admittance as associated weight. The weight of each (trans)admittance is a complex number because it functionally depends on all the devices composing such block. The contribution of each (trans)admittance to the global circuit behavior is then numerically evaluated. This is efficiently done using a hierarchical MNA formulation and sparse techniques to solve the matrices. The magnitude of these contributions indicates which term generator must become active. The generation process continues iteratively until the error criterion is met. Obviously, this is guaranteed only at the selected frequency sample. An algorithm for maximum error detection, which relays in a robust numerical reference generator and interval analysis Original Circuit No Generator Figure 4. Error-controlled expression generation techniques is used to detect frequency values where the errors are exceeded [4]. Then, the process is repeated until the error criteria are met in the required frequency range. 5. Experimental results Two examples are analyzed using the proposed technique. Each is . representative of different application scenarios: a circuit composed of blocks (too large to be analyzed using flat analysis algorithms) and a building block described at the transistor level. 5.1. A band-pass filter The first example is a decision band-pass filter used in an FSK modem and shown in Fig. 5(a), where the OTA transistor-level schematics in Fig. 5(c)-(d) and the transistor model in Fig. 5(b) were used. The magnitude/phase error constraints are ]AMag\ 5 1 dB , ]APhs( I5 degrees in 10 Hz I f 5 lO'Hz. 4 .. Figure 5. (a) Band-pass filter; (b) small-signal model; (c) biasing OTA; (d) OTA schematics. Previously existing hierarchical approaches did not incorporate approximation strategies and, therefore, could analyze the circuit in Fig. 5(a) only if very simple macromodels instead of transistorlevel descriptions for the OTAs were used. The small-signal expansion of the circuit yields a circuit model with 618 devices and 45 nodes. After the circuit reduction step, the expanded model contains 67 devices and 26 nodes, which means a large reduction, but not enough for flat analysis algorithms. Applying our hierarchical approach, the following transfer function is obtained in 100 seconds of CPU time: (1) taB9.bp.in . (aB8.lp.lp + C, . s) - taB7.bp.l~ taB8.lp.bp + aB8.lp.lp. C, . s + C, . C, . s2 Tf = where the (trans)admittances are the following approximate symbolic expressions: (3) 111-135 (-gm I I gr~ 14gv~ (gds, + gds,) - gm ,2giii 13gm lBgd~~2 taB8.lp.bp= gin,lgin1,(grn12 + gds2 + gds,) (5) The error between the magnitude and phase behavior predicted by eqs. (1)-(5) and the magnitude and phase behavior of the original circuit is shown in Fig. 6. 1.0 U 0.5 1 ? 1 o5 lo6 frequency (HZ) io7 5.0 1 I -3 U 1 o4 1 o5 lo6 frequency (HZ) io7 Figure 6. Magnitude and phase errors. 5.2. pa741 amplifier Now, the p741 operational amplifier in Fig. 7 will be analyzed. The magnitude/phase error constraints ‘are (AMng( I 3 dB , (Apkrl I 10 degrees in 1 Hz I f I 106Hz, to include the complete gain-bandwidth product of the amplifier. Although the netlist is input with a predefined partitioning, which is shown in Fig. 7, the internal partition size checking detects that the block structure after the circuit reduction step is not adequate to be efficiently handled. Therefore, it provides some partitioning suggestions (joining Bias, SC-prot and Output stages to the upper level). Term generation yields, then, the following voltage gain: (6) tuSec 17.9 . tulnp9.4 go,3B’ (ulnp9.9 + aSec9.9) - tuSec9.17. tuSecl7.9 H(s) = where the (trans)admittances of the blocks are gm3 ’ g!n6 ’ (gml + s ’ CZI) talnp9.4 = - uInp9.9 = go4 gm5 . (grnl + girt3) gg. 5’16. $‘I7 uSec9.9 = 911116. S“117 These results are obtained in 4.8 seconds of CPU time. A flat analysis tool with the same error specifications provides a network function containing 53 symbolic terms. 6. Conclusions This paper has introduced a methodology for the incorporation of approximation strategies into a hierarchical analysis technique. On the one hand, this overcomes the problems of approximate flat analysis techniques when addressing very large circuits. On the other, the inherent hierarchy of large circuits is respected but the introduction of approximation techniques makes the results more interpretable and more efficiently evaluated than with conventional hierarchical analysis techniques. Figure 7. pa741 operational amplifier with explicit block partitioning and small-signal model for transistors. 7. References F. V. Femindez, A. Rodriguez-Vizquez, J. L. Huertas and G. Gielen, Eds., Symbolic Analysis Techniques. Applications to Analog Design Automation. Piscataway, NJ: IEEE Press, 1998. P. Wambacq, F.V. Femindez, G. Gielen, W. Sansen and A. Rodriguez-Vizquez, ”Efficient symbolic computation of approximated small-signal characteristics of analog integrated circuits” IEEE J. Solid-State Circuits, vol. 30, No. 3, pp. 327- 330, March 1995. Q. Yu and C. Sechen, “A unified approach to the approximated symbolic analysis of large analog integrated circuits” IEEE Trans. Circuits and Syst.-I, Vol. 43, No. 8, pp. 656-669, 1996. 0. Guerra, J.D. Rodriguez-Garcia, E. Roca, F.V. Fernlndez and A. Rodriguez-Vhquez, “A simplification before and during generation methodology for symbolic large-circuits analysis” Proc. IEEE Inc. Con$ Electronics, Circuits andSystems, Vol. 3, pp. 81-84, Lisbon, September 1998. J. A. Starzyk and A. Konczykowska, “Flowgraph analysi:s of large electronic networks,” IEEE Trans. on Circuits and Syst., M. M. Hassoun and K. S. McCarville, “Symbolic analysis of large-scale networks using a hierarchical signal flowgraph approach,” Analog Int. Circuits and Signal Proc., vol. 3, pp. 3 1- 42, Kluwer, Boston, 1993. M. M. Hassoun and P. M. Lin, “A hierarchical network approach to symbolic analysis of large-scale networks,” IEEE Trans. on Circuits and Syst.4, vol. 42, No. 4, pp. 201-211, April 1995. X.D. Tan and C.J.R. Shi, “Interpretable symbolic small-signal characterization of large analog circuits using determinant decision diagrams“, Proc. of the Design Automation Con$, pp. X.D. Tan and C.J.R. Shi, “Hierarchical symbolic analysis of large analog circuits with determinant decision diagrams”, Proc. IEEE Int. Symp. Circuits and Systems, pp. 3 18-32]. June 1998. vol. CAS-33, NO. 3, pp. 302-315, March 1986. 448-453, March 1999. [lo] 0. Guerra, J.D. Rodriguez-Garcia and A. Rodriguez-Vfizquez, “True Hierarchical Symbolic Analysis of Large-scale Analog Integrated Circuits” Proc. Int. Workshop on Symbolic Methods &Applications to Circuit Design, pp. 164-167, October 1998. 111- 136