Is Front-End Analog Design Automation an NP-type or simply a P-type problem ?
TimeWednesday, July 13th5pm - 6pm PDT
LocationLevel 2 Exhibit Hall
Event Type
Engineering Track Poster
Engineering Tracks
Back-End Design
Embedded Systems
Front-End Design
DescriptionSince decades, the automated front-end design of analog circuits has been considered as a difficult problem to solve. It was always labelled as an NP problem since it is difficult to solve in polynomial time as a function of the circuit variables. It is known that NP problems have efficient verifiers that verify in polynomial time if a candidate solution is correct. Therefore, researchers proposed automated analog design flows that use optimization algorithms in-a-loop with spice simulators. The optimization algorithms generate candidate solutions that are verified by running a spice simulation and a fitness score is computed by comparing the difference between evaluated performances and specifications. Despite all efforts, these design flows did not reach wide acceptance in the design community and few tools were commercialized with limited success.

In this presentation, we analyze the theoretical bases on which the design of analog circuits has been considered as NP-type problem and we introduce a novel mathematical modeling approach using graph theory to reformulate the problem as P-type problem, that is, solvable in polynomial time according to the variables of the circuit to be determined. Automated analog design of an industrial testcase will be demonstrated proving the huge ROI of our approach on productivity gain and design quality. It will be concluded that automated front-end design of analog circuits is a P-type problem.