The search for the Holy Grail in Analog Design Automation
Introduction:
The optimization of analog circuit sizing has long been recognized as a challenging task within the field. This difficulty has given rise to two distinct approaches to design optimization:
1. Knowledgebased optimization
2. Simulationbased optimization.
In the first approach, referred to as knowledgebased optimization, tools like OASYS and ASTRX/OBLX have been developed. These tools operate on the basis of predefined rules and expert knowledge, guiding the optimization process. On the other hand, simulationbased optimization, as exemplified by ANACONDA, relies on simulating the circuit's behavior under various conditions to determine the optimal sizing.
Despite the efforts made by both schools of thought, neither has been successful in creating a widely accepted commercial design automation tool that fully satisfies the expectations of industrial design experts. These expectations include aspects such as design productivity, full traceability, easy debugging, design reuse, quality assurance, minimum cost, and comprehensive design documentation.
Therefore, the question remains: Is analog circuit sizing optimization an NPComplete or NPHard problem ?
Our intention is to delve into this subject matter, carefully dissecting the mathematical principles that underpin this claim, while also striving to construct a fresh computational model capable of effortlessly transforming this problem into a Ptype one.
P, NP, NPComplete and NPHard problems:
In computational complexity theory, P, NP, NPcomplete, and NPhard are classes of decision problems.
Figure 1: Relations between algorithm complexities.
P (Polynomial Time): P is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time. This means that the solution can be found efficiently with a time complexity of O(n^k), where n is the size of the input and k is a fixed constant.
NP (Nondeterministic Polynomial Time): NP is the class of decision problems that can be verified by a nondeterministic Turing machine in polynomial time. This means that given a potential solution, it can be verified efficiently with a time complexity of O(n^k). However, finding the solution itself may be computationally expensive.
NPcomplete: NPcomplete problems are a subset of NP problems. A decision problem is NPcomplete if every problem in NP can be reduced to it in polynomial time. In other words, if a polynomialtime algorithm exists for one NPcomplete problem, then it would imply the existence of polynomialtime solutions for all NP problems. This makes NPcomplete problems some of the most challenging and important problems in computer science.
NPhard: NPhard problems are a broader class that includes both NP and NPcomplete problems. NPhard problems are at least as hard as the hardest problems in NP. They may or may not be in NP themselves. Essentially, NPhardness implies that a problem is as difficult as the most difficult problems in NP but does not necessarily mean it is solvable within polynomial time.
Is P=NP Statement Valid?
A question that’s fascinated many computer scientists is whether or not all algorithms in NP belong to P.
For our definitions, we assumed that P≠NP, however, P=NP may be possible. If it were so, aside from NP or NPComplete or problems being solvable in polynomial time, certain algorithms in NPHard would also dramatically simplify. For example, if their verifier is NP or NPComplete, then it follows that they must also be solvable in polynomial time, moving them into P = NP = NPCompete as well.
We can conclude that means a radical change in computer science and even in the realworld scenarios. Currently, some security algorithms have the basis of being a requirement of too long calculation time. Many encryption schemes and algorithms in cryptography are based on the number factorization which the bestknown algorithm with exponential complexity. If we find a polynomialtime algorithm, these algorithms become vulnerable to attacks.
How did Analog Circuit Optimization start?
Since the 80's, analog circuit optimization was assumed to be NP due to its complex nature. Following the definitions of NP mentioned above, NP problems can be easily verified but are hard to solve. Consequently, it was decided to use an optimization engine to generate candidate solutions and verify each candidate by a performance evaluator such as SPICE simulators. This point of view led to the emergence of simulationbased optimization tools such as ASF, ANACONDA and MAELSTROM as depicted in Figure 2.
Figure 2: (a) Simulationbased optimization flow, (b) Observation made in [31]
A general and honest observation has been outlined in [31]: despite the huge computational effort used in this work to optimize the Equalizer, the optimization engine was not capable of reaching the precision of hand analysis.
This observation is very fundamental to our analysis and the real questions become:
 Why analog designers can reach a precision that may not be achieved using high computational effort ?
 Why simulationbased optimization failed to meet hand analysis despite the existence of a SPICE simulator in the loop ?
