Digital circuit sizing for an inverter chain (GP)
% Boyd, Kim, Patil, and Horowitz, "Digital circuit optimization % via geometric programming" % Written for CVX by Almir Mutapcic 02/08/06 % % We consider a chain of N inverters driving a load capacitance CL. % The problem is to find optimal scale factors for the inverter % that minimize the sum of them (area), while obeying constraints % on the maximum delay through the circuit, and minimum and maximum % limits on scale factors. There are no limits on the total power. % (For more details about the inverter chain see sec. 2.1.11 in the paper.) % % minimize sum(x) % s.t. T_j <= Dmax for j an output gate % T_j + d_i <= T_i for j in FI(i) % x_min <= x <= x_max % % where variables are x and T. % Here we use data structures and digital circuit models from the % referenced paper. %******************************************************************** % problem data %******************************************************************** N = 8; % number of inverters CL = 20; % capacitance load Dmax = 20; % maximum delay through the circuit x_min = 1; % minimum scale factor x_max = 20; % maximum scale factor % circuit labeling convention: % label primary input (input to the first inverter in the chain) with N+1 % label primary output (output of the last inverter in the chain) with N+2 % label inverters in the chain with 1,2,...,N based on their location % primary input and primary output labels (start with N+1) primary_inputs = [N+1]; primary_outputs = [N+2]; M = N + length( primary_inputs ) + length( primary_outputs ); % fan-in cell array for a straight chain of inverters FI{1} = [N+1]; % fan-in of the first inverter is the primary input for k = 2:N FI{k} = [k-1]; % fan-in of other inverters is the inverter feeding into them end FI{N+2} = [N]; % fan-in of the primary output is the last inverter in the chain % fan-out cell array % (will be computed from the fan-in cell array, no need to modify) FO = cell(M,1); for gate = [1:N primary_outputs] preds = FI{gate}; for k = 1:length(preds) FO{preds(k)}(end+1) = gate; end end % input and internal capacitance of gates and the driving resistance Cin_norm = ones(N,1); Cint_norm = ones(N,1); Rdrv_norm = ones(N,1); % place extra capacitance before the input of the 5th inverter Cin_norm(5) = 80; % primary output has Cin capacitance (but has no Cload) Cin_po = sparse(M,1); Cin_po(primary_outputs) = CL; % primary input has Cload capacitance (but has no Cin) Cload_pi = sparse(M,1); Cload_pi(primary_inputs) = 1; %******************************************************************** % optimization %******************************************************************** cvx_begin gp % optimization variables variable x(N) % sizes variable T(N) % arrival times % minimize the sum of scale factors subject to above constraints minimize( sum(x) ) subject to % input capacitance is an affine function of sizes Cin = Cin_norm.*x; Cint = Cint_norm.*x; % driving resistance is inversily proportional to sizes R = Rdrv_norm./x; % gate delay is the product of its driving resistance and load cap. Cload = cvx( zeros(N,1) ); for gate = 1:N if ~ismember( FO{gate}, primary_outputs ) Cload(gate) = sum( Cin(FO{gate}) ); else Cload(gate) = Cin_po( FO{gate} ); end end % delay D = 0.69*ones(N,1).*R.*( Cint + Cload ); % create timing constraints for gate = 1:N if ~ismember( FI{gate}, primary_inputs ) for j = FI{gate} % enforce T_j + D_j <= T_i over all gates j that drive i D(gate) + T(j) <= T(gate); end else % enforce D_i <= T_i for gates i connected to primary inputs D(gate) <= T(gate); end end % circuit delay is the max of arrival times for output gates output_gates = [FI{primary_outputs}]; circuit_delay = max( T(output_gates) ); % collect all the constraints circuit_delay <= Dmax; x >= x_min; x <= x_max; cvx_end % message about extra capacitance and result display disp(' ') disp(['Note: there is an extra capacitance between the 4th and 5th inverter'... ' in the chain.']) fprintf(1,'\nOptimal scale factors are: \n'), x % plot scale factors and maximum delay for inverter i close all; subplot(2,1,1); plot([1:N],T,'g--',[1:N],T,'bo'); ylabel('maximum delay T') subplot(2,1,2); stem([1:N],x); ylabel('scale factor x') xlabel('inverter stage')
Successive approximation method to be employed. SDPT3 will be called several times to refine the solution. Original size: 130 variables, 45 equality constraints For improved efficiency, SDPT3 is solving the dual problem. Approximation size: 435 variables, 235 equality constraints ----------------------------------------------------------------- Target Conic Solver Precision Error Status --------------------------- 1.221e-04 6.789e-01 Unbounded 1.221e-04 2.660e-01 Solved 1.221e-04 4.391e-04 Solved 1.221e-04 0.000e+00 Solved 1.490e-08 1.518e-08 Solved 1.490e-08 0.000e+00 Solved ----------------------------------------------------------------- Status: Solved Optimal value (cvx_optval): +32.2496 Note: there is an extra capacitance between the 4th and 5th inverter in the chain. Optimal scale factors are: x = 3.0461 2.6553 4.3323 12.4395 1.0000 1.3185 2.2359 5.2220
