Chandu Visweswariah IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598 [email protected] Dynamic Tuning for High–Performance Custom Digital Design Of 77:1 Dynamic Tuning for High–Performance Custom Digital Design Chandu Visweswariah Acknowledgements Dynamic Tuning for High–Performance Custom Digital Design Andrew R. Conn, Applied Mathematics, IBM Watson Ruud A. Haring, Integrated System Design, IBM Watson Chandu Visweswariah Of 77:2 1. Outline Introduction and motivation 2. Circuit simulation 3. Time–domain gradient computation 4. Nonlinear optimization 5. Case study – JiffyTune: algorithms and implementation – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective Dynamic Tuning for High–Performance Custom Digital Design 6. Conclusions, future work and pointers to the reading list Chandu Visweswariah Of 77:3 Introduction and Motivation Update design custom design poses challenges in performance (delay and slew), area, power, noise, etc.,. competitive environment drives aggressive circuit tuning formerly a manual, tedious, error–prone procedure Simulate Good enough? Dynamic Tuning for High–Performance Custom Digital Design Design re–use not easy! Chandu Visweswariah Of 77:4 Dynamic Tuning dynamic tuning implies automatic tuning based on dynamic or ‘‘pattern–driven” simulation hence dynamic tuning requires ‘‘input patterns” or ‘‘vectors” Static Tuning 25% Dynamic Tuning Piecewise approximate 5% Dynamic Tuning for High–Performance Custom Digital Design SPICE– based 1% Accuracy Sensitivity computation tuning only as good as patterns capture switching situations Chandu Visweswariah 10 30 1K 10K Size Of 77:5 Dynamic vs. Static Tuning Advantages of static tuning can handle larger problems (or problems of the same size faster) does not require sensitization patterns tunes only the ‘‘worst–case” or ‘‘most pessimistic” condition more applicable to control–flow than data–flow circuits requires either pre–characterized cells or simulation on the fly Advantages of dynamic tuning more accurate than static tuning does not suffer from the false–path problem more applicable to data–flow than control–flow circuits has no problem with custom circuits Dynamic Tuning for High–Performance Custom Digital Design The two types of tuning complement each other at different stages of the design process and on different kinds of circuits. Chandu Visweswariah Of 77:6 Statement of the Dynamic Tuning Problem Given a working circuit schematic with initial transistor sizes input signals or patterns or stimuli a precise statement of circuit performance requirements Determine optimal transistor size assignments While supporting... flexible objective functions and constraints simple bounds ratio–ing of transistors and grouping of similar structures i delay, rise/fall time, area and power measurements minimax optimization: min [ max { f i(x) } ] x easy–to–use graphical user interface in schematic environment Dynamic Tuning for High–Performance Custom Digital Design Must be able to tune a circuit with a few 100s of tunable transistors in a few minutes of CPU time. Chandu Visweswariah Of 77:7 Sample Dynamic Tuning Problem Tri–state driver D_in En D_in fast path D_in → D_out when enabled (minimize delay) Dynamic Tuning for High–Performance Custom Digital Design – small margin if D_in switches, larger margin if En switches break–before–make on P_drv and N_drv (constraints) Chandu Visweswariah D_out Of 77:8 Patterns Device models Structure of a Dynamic Tuner Circuit schematic Netlist Optimization problem description Simulator and gradient calculator Function and gradient values Dynamic Tuning for High–Performance Custom Digital Design Y Done? N Nonlinear optimizer Back–annotate Chandu Visweswariah Clobber transistor widths with new widths from non– linear optimizer Of 77:9 Circuit simulation Mini–outline 1. Introduction and motivation 2. – SPICE–like simulation – piecewise–approximate simulation 3. Time–domain gradient computation 4. Nonlinear optimization 5. Case study – JiffyTune: algorithms and implementation – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective Dynamic Tuning for High–Performance Custom Digital Design 6. Conclusions, future work and pointers to the reading list Chandu Visweswariah Of 77:10 Simulation incremental in time analytic device models (gradients and continuity required) 1% numerical accuracy limited to about 10K transistors (n1.5) in size complexity, (n) in simulation interval SPICE–like simulators Piecewise approximate simulators Of 77:11 examples: SPECS, ACES, PowerMill modeling approximations, typically piecewise approximate i–v characteristics, constant (grounded) capacitances event–driven special step a priori to create device models from SPICE models 5% accuracy, 2 orders of magnitude speedup over SPICE 100K transistors easily handled (n) in size complexity, (n) in simulation interval Dynamic Tuning for High–Performance Custom Digital Design Tuning accuracy is only as good as underlying simulator and device models! Chandu Visweswariah SPICE–like Simulation Equation formulation MNA, STA, TLA Integration for all time TR, BE, BD2, Gear Linearization until convergence Newton iterations Device model evaluation and solution Sparse LU factorization device model evaluation time is significant Dynamic Tuning for High–Performance Custom Digital Design Algebraic, non– linear ODEs Algebraic, non– linear equations Of 77:12 Algebraic, linear equations Both device modeling and analysis must be attacked to get reasonable speedups! Chandu Visweswariah v PIECEWISE APPROXIMATE SPECS, ACES, PowerMill i Run time CIRCUIT SPICE i = f(v) Piecewise Approximate Circuit Simulation SWITCH COSMOS, PARCH Dynamic Tuning for High–Performance Custom Digital Design Of 77:13 discretization in i–v characteristics allows event–driven simulation and variable accuracy event–driven simulation leads to latency/multi–rate exploitation creative integration methods employed to avoid matrix equations Chandu Visweswariah Accuracy Mini–outline 1. Introduction and motivation Time–domain gradient computation 2. Circuit simulation 3. – introduction to gradient computation – direct and adjoint methods – extension to nonlinear circuits and time–domain 4. Nonlinear optimization 5. Case study – JiffyTune: algorithms and implementation – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective Dynamic Tuning for High–Performance Custom Digital Design 6. Conclusions, future work and pointers to the reading list Chandu Visweswariah Of 77:14 signal Time–domain Gradient Computation delay width sensitivity lim width0 Dynamic Tuning for High–Performance Custom Digital Design delay width Of 77:15 time delay we would like to determine sensitivities not by finite differences or by perturbation, but by incremental methods; perturbation methods are inefficient and numerically ill–behaved performance measures like delay, slew, power, noise, area are sensitivity functions tunable parameters like transistor widths, interconnect sizes are sensitivity parameters in the direct method, the sensitivity of any number of functions with respect to one parameter can be computed efficiently in the adjoint method, the sensitivity of one function with respect to any number of parameters can be computed efficiently both methods are typically implemented as part of circuit simulator Chandu Visweswariah t 1 C i W eff t I ds W eff 2 C i W eff PW I ds W eff PW i t 2 C i W eff C i W eff PW Incremental Sensitivity and Chain Ruling i t 1 t 1 C i area W eff C i perimeter W eff C i area W eff PW C i perimeter PW W eff delay t 1 t 2 t 1 t delay 2 PW PW PW t I ds W eff 1 I ds W eff PW Of 77:16 number of ‘‘electrical” gradient computations can be very large example: problem with 10 delays, 10 slews and 1 power function, with 100 tunable transistors number of gradient evaluations (conservatively) = 40 iterations x 41 functions x 100 tunable transistors x 6 electrical parameters per transistor 1 Million! dependent (ratio–ed) transistor widths can be accommodated similarly by chain ruling Dynamic Tuning for High–Performance Custom Digital Design Incremental sensitivity computation has to be extremely efficient! Chandu Visweswariah Chandu Visweswariah v – . C ^ i I p v^ V p +– v^ + +– ^ R i i R p ^ v^ i R Ri p + ^ i C v ^ ^ p . i C dv C v p dt – – Sensitivity Analysis by the Direct Method + i R v iR v R i i R p p p vV +– V v p p iI i I p p + i v – C i C dv dt dv dv C i C ( ) p dt p dt p Key: directly differentiate BCRs Dynamic Tuning for High–Performance Custom Digital Design Of 77:17 V5 + – Direct Method: Procedure R1 +– i R1 R2 replace elements by directly differentiating BCRs to get sensitivity circuit reuse LU factors of original solution R3 R4 v R 4 , so p R 1 any number of functions, only one parameter Example: R1 R2 problem is to find R 1 Dynamic Tuning for High–Performance Custom Digital Design 4 solve for v^ R ; that is the required answer! R3 replace V 5 by a short; add a voltage source in series with R 1; Chandu Visweswariah + v^ R – 4 R4 Of 77:18 ^ ^ i i (v, p) di i dv i v dp p dp ^ or i G v^ I x G eq Linear model : i G eq v I eq v Direct Method: Extension to Nonlinear Circuits i i solution I eq v solution in the sensitivity circuit, ^ ^ i G solution v^ I x Dynamic Tuning for High–Performance Custom Digital Design extra source LU factors can be re–used think of it as the sensitivity of the linearized equivalent circuit at the DC solution Chandu Visweswariah Of 77:19 sensitivity circuit time nominal circuit Direct Method: Extension to Time–domain series of linear(ized) equivalents Problems LU factors can be re–used only if the Jacobians are identical Jacobians are identical provided time points are identical time points selected, however, only with consideration to solution of nominal circuit, hence may not be suitable to the sensitivity circuit must either use conservative time–steps or interpolate Jacobians event–driven simulators may have an advantage if event times of original and sensitivity circuit are inherently identical ^ Dynamic Tuning for High–Performance Custom Digital Design can find ‘‘full” transient sensitivity, like v^(t) or i(t) Chandu Visweswariah Of 77:20 Sensitivity Analysis by the Adjoint Method Matrix formulation of adjoint method Ax b A x A x b p p p f f Given a scalar function f (x), [ ] T[x] p x p f Postulate A T [ ] x f TA[x] T[b – A x] p p p p Then re–use LU factors of original solution; LU factors of A T are U T and L T any number of parameters, only one function . ^. Of 77:21 the adjoint of a dynamical system x Ax u is x A Tx^ u^ Dynamic Tuning for High–Performance Custom Digital Design electrical formulation based on Tellegen’s theorem Chandu Visweswariah Tellegen’s Theorem branches v bi v n ifrom– v nito i current of branches incident at each node 0 1, 0 Ai b 0 A topological incidence matrix v b A Tv n i ^ ^ i i ^ ^ same topology ^ ^ ^ ^ ^ Dynamic Tuning for High–Performance Custom Digital Design i vb ib vbT ib [ATvn]T ib vnT A ib 0 i ib vb ibT vb ibT AT vn [A ib]T vn 0 i Tellegen’s theorem Chandu Visweswariah KCL KVL Of 77:22 instantaneous power of branch 0 Conservation of energy v b Ti b 0 nodes Adjoint Sensitivity via Tellegen’s Theorem i ^ ^ bi i i i ^ i ^ v^b,i b i ^ Key relation! i ib vb 0 i (ib ib ) vb 0 i i b i b v^ b ) 0 i i Application of Tellegen’s theorem to a perturbed circuit v b, i b ^ ib i v ) i bi v b v b, i b i b i bi vb i (v i (vb i Motivation ^ Vs ^ others Dynamic Tuning for High–Performance Custom Digital Design Of 77:23 and then into f k p k then we can pick up (in the limit) all the required sensitivities fp k I vI iI iV vV typical term if we can manipulate the above equation into Chandu Visweswariah Adjoint Sensitivity Computation i I I ^ ^ v R i R R R i R R i R Typical term (v I i I I v^ I) i I I; Consider a circuit with only resistors and current sources: for any current source: ^ for any resistor: v R i R R; Is ^ Is ^ Rs ^ . f v I. v I vI iI I vI iR iR R By choosing v^ R R i R, we get typical term i R i R R. total circuit: ^ f v I and ^ f iR iR R given a scalar performance function f (v I), f choose iI f v^ I I pick off the required sensitivities: Thus Dynamic Tuning for High–Performance Custom Digital Design any number of parameters can be accommodated at once! Chandu Visweswariah Of 77:24 I1 R1 R3 R4 ^ + v^ I1 – ^ R1 R2 Adjoint Method: An Example R2 ^ ^ choose I 2 1 ^ v R4 0, R 2 v ^ R4 i R3i R3, R 3 R3 R4 v ^ R4 i R4i R4 R 4 v v R4 R4 0 and 0 R 3 R 4 v R4 ^ v I1 I 1 v ^ R4 i R2i R2, R 2 i R1i R1R 1 i R2i R2R 2 i R3i R3R 3 i R4i R4R 4 I 1v^ I1 v I2 v R4 v ^ R4 i R1i R1, R 1 v note that R4 0, R 1 can re–use LU factors of nominal solution Dynamic Tuning for High–Performance Custom Digital Design All parameters handled at once! Chandu Visweswariah ^ I2 Of 77:25 + v2 v^ 2 i2 i1 Adjoint Sensitivity: Controlled Sources i1 – ^ ^ v 1 v 2 i 2 i 2 ^ Current–controlled current source + v1 0 – ^ ^ v 1 i 1 i 1 v 1 i 1 i 1 v^ 1 v 2 i 2 v^ 2 ( i 1 i 1) Typical term ^ ^ i1 + v^ 2 – i2 0 ^ Choose i 2 0 (current source) KEY TERM! v^ 1 – v^ 2 (voltage–controlled voltage source) v^ 1 v^ 2 + – final typical term is v^ 2 i 1 Dynamic Tuning for High–Performance Custom Digital Design control is reversed! Chandu Visweswariah Of 77:26 ^ Vs ^ Rs ^ Cs + dv dv ^ C C v C v^ dt C dt C KEY TERM! iC vC vI iI iV vV iR iR R ?? Adjoint Sensitivity: Extension to Time–domain Recall I ^ Typical term for Cs v C i C C – Dynamic Tuning for High–Performance Custom Digital Design Of 77:27 these have go although a v C(t 0) term would be handy tf tf tf tf ^ ^. . t C Typical term dt v i dt – C v^ v f C v v dt– v^ v dt C C C C C C C C t0 t0 t0 t0 t0 tf tf ^ ^. . C (i C v ) dt v C v^ (t ) v (t ) C v^ (t ) v (t ) v^ v dt C C C C C C 0 C 0 C C f f t0 t0 Chandu Visweswariah ^. Of 77:28 Adjoint Sensitivity: Extension to Time–domain, Cont’d. ^ to get rid of the unwanted terms, i C Cv C and v^ C(t f) 0 Solution: run time backwards!! k t, usually t 0 t f t make use of the fact that Tellegen’s theorem holds for any choice of time point in the two circuits dv^ dv^ (t) ^ ^. then i C() C C C C Cv C(t) and choose dt d v^ C(t f) v^ C( t 0) as an initial condition with value 0 Dynamic Tuning for High–Performance Custom Digital Design tf . C so finally, typical term C v^ (t ) v (t ) v^ v dt C 0 C 0 C C t0 required sensitivity becomes a convolution integral; in fact, all sensitivities become convolutions Chandu Visweswariah tf t0 (i V v^ V) dt ^ k p k Adjoint Sensitivity: Function Tricks ^ (–v I i I) dt Vs the left hand side of the general relation tf Is t0 ^ must be chosen to be f by good choices of i I and v^ V V k pk t start 1 dt t end sampling of v^ I (t t 1): choose i I (t t 1) so that t end i v I| tt1 k p k power: choose v^ V 0 so that t start Dynamic Tuning for High–Performance Custom Digital Design remember to map ts to s Elmore delay is easily expressed as an integral, too Chandu Visweswariah Of 77:29 cross Adjoint Sensitivity: Crossing Delays Crossing delay sensitivity v cross v N tt v^ N| ttcross dt cross dp . v N| tt cross v^ N dt cross . – vN dp tt cross t cross Dynamic Tuning for High–Performance Custom Digital Design t v v dv dt cross cross 0 d v (t, p) tt N N cross t p dp N dp dp tt cross tt cross vN v cross Chandu Visweswariah Of 77:30 Sensitivity Computation: Wrap–up Direct method directly differentiate BCRs any number of functions, one parameter can re–use LU factors (modulo time–point mismatch) original sources removed; a new source is introduced in conjunction with the single sensitivity parameter ‘‘full” transient sensitivity, e.g., v N(t)W eff can be computed Adjoint method Dynamic Tuning for High–Performance Custom Digital Design based on the ‘‘adjoint” or transposed set of circuit equations; most intuitively approached via Tellegen’s theorem one function, any number of parameters control reversed; time run backwards can re–use LU factors (modulo time–point mismatch) sources removed; a new source is introduced and manipulated to express the single sensitivity function as a convolution sensitivity results are convolutions, hence an overhead ‘‘full” transient sensitivity harder to compute Chandu Visweswariah Of 77:31 Mini–outline 1. Introduction and motivation 2. Circuit simulation 3. Time–domain gradient computation Dynamic Tuning for High–Performance Custom Digital Design 4. Nonlinear optimization – terminology – basics of linear programming – basics of nonlinear programming – LANCELOT and MINOS – minimax optimization – key messages 5. Case study – JiffyTune: algorithms and implementation – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective 6. Conclusions, future work and pointers to the reading list Chandu Visweswariah Of 77:32 Terminology i 1, 2, , n i l 1, l 2, , l m i 1, 2,..., l min f (x) s.t. c i(x) 0 c i(x) 0 li xi u i objective function (maximize/minimize) equality constraints inequality constraints ( and ) c i(x) 0 c i(x) s i 0 s.t. s i 0 c i(x) s i 0 s.t. s i 0 – often handled by introducing a slack variable s i c i(x) 0 – note that s i is a new variable of the problem simple bounds (either l i or u i can be unbounded) Dynamic Tuning for High–Performance Custom Digital Design constrained vs. unconstrained optimization Chandu Visweswariah Of 77:33 Terminology, Cont’d. i 1, 2, , n i l 1, l 2,..., l m min f (x) s.t. c i(x) 0 i 1, 2,..., l c i(x) 0 li xi u i solution vectors x 1, x 2, , x k, , x * feasibility (feasible points, feasible regions) activities are constraints that are ‘‘tight” if f (x) or any of c i(x) is a nonlinear function of x, we have a nonlinear problem linear programming: 1M+ variables is large but tractable nonlinear programming: 1K+ variables is large but tractable Key message: use nonlinear programming to solve nonlinear problems (all circuit tuning problems are nonlinear)! Dynamic Tuning for High–Performance Custom Digital Design Consider good solutions to bad models vs. less good solutions to better (possibly nonlinear) models! Chandu Visweswariah Of 77:34 Classical Theory Unconstrained optima to minimize f (x), f 2 f – Jacobian = x f 0 is a necessary condition x i* 2f 2 f – Hessian = xx 0 is a sufficient condition x i* x j* all eigenvalues of the Hessian must be non–negative think of the second condition as ensuring ‘‘positive curvature” the second condition avoids saddle points and maxima Constrained optima: Lagrangian formulation i1 ici(x) l the minimizer of f (x) subject to equality constrains 0, i 1, 2,..., l is a stationary point of the Lagrangian c i(x) (x, ) f (x) c i(x l ixci(x*) 0 i1 Dynamic Tuning for High–Performance Custom Digital Design – dual feasibility: x f (x *) applying the above criteria, we get *) 0 i – primal feasibility: Chandu Visweswariah Of 77:35 Kuhn–Tucker Conditions for Equality Constraints min f (x) s.t. c(x) 0, f, c 2 consider the set of all feasible directions, i.e., d such that c(x d) – c(x) d Tc 0 optimality implies that there does not exist even a single feasible descent direction, i.e., d Tf 0 we know that if d Tc 0 then d is in the null space of c d Z t for any t is therefore the set of all feasible directions, where Z is a basis for the null space of c (or the columns of Z are a basis for that null space or the columns of Z span the null space) hence t TZ Tf 0 t or Z Tf 0 is the first–order condition Dynamic Tuning for High–Performance Custom Digital Design Of 77:36 just as f (x d) f (x) d f(x) 12 d 2 f(x) is a scalar quadratic model, f (x d) f (x) d Tf 12 d T 2f d is a quadratic model for f (x) using a quadratic model for f (x) and c(x) and restricting ourselves to feasible d, we derive the second–order condition Z T 2f Z 0 Chandu Visweswariah Of 77:37 Kuhn–Tucker Conditions for Inequality Constraints min f (x) s.t. c(x) 0 optimality now implies that there is no further descent direction d for which c(x d) – c(x) d T c 0 d Tf 0 f is a (negative) linear combination of the gradient of the (active) constraints the Lagrange multipliers corresponding to inactive constraints are zero first–order condition: Z Tf 0 where Z is a basis for the null space of the Jacobian of the active constraints (which have positive Lagrange multipliers) Dynamic Tuning for High–Performance Custom Digital Design Z T 2f Z 0 second order condition: Chandu Visweswariah 2 3 Whirlwind Tour of Linear Programming Active set methods (simplex) 4 min f (x) s.t. c i(x) 0 descent direction 1 Dynamic Tuning for High–Performance Custom Digital Design there is always a solution at a point where at least n constraints intersect in n–space (2 in the figure) strategy: move from one vertex to an adjacent vertex while seeking a decrease in the objective function theoretical worst–case complexity is exponential, but works well in practice Chandu Visweswariah Of 77:38 Whirlwind Tour of Linear Programming, Cont’d. Penalty function methods: interior point methods log(xi) for the simple bounds start feasible always stay feasible use ‘‘barrier functions” in merit function to stay within simple bounds 1 example: (x) f (x) i x i 0 ( is a penalty parameter) polynomial complexity less likely to suffer from degeneracy problems Penalty function methods: exterior point methods feasible is guaranteed only at the solution Aside for nonlinear programming log ci(x) for ci(x) 0 Of 77:39 can use ‘‘barrier” function for inequalities in interior method merit 1 functions such as (x) f (x) i Dynamic Tuning for High–Performance Custom Digital Design i can use penalty term for equalities in exterior method merit 1 function such as (x) f (x) c i2(x) Chandu Visweswariah Nonlinear Programming Derivative (D) vs. Derivative Free (DF) Methods never use DF if D is possible – DF popular since easy to understand – DF popular since easy to implement most implementations of DF: – useful only if # variables < 20 – not robust – not efficient (especially for circuit applications) – no convergence theory – however, sometimes the only usable method recent developments – DF algorithms with convergence theory and better robustness have been developed... – ... but they are applicable only to small problems – ... and are still inefficient (but parallelizable) Dynamic Tuning for High–Performance Custom Digital Design Key message: never use DF unless you have no choice! Chandu Visweswariah Of 77:40 Nonlinear Programming Some general comments Key message: tremendous progress in nonlinear optimization in the last 15 years! global optimality is almost impossible to achieve or detect on large–scale problems the best we can hope for is – problem is convex (in which case we can achieve and detect a global optimum) – we converge to a local minimum – improvement is obtained! exploit structure where possible – example: sparsity or group partial separability line–search vs. trust–region approaches Dynamic Tuning for High–Performance Custom Digital Design Of 77:41 Key message: requires sophisticated user or optimization specialist to best exploit nonlinear optimization... using the software as a black box is not ideal! Chandu Visweswariah Unconstrained Nonlinear Optimization Steepest descent (SD) ‘‘low storage” solution, simple and efficient per iteration unfortunately, slow linear– or even non–convergence used early in the optimization to capture global behavior Safeguarded Newton’s method and variations (NM) (safeguarded) step in direction that minimizes quadratic model second–order convergence more expensive used late in the optimization for fast asymptotic convergence Alternatives modified Newton’s method to guarantee positive definiteness of Hessian of quadratic model and hence descent Of 77:42 quasi–Newton (low rank updates to the Hessian) (converts SD to NM) coordinate descent (BAD) and its generalization, conjugate directions (GOOD) Dynamic Tuning for High–Performance Custom Digital Design Levenberg–Marquardt Chandu Visweswariah Unconstrained Nonlinear Optimization Conjugate gradients Steepest descent Newton’s method Dynamic Tuning for High–Performance Custom Digital Design Of 77:43 Method of choice for large problems: conjugate gradient (CG) iterations with appropriate choice of pre–conditioner Chandu Visweswariah MINOS Stanford, ca. 1980 min F(x) c Tx d Ty Dynamic Tuning for High–Performance Custom Digital Design augmentation objective function Lagrangian of nonlinear part of constraints ~ s.t. f(x) A 1y b 1 linearized constraints A 2x A 3y b 2 linear constraints lx x ux simple bounds ly y uy where ~ where f(x) f (x) J k(x–x k) (linearization) nonlinear linear s.t. f (x) A 1y b 1 nonlinear constraints A 2x A 3y b 2 linear constraints lx x ux simple bounds ly y uy is remapped to ~ ~ ~ min F(x) c Tx d Ty kT[f (x) – f(x)] 1 [f (x) – f(x)] T[f (x) – f(x)] 2 Chandu Visweswariah Of 77:44 MINOS, Cont’d. Dynamic Tuning for High–Performance Custom Digital Design large–scale, general–purpose, nonlinear optimization package intuition: – separate linear and nonlinear parts – use active set methods for the linear part (LP–like) – use augmented Lagrangian for the nonlinear part – minimize quadratic model of the merit function subject to linear model of constraints (QP) – line–search methods for minimizing the quadratic model in practice, very effective, especially if – most constraints are linear or near linear – real number of degrees of freedom at the solution is not large Chandu Visweswariah Of 77:45 LANCELOT large–scale, general–purpose, nonlinear optimization package efficient, especially for nonlinear constraints exploits structure via group partial separability Major Iteration update l or m value(s) formulate augmented Lagrangian and iteratively: Minor Iteration trust–region approach simple bounds handled explicitly and well minimize merit function Dynamic Tuning for High–Performance Custom Digital Design Of 77:46 test for convergence many options: – l l 2 trust regions (box and sphere) – various preconditioners and initializations available – approximate/accurate bounded quadratic problem (BQP) solver has successfully handled 20,000 variable problems with 20,000 nonlinear constraints; has been tested on 15,000 test cases representing 1,000 unique problems Chandu Visweswariah i Lagrangian i min f (x 1, x 2) 0 x1 a 0 x2 b x2 Of 77:47 Quadratic model penalty function to weight feasibility i ci(x) 21 ci(x)2 How LANCELOT Works (x, , ) f (x) composite function objective for unconstrained function –f minimization x1 v w b Dynamic Tuning for High–Performance Custom Digital Design xk u Trust region Simple bounds a Chandu Visweswariah Minimax Optimization x i x* x z the original problem is min [ max { f i(x) } ], i 1, 2, , m x, z f 2(x) xk not directly differentiable remap to min (z) s.t. z f i(x) i f 1(x) Special considerations i* 1, so initialize i 1m i initialize z to max f i(x) directly after the first function evaluation optimality condition: i Dynamic Tuning for High–Performance Custom Digital Design can handle minimax problems in other ways Chandu Visweswariah Of 77:48 Andy and Chandu’s Top–10 Key Messages! Time to wake up! Dynamic Tuning for High–Performance Custom Digital Design Of 77:49 1. Replace good solutions to bad models by potentially less good solutions to better models! 2. Use nonlinear optimization on nonlinear problems! 3. Swapping objective function and constraints does not a new ICCAD paper make! 4. Tremendous progress has been made in nonlinear optimization in the last 15 years; do not use outdated methods! 5. Never use derivative–free methods unless you have no choice! 6. In circuit tuning, CPU time is dominated by simulation and gradient computation; must leverage optimizer to reduce number of iterations! 7. Efficient sensitivity computation is essential to any high–performance circuit tuner! 8. Carefully specify all aspects of the problem you really want to solve (forces careful understanding of the circuit and problem being posed)! 9. ‘‘Black box” optimization under–utilizes capabilities of a package (and often leads to greatly sub–optimal solutions)! 10.Any simulation–based optimization is inherently noisy! Chandu Visweswariah Mini–outline 1. Introduction and motivation 2. Circuit simulation 3. Time–domain gradient computation Case study 4. Nonlinear optimization 5. – JiffyTune: algorithms and implementation simulation gradient computation nonlinear optimization – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective Dynamic Tuning for High–Performance Custom Digital Design 6. Conclusions, future work and pointers to the reading list Chandu Visweswariah Of 77:50 Case Study: JiffyTune dynamic circuit optimization tool called JiffyTune has been developed at IBM over the last 16 months – circuit simulated by SPECS (piecewise approximate, event–driven, fast circuit simulation program) – takes advantage of both direct and adjoint transient sensitivity computation – uses LANCELOT (augmented Lagrangian, trust–region–based, large–scale, general–purpose nonlinear optimization package) has successfully tuned circuits with up to 500 tunable transistors has been used by about 50 designers in about 2,700 tuning runs in many different technologies and sites of IBM human interface and methodology issues carefully taken into account during development Dynamic Tuning for High–Performance Custom Digital Design was extensively used on domino circuits of a custom, high–performance, PowerPC microprocessor Chandu Visweswariah Of 77:51 JiffyTune: Features at a Glance Dynamic Tuning for High–Performance Custom Digital Design accommodates delay, slew, area and power functions supports minimax optimization any combination of weighted constraints and objective function(s) permitted all three types of constraints (equality, less–than and greater–than) can be specified ratio–ing of transistors allowed similar instances can be grouped for regular layout automatic failure–recovery allows optimizer to take aggressive steps two manufacturability modes implemented – post–tuning information mode at various process corners – simultaneous tuning at multiple process corners easy–to–use human interface for problem specification as well as back–annotation of results specialized stopping criteria and considerations for noise Chandu Visweswariah Of 77:52 Circuit, models, optimization criteria Chandu Visweswariah User interface Problem specification LANCELOT JiffyTune administration chain ruling ad nauseam X new X old Of 77:53 User interface Back annotation JiffyTune: Software Overview g, J f, f SPECS JiffyTune ‘‘Engine” Dynamic Tuning for High–Performance Custom Digital Design Optimized circuit iL vL iL vL Of 77:54 SPECS: Piecewise Approximate Circuit Simulation Modeling piecewise constant i–v characteristics ( 1% error) linearized junction and diffusion capacitances ( 1% error) gate capacitances linearized and grounded ( 5% error) Dynamic Tuning for High–Performance Custom Digital Design tree/link formulation of circuit equations event–driven simulation to exploit latency and multi–rate behavior incremental processing of KCL and KVL equations whenever a device moves from one segment of its i–v table to the next relative timing error inversely proportional to square of signal slope Analysis Chandu Visweswariah Upside SPECS Summary speed: 70x (6,000 events per second on a workstation) capacity: 10x (0.25M transistors) accuracy: greater than 1s of delays with 5% relative timing accuracy; worst case is 10% used in 12 IBM sites for – timing verification – functional verification – tuning – power estimation of digital and memory circuits Downside Of 77:55 constant–grounded–capacitance–assumption causes inaccuracy stiff circuits a problem Dynamic Tuning for High–Performance Custom Digital Design no inductors Chandu Visweswariah i Sensitivity Analysis in SPECS ^ G v i i (v, p) ^ ^ ^ di i dv i or i Gv^ I x v dp p dp sensitivity or adjoint circuit consists of mostly disconnected, grounded capacitors little ‘‘spurts” of charge sharing occur instantaneously at the times of the events of the original nominal circuit event information from nominal simulation is saved results of sensitivity or adjoint circuit yield required sensitivities; convolution is required in the case of adjoint sensitivity both direct and adjoint methods implemented Dynamic Tuning for High–Performance Custom Digital Design sensitivity or adjoint circuit repeatedly solved with appropriate excitation Chandu Visweswariah v^ Of 77:56 Sensitivity Analysis in SPECS, Cont’d. Functions any crossing time (delay and slew are expressed as the difference of two crossing times) power in any voltage source over any sub–interval of time transient node voltage (direct method only) Parameters transistor widths (chain ruling done automatically) resistor and capacitance values Implementation notes Dynamic Tuning for High–Performance Custom Digital Design convolution in the adjoint method is carried out in an event–driven fashion automatic heuristic to choose between direct and adjoint method (presently checks if # parameters > 3 * # functions) can force direct or adjoint method Chandu Visweswariah Of 77:57 Efficiency of Sensitivity Analysis in SPECS 144 MOS transistors, 27 ns of simulation 36 functions, 104 parameters (more internally) nominal simulation: 2 s on Risc/System 6000 mod 590 sensitivity run time: 10.9 s overhead per adjoint sensitivity circuit simulation = 15% overhead per gradient computation = 0.14% Example 1: PowerPC Branch Scan and Select Circuit Dynamic Tuning for High–Performance Custom Digital Design 6,166 MOS transistors, 770 resistors, 66 ns of simulation 99 functions, 6,166 parameters (more internally) nominal simulation: 3 mins 5 s sensitivity run time: 20 mins 5 s overhead per adjoint sensitivity circuit simulation = 6.5% overhead per gradient computation = 0.001% !!!! Logic panel module IOmux Chandu Visweswariah Of 77:58 v N R –0.98795 –1.98795 0 Chandu Visweswariah 4 6 + – R 8 SPECS Analytic 10 Of 77:59 Time(ns) C vN Sensitivity Results on Simple Circuit 2 Dynamic Tuning for High–Performance Custom Digital Design delay 6.20 6.00 5.80 5.60 5.40 5.20 5.00 4.80 4.60 4.40 4.20 4.00 3.80 5.00 15.00 Delay Sensitivity SENS DATA Results 10.00 Dynamic Tuning for High–Performance Custom Digital Design delay sensitivity plotted as tangents to delay–width curve Chandu Visweswariah 20.00 width Of 77:60 LANCELOT Optimization: Special Issues Formulation minimax optimization (and initialization of Lagrange multipliers) implemented as described earlier CUTE testing environment has allowed us to integrate MINOS from Stanford as an alternative optimizer Problems due to noise any simulation–based optimization is inherently noisy unable to recover from poor initializations; optimizer often wastes time going nowhere does not stop gracefully or predictably Special considerations for noisy optimization tolerance for feasibility and line search break points Of 77:61 consideration of small step beneath which further progress unlikely initial trust region radius initial Hessian approximation for secant methods Dynamic Tuning for High–Performance Custom Digital Design stopping criteria Chandu Visweswariah Manufacturability Modes in JiffyTune general goal: make parametric manufacturability a push–button, transparent, easy–to–use part of tuning ‘‘Information” mode perform nominal tuning as a postprocess, simulate the tuned circuit at each process corner summarize the distribution of circuit performance across process corners Simultaneous tuning at multiple process corners simultaneously tune at all process corners; no surprises after tuning is completed replicate and modify tuning criteria for all process corners i – constraint: convert d(x) t to d i(x) t i x x x i, j i – objective function: convert min d(x) to min[max d i(x)] i x j – minimax: convert min[max d j(x)] j to min[max d ij(x)] i, j Dynamic Tuning for High–Performance Custom Digital Design run time overhead is roughly n where n number of corners Chandu Visweswariah Of 77:62 u Chandu Visweswariah Two–step Updates min f (x) s.t. c(x) u 0, u0 [c(x) u] 2 2 f (x) [c(x) u] x k1, u k1 minimize along this line Trust region x k, u k Dynamic Tuning for High–Performance Custom Digital Design x Of 77:63 Intuition Two–step Updates, Cont’d. if a variable appears in the merit function in a known functional form, a second update can be applied to it without incurring the cost of a new function/gradient evaluation under mild assumptions, the second step can be outside the trust–region; convergence is still guaranteed two–step updates lead to faster convergence, better optimization efficiency Minimax problems i i[z f i(x) u i] 1 2 i [z fi(x) ui]2 can be applied to the z variable in minimax problems; min [ max f i(x) ] leads to x z i Dynamic Tuning for High–Performance Custom Digital Design is a quadratic in z and is therefore amenable to two–step updates Chandu Visweswariah Of 77:64 JiffyTune: The Human Interface good tools are useless without a good human interface JiffyTune engine is file–driven and hence is not amenable to quick and productive design Features of Cadence interface Dynamic Tuning for High–Performance Custom Digital Design developed by actual circuit designer all functionality provided from schematic diagram – familiar environment ⇒ no steep learning curve – visual and interactive – complexities of tool hidden (but accessible) enforces clear expression of otherwise tacit circuit requirements – JiffyTune is greedy! adds significant additional functionality like grouping & ratio–ing overcomes the drudgery of a file–driven interface configurable to different site/project environments Chandu Visweswariah Of 77:65 JiffyTune Interface: Main Form 480ps Dynamic Tuning for High–Performance Custom Digital Design rise time <= 400ps 1400ps CLKG CLKM Chandu Visweswariah Of 77:66 JiffyTune Interface: Parameters Form Dynamic Tuning for High–Performance Custom Digital Design tunable/untunable transistors upper/lower bounds grouping (tracking) of instances individual settings support for hierarchy Parameters Chandu Visweswariah Of 77:67 JiffyTune Interface: Measurements Form rise time <= 400ps 1400ps CLKG CLKM 480ps delay rise/fall time area minimax function Dynamic Tuning for High–Performance Custom Digital Design Measurements (optimization targets) Chandu Visweswariah Of 77:68 JiffyTune Interface: Back Annotation Back annotation of results Dynamic Tuning for High–Performance Custom Digital Design same constraints, 2.5x load (0.6 pF → 1.5 pF) new (suggested) transistor widths and waveform data back–annotated on schematic Chandu Visweswariah Of 77:69 JiffyTune: Methodology Impact JiffyTune was used to tune120 circuits of a custom dynamic–logic microprocessor and was found to be a key productivity tool measurements, functions, weights, tunability, simple bounds, etc., are stored as attributes of schematic they are indeed part of the intellectual exercise of designing a good circuit thus design re–use is encouraged – when device models change – for different loading and arrival time situations – when design specifications change – during design remap forces careful and explicit specification of circuit requirements: the issue becomes how to correctly specify the optimization problem rather than solving the optimization problem itself! can create a power–delay or area–delay tradeoff curve by rerunning optimizer Dynamic Tuning for High–Performance Custom Digital Design Emphasis shifts to: (a) starting with a good topology and a working circuit, (b) posing the problem well Chandu Visweswariah Of 77:70 Historical Perspective: DELIGHT.SPICE W. Nye, D. C. Riley, A. S. Vincentelli, A. L. Tits, 1988 accommodates semi–infinite constraints hard and soft constraints; the latter have ‘‘good” and ‘‘bad” values from which the quality of the solution is judged minimax PHASE–I–II–III optimization by method of feasible directions (always produces feasible design, monotonically decreases merit function while handling semi–infinite constraints) implements sensitivity in SPICE Weaknesses Dynamic Tuning for High–Performance Custom Digital Design sloooooooooooow, tailored to small analog circuits hard to use Chandu Visweswariah Of 77:71 Historical Perspective: TAILOR D. Marple, 1989 operates on the layout constraint graph of a cell no separate post–layout closure needed uses constraint graph with corner–stitching data structure; variable weight for each transistor arc constructs a delay graph based on a single time–constant approximation (static) then works to minimize cell’s pitch in one dimension uses augmented Lagrangian with penalty term alternates steepest descent and steepest ascent to find saddle point of Lagrangian Weaknesses Dynamic Tuning for High–Performance Custom Digital Design used on small cells only (50 transistors) no hierarchy crude delay model Chandu Visweswariah Of 77:72 Historical Perspective: Interconnect Sizing J. Cong, K.–S. Leung, 1994 N. Menezes, S. Pullela, L. T. Pileggi, 1995 concurrent gate and interconnect sizing; flurry of interest in this topic since Elmore delay approximation for gates moment matching models for wires formulated into a convex optimization problem delay models differentiated analytically to provide gradients sequential quadratic programming (SQP) applied – quadratic fit about last solution point – minimize quadratic to get new solution vector routability enhanced by simple congestion weight factors Weaknesses Dynamic Tuning for High–Performance Custom Digital Design inaccurate gate delay model Chandu Visweswariah Of 77:73 Mini–outline 1. Introduction and motivation 2. Circuit simulation 3. Time–domain gradient computation 4. Nonlinear optimization Dynamic Tuning for High–Performance Custom Digital Design Conclusions, future work and pointers to the reading list – JiffyTune: algorithms and implementation – human interface – application to PowerPC microprocessor design – methodology impact and implications – historical perspective 5. Case study 6. Chandu Visweswariah Of 77:74 Chandu Visweswariah Conclusions dynamic tuning is possible and meaningful 1,000 tunable transistors well within reach; perhaps 10,000 tunable transistors is not far out of reach reasonable compromises on simulation accuracy (piecewise approximate circuit simulation) are both necessary and practical gradients necessary to carry out tuning adjoint method can be used to compute large number of gradients efficiently sophisticated nonlinear optimization algorithms essential extensions to manufacturability based on a design–of–experiments paradigm straightforward having a tuning capability not only improves design time and circuit quality, it has methodology impact too Dynamic Tuning for High–Performance Custom Digital Design Of 77:75 Future Work Dynamic Tuning for High–Performance Custom Digital Design accommodation of semi–infinite constraints, e.g., delay should be less than a target for a range of power supply voltages parallel processing for sensitivity computation Hessian computation automatic generation of problems from a static tuner; automatic generation of stimulus patterns and problem constraints exploitation of structure, e.g., group partial separability formulation as a mixed integer–continuous problem for discrete transforms formulation improvements to speedup large optimization runs Chandu Visweswariah Of 77:76 Reading List Dynamic Tuning for High–Performance Custom Digital Design classified into – circuit optimization in general – SPICE–like simulation – piecewise approximate simulation – gradient computation – nonlinear optimization bibliography has been annotated NEOS home page (take the state–of–the–art optimization software for a test run): http://www.mcs.anl.gov/home/otc/Server/neos.html HAPPY READING! Chandu Visweswariah Of 77:77

- Similar pages
- "Sparse Semidefinite Programming Relaxations for Large Scale Polynomial optimization and their applications to differential equations"
- Digital-to-Analog Converter ICs Solutions Bulletin, Volume 10, Issue 1
- Model-Based Design Streamlines Embedded Motor Control System Development PDF
- Motor Control Systems and Design Brochure PDF
- ETC AB-046
- V01N2 - OCTOBER
- V19N1 - MARCH
- V08N1 - FEBRUARY
- JiffyTune: circuit optimization using time-domain sensitivities.
- Efficient time-domain simulation and optimization of digital FET circuits.
- here
- AN-263 Sine Wave Generation Techniques
- Instrumentation Applications for a Monolithic Oscillator
- Algorithms for formal circuit optimization on a static timing basis.
- Optimization challenges in transistor sizing.