A Deeper Look into SPICE Computational Model:
In order to determine how efficient is the computational model implemented in SPICE simulator, we analyzed graphically the nonlinear DC analysis since it is the only backbone algorithm in SPICE engine. Other analyses such as AC and TRANSIENT are simply variants of the nonlinear DC analysis:
 The AC analysis is a linearization of the circuit around the DC operating point.
 The TRANSIENT analysis is a nonlinear DC analysis with initial conditions varying with time for each timestep.
To measure the complexity of the nonlinear DC analysis implementing the NewtonRaphson algorithm, we modeled the DC analysis as a cyclic graph as illustrated below:
Figure 3: Graph modeling of the nonlinear DC analysis implemented in SPICE.
A deeper look into the graph on the right side reveals how complex is the computation model in SPICE. Loops exist on the level of each vertical branch. Forward and backward values propagation occur from one branch to the next one increasing the dependency between branches. These propagations exist due to the presence of diagonal and nondiagonal Jacobian elements. All these computations occur at each iteration of the nonlinear DC simulation. We conclude that the computational model of SPICE inherently requires lots of computations and suffers from convergence issues due to the presence of Jacobian elements in each forward and backward propagation. Over the years, lots of research efforts led to the reduction of the complexity of the DC analysis to O(n^1.2) = α. n^1.2 where n is the number of node voltages to compute.
To summarize this section, the computational model of SPICE:
 Has a Matrixbased formulation.
 Implements simultaneous nonlinear equations resolution.
 Each iteration requires a large number of computations.
 Jacobian computation becomes a major difficulty.
The next question that arises is the following: Analog designers do not explicitly compute the Jacobian matrix during hand analysis, so how they do it?
Computational Model used by an experienced analog designer
Figure 4: Analog designer manual structured analysis of a typical analog circuit.
To compute the size W1 of the upper transistor in the schematic, the design would propose values for the biasing current, MOS Length and the node voltage Vn1, then he will compute W1 using a simple MOS model. Next, the designer will propagate Vn1 to the next transistor, proposes a vnode voltage Vn2 and then computes W2 assuming same current and Length, and so on.
We conclude that during hand analysis, the model of computation followed by the analog designer is much simpler than the SPICE one since:
 Structured Resolution since each node voltage is computed in sequence.
 No matrixbased formulation.
 Each iteration requires only one computation to determine the size
 Jacobian computation disappeared
Here, the big question that arises is the following: Can we combine the simplicity of the structured resolution approach used during hand analysis with the precision of SPICE simulation to design, explore, optimize and migrate analog circuits ?
Structured Resolution Approach for Analog Design Automation
It is possible to build an analog synthesis system that mimics analog designer behavior during hand analysis but does the same job at SPICE precision. This can be quite easily achieved by replacing MOS level 1 models with standardized API interface for Process Design Kits that are compatible with all device types and all foundries PDKs. The resulting approach is illustrated in Figure 5, where sizing and biasing functions F interface with PDK files to compute the sizes and biases of each transistor sequentially.
Doing so, an efficient Cognitive Computing system has been created by capitalizing on the efficiency of human designers while supported by the accuracy of computer simulation programs.
Figure 5: Mimic human cognitive behavior with SPICE accuracy
Here, the next question that arises is: How to build a product to automate analog design and migration?
DigitallyInspired Analog Circuit Synthesis System
Figure 6 below shows how to build an analog circuit synthesis flow similar to digital highlevel synthesis systems that are very mature and in production since decades. The flow for analog will rely on four modules :
1 The schematic scheduler: This module scans the schematic and determines the sequence of transistors to compute in order. Here, it acts like a human designer and implementing cognitive computing strategies.
2 The Function Allocator: This module will assign a sizing and biasing function that shall compute the device biases and geometries based on its connectivity context.
3 Technology Mapper: This module links each transistor to the PDK files based on the requested device variant in order to size and bias the device accurately using standard compact device models or simply accurate DC simulations.
4 Graph Evaluator: In this analog flow, we previously described steps (1)(3) as directed acyclique graphes that shall be evaluated in step (4) to get sizes and biases.
Figure 6: Proposed architecture of the digitallyinspired analog synthesis system
Ptype Knowledge Graphs Generated by the synthesis system
To appreciate the proposed methodology, we illustrate in Figure 7 the Miller OTA amplifier to be synthesized:
Figure 7: Miller OTA amplifier
Figure 8 shows the corresponding generated bipartite knowledge graph taking as input the designer chosen parameters and the topology of the OTA Miller and computing the size and bias of each device as the output of its allocated function.
Figure 8: Ptype computational model describing the DC design space of the Miller OTA amplifier
The complexity of this knowledge bipartite graph is linear with respect to the number of devices or nodes in the circuit. Therefore, it represents the Ptype computational model for the OTA Miller describing the full design space of the DC operating point. It has been generated cognitively and without any datadriven learning.
We conclude that the analog circuit sizing optimization task is neither NPComplete nor NPHard. It is solvable as a Ptype problem.
References:

