# Digital circuit sizing for an inverter chain (GP)

Jump to: Source code Text output Plots Library index

    % 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_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.
       For improved efficiency, sedumi is solving the dual problem.
       sedumi will be called several times to refine the solution.
       Original size: 154 variables, 69 equality constraints
       38 exponentials add 304 variables, 190 equality constraints
    -----------------------------------------------------------------
     Cones  |             Errors              |
    Mov/Act | Centering  Exp cone   Poly cone | Status
    --------+---------------------------------+---------
     16/ 16 | 3.268e+00  5.243e-01  0.000e+00 | Unbounded
     38/ 38 | 5.508e+00  1.887e+00  8.406e-08 | Solved
     38/ 38 | 1.071e+00  8.345e-02  2.688e-07 | Solved
     34/ 37 | 3.872e-02  1.054e-04  2.143e-07 | Solved
      9/ 18 | 3.822e-03  1.030e-06  2.180e-07 | Solved
      0/  0 | 0.000e+00  0.000e+00  0.000e+00 | Solved
    -----------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): +32.2495

    Note: there is an extra capacitance between the 4th and 5th inverter in the chain.

    Optimal scale factors are:

    x =

        3.0463
        2.6555
        4.3325
       12.4397
        1.0000
        1.3184
        2.2358
        5.2215