R.Harjani, R.A.Rutenbar, L.R.Carley, "OASYS: a framework for analog circuit synthesis," IEEE Transactions on ComputerAided Design, vol. 8, no. 11, pp. 1247–1266, 1989.

M.G.R.DeGrauwe, E.D.O.Nys, J.Rijmenants, S.Bitz, B.L.A.G.Goffart, E.A.Vittoz, S.Cserveny, C.Meixenberger, G.vanderStappen, H.J.Oguey, "IDAC: an interactive designtool for analog CMOS circuits," IEEE Journal of SolidState Circuits, vol. 22, no. 6, pp. 1106–1116, 1987.

H.Y.Koh, C.H.Sequin, P.R.Gray, "OPASYN: a compiler for CMOS operational amplifiers," IEEE Transactions on ComputerAided Design, vol. 9, no. 2, pp. 113–125, 1990.

W.Nye, D.Riley, A.SangiovanniVincentelli, A.L.Tits, "DELIGHT.SPICE: an optimizationbased system for design of integrated circuits," IEEE Transactions on ComputerAided Design, vol. 7, no. 4, pp. 501–518, 1988.

E.S.Ochotta, R.A.Rutenbar, L.R.Carley, "Synthesis of highperformance analog circuits in ASTRX/OBLX," IEEE Transactions on ComputerAided Design, vol. 15, no. 3, pp. 273–294, 1996.

G.V.derPlas, G.Debyser, F.Leyn, K.Lampaert, J.Vandenbussche, G.Gielen, W.Sansen, P.Veselinovic, D.Leenaerts, "AMGIE: a synthesis environment for CMOS analog integrated circuits," IEEE Transactions on Circuits and Systems, vol. 20, no. 6, pp. 1037–1058, 2001.

M.Krasnicki, R.Phelps, R.A.Rutenbar, L.R.Carley, "MAELSTROM: efficient simulationbased synthesis for custom analog cells," in Proceedings of the Design Automation Conference, 1999, pp. 945–950.

R.Phelps, M.Krasnicki, R.A.Rutenbar, L.R.Carley, J.R.Hellums, "ANACONDA: robust synthesis of analog circuits via stochastic pattern search," IEEE Transactions on ComputerAided Design, vol. 19, no. 5, pp. 567–570, 2000.

M.J.Krasnicki, R.Phelps, J.R.Hellums, M.McClung, R.A.Rutenbar, L.R.Carley, "ASF: a practical simulationbased methodology for the synthesis of custom analog circuits," in Proceedings of the IEEE International Conference on ComputerAided Design, 2001, pp. 350–357.

A.Doboli, R.Vemuri, "Explorationbased highlevel synthesis of linear analogue systems operating at low/medium frequencies," IEEE Transactions on ComputerAided Design, vol. 22, no. 11, pp. 1556–1568, 2003.

R.A.Rutenbar, G.Gielen, "Hierarchical Modeling, Optimization and Synthesis for SystemLevel Analog and RF Designs," vol. 95, IEEE Press, 2007, pp. 1556–1568.

G.Stehr, M.Pronath, F.Schenkel, H.Graeb, K.Antreich, "Initial sizing of analog integrated circuits by centering with implicit topology given specification," in Proceedings of the IEEE International Conference on ComputerAided Design, 2003, pp. 241–246.

D.Stefanovic, M.Kayal, P.A.D: a new interactive knowledgebased analog design approach," Analog Integrated Circuits and Signal Processing, vol. 45, pp. 291–299, 2005.

D.Stefanovic, M.Kayal, "Structured Analog CMOS Design," Kluwer Academic Publishers, 2009 (ISBN 9781402085727).

D.M.Binkley, C.E.Hopper, S.D.Tucker, B.C.Moss, J.M.Rochelle, D.P.Foty, "ACAD methodology for optimizing transistor current and sizing in analog CMOS design," IEEE Transactions on ComputerAided Design, vol. 22, no. 2, pp. 225–237, 2003.

D.Binkley, "Tradeoffs and Optimization in Analog CMOS Design," John Wiley and Sons Inc., 2008 (ISBN 9780470031360).

T.Morie, H.Onodera, K.Tamaru, "A method for analog circuit design that stores and reuses design procedures," Electronics and Communications in Japan, vol. 77, no. 1, pp. 87–96, 1994.

G.Gielen, P.Wambacq, W.Sansen, "Symbolic analysis for analog circuits: a tutorial overview," Proceedings of the IEEE, vol. 82, no. 2, pp. 287–304, 1994.

G.Gielen, W.Sansen, "Symbolic Analysis for Automated Design of Analog Integrated Circuits," Kluwer Academic Publishers, 1991 (ISBN 0792391616).

F.Fernandez, A.RodriguezVazquez, J.L.Huertas, G.Gielen, "Symbolic Analysis Techniques: Applications to Analog Design Automation," IEEE Press, 1997 (ISBN13 9780780310759).

F.D.Bernardinis, M.Jordan, A.SangiovanniVincentelli, "Support vector machines for analog circuit performance representation," in Proceedings of the Design Automation Conference, 2003, pp. 964–969.

Cochran & Cox, "Experimental Designs," John Wiley and Sons Inc., 1992, ISBN 0471545678.

F.Silveira, D.Flandre, P.G.A.Jespers, "A gm/ID based methodology for the design of CMOS analog circuits and its application to the synthesis of a silicononinsulator micropower OTA," IEEE Journal of SolidState Circuits, vol. 31, no. 9, pp. 1314–1319, 1996.

P.Jespers, "The gm/ID methodology," in "A Sizing Tool for LowVoltage Analog CMOS Circuits," Kluwer Academic Publishers, 2010 (ISBN 9780387471006).

C.Enz, F.Krummenacher, E.Vittoz, "An analytical MOS transistor model valid in all regions of operation and dedicated to lowvoltage and lowcurrent applications," Analog Integrated Circuits and Signal Processing, vol. 8, pp. 83–114, 1995.

C.C.Enz, E.A.Vittoz, "ChargeBased MOS Transistor Modeling: The EKV Model for LowPower and RF IC Design," John Wiley and Sons Inc., 2006 (ISBN 9780470855416).

M.C.Schneider, C.GalupMontoro, "CMOS Analog Design Using AllRegion MOSFET Modeling," Cambridge University Press, 2010 (ISBN 9780521110365).

J.Vlach, K.Singhal, "Computer Methods for Circuit Analysis and Design," Kluwer Academic Publishers, 1983 (ISBN 0442281080).

H.Graeb, S.Zizala, J.Eckmueller, K.Antreich, "The sizing rules method for analog integrated circuit design," in Proceedings of the IEEE International Conference on ComputerAided Design, 2001, pp. 343–349.

H.E.Graeb, "Analog Design Centering and Sizing," Kluwer Academic Publishers, 2007 (ISBN 9781402060038).

R.Phelps, M.J.Krasnicki, R.A.Rutenbar, L.R.Carley,J.R.Hellums, A case study of synthesis for industrialscale analog IP: redesign of the equalizer/filter frontend for an ADSL CODE, in Proceedings of the IEEE 37th Design Automation Conference, DAC'00, June 2000, Pages 1–6.

A.Malak, Y. Li, R. Iskander, F. Durbin, F. Javid, M. M. Louërat, A. Tissot, J. M. Guebhard : “Fast multidimensional optimization of analog circuits initiated by monodimensional global Peano explorations”, Integration, the VLSI Journal, vol. 48, pp. 198212, (Elsevier) (2015).

R. Iskander, M. M. Louërat, A. Kaiser : “Hierarchical sizing and biasing of analog firm intellectual properties”, Integration, the VLSI Journal, vol. 46 (2), pp. 172188, (Elsevier) (2013).

R. Iskander, M. M. Louërat, A. Kaiser : “Automatic DC operating point computation and design plan generation for analog IPs”, Analog Integrated Circuits and Signal Processing, vol. 56 (12), pp. 93105, (Springer Verlag) (2008).