simple_NAND2_gate

% Two-input NAND gate sizing (a simple, hard-coded example).
% (a figure is generated if the tradeoff flag is turned on)
%
% This is an example taken directly from the paper:
%
%   Digital circuit optimization via geometrical programming
%   by Boyd, Kim, Patil, and Horowitz
%   Operations Research 53(6): 899-932, 2005.
%
% Solves the problem of choosing device widths w_i for the given
% NAND2 gate in order to achive minimum Elmore delay for different
% gate transitions, subject to limits on the device widths,
% gate area, power, and so on. The problem is a GP:
%
%   minimize   D = max( D_1, ..., D_k )  for k transitions
%       s.t.   w_min <= w <= w_max
%              A <= Amax, etc.
%
% where variables are widths w.
%
% This code is specific to the NAND2 gate shown in figure 19
% (page 926) of the paper. All the constraints and the objective
% are hard-coded for this particular circuit.
%
% Almir Mutapcic 02/01/2006
clear all; close all;
PLOT_TRADEOFF = 1; % to disable set PLOT_TRADEOFF = 0;

%********************************************************************
% problem data and hard-coded GP specification (evaluate all transitions)
%********************************************************************
N = 4;       % number of devices
Cload = 12;  % load capacitance
Vdd = 1.5;   % voltage

% device specs
NMOS = struct('R',0.4831, 'Cdb',0.6, 'Csb',0.6, 'Cgb',1, 'Cgs',1);
PMOS = struct('R',2*0.4831, 'Cdb',0.6, 'Csb',0.6, 'Cgb',1, 'Cgs',1);

% device width variables
gpvar w(N)

% gate specs
gates(1:2) = PMOS; gates(3:4) = NMOS;

for num = 1:N
  gates(num).R   = gates(num).R/w(num);
  gates(num).Cdb = gates(num).Cdb*w(num);
  gates(num).Csb = gates(num).Csb*w(num);
  gates(num).Cgb = gates(num).Cgb*w(num);
  gates(num).Cgs = gates(num).Cgs*w(num);
end

% capacitances
C1 = sum([gates(1:3).Cdb]) + Cload;
C2 = gates(3).Csb + gates(4).Cdb;

% input capacitances
Cin_A = sum([ gates([2 3]).Cgb ]) + sum([ gates([2 3]).Cgs ]);
Cin_B = sum([ gates([1 4]).Cgb ]) + sum([ gates([1 4]).Cgs ]);

% resistances
R = [gates.R]';

% delays and dissipated energies for all six possible transitions
% transition 1 is A: 1->1, B: 1->0, Z: 0->1
D1 = R(1)*(C1 + C2);
E1 = (C1 + C2)*Vdd^2/2;
% transition 2 is A: 1->0, B: 1->1, Z: 0->1
D2 = R(2)*C1;
E2 = C1*Vdd^2/2;
% transition 3 is A: 1->0, B: 1->0, Z: 0->1
% D3 = C1*R(1)*R(2)/(R(1) + R(2)); % not a posynomial
E3 = C1*Vdd^2/2;
% transition 4 is A: 1->1, B: 0->1, Z: 1->0
D4 = C1*R(3) + R(4)*(C1 + C2);
E4 = (C1 + C2)*Vdd^2/2;
% transition 5 is A: 0->1, B: 1->1, Z: 1->0
D5 = C1*(R(3) + R(4));
E5 = (C1 + C2)*Vdd^2/2;
% transition 6 is A: 0->1, B: 0->1, Z: 1->0
D6 = C1*R(3) + R(4)*(C1 + C2);
E6 = (C1 + C2)*Vdd^2/2;

% maximum area and power specification
Amax = [5:45];
Amax = 24;
wmin = 1;
area = sum(w);

% objective is the worst-case delay
gate_delay = max(D1,D2,D4);

% collect all the constraints
constr = [area <= Amax; wmin*ones(N,1) <= w];

% formulate the GP problem and solve it
[obj_value, solution, status] = gpsolve(gate_delay, constr);
assign(solution);

fprintf(1,'\nOptimal gate delay for Amax = %d is %3.4f.\n', ...
        Amax, obj_value)
disp('Optimal device widths are: '), w

%********************************************************************
% tradeoff curve code
%********************************************************************
if( PLOT_TRADEOFF )

% varying parameters for an optimal trade-off curve
Npoints = 25;
Amax = linspace(5,45,Npoints);
Dopt = []; Duniform = [];

% set the quiet flag (no solver reporting)
global QUIET; QUIET = 1;

for k = 1:Npoints
  % add constraints that have varying parameters
  constr(1) = area <= Amax(k);

  % solve the GP problem and compute the optimal volume
  [obj_value, solution, status] = gpsolve(gate_delay, constr);
  Dopt = [Dopt obj_value];
  Duniform = [Duniform eval(gate_delay, {'w' Amax(k)/N*ones(N,1)}) ];
end

% enable solver reporting again
global QUIET; QUIET = 0;

% plot the tradeoff curve
plot(Dopt,Amax,Duniform,Amax,'--');
xlabel('Dmin'); ylabel('Amax');
legend('optimal','uniform')

end
% end tradeoff curve code

 
Iteration     primal obj.         gap        dual residual     previous step.
 
   1         3.67367e+00       1.80000e+01       2.15e+01               Inf
   2         1.53724e+00       7.89798e+00       9.59e-02       9.79990e-01
   3         9.81709e-01       6.75510e+00       5.21e-02       2.65444e-01
   4         6.64858e-01       5.63684e+00       2.11e-02       3.63481e-01
   5         4.77514e-01       4.76207e+00       6.45e-03       4.46146e-01
   6         3.50469e-01       4.17319e+00       1.48e-03       5.20527e-01
   7        -8.13243e-02       2.63911e+00       1.52e-04       6.75844e-01
 
Iteration     primal obj.         gap        dual residual     previous step.
 
   1         7.30425e+01       1.80000e+01       9.35e-01               Inf
   2         3.60296e+01       1.69238e+01       8.90e-01       2.41449e-02
   3         1.55930e+01       1.58376e+01       8.20e-01       4.00964e-02
   4         8.08709e+00       1.50148e+01       7.24e-01       6.05182e-02
   5         4.06500e+00       1.38377e+01       5.54e-01       1.25000e-01
   6         2.21655e+00       1.07336e+01       1.39e-01       5.00000e-01
   7         3.57132e+00       9.49919e+00       6.96e-06       1.00000e+00
   8         2.32432e+00       4.75134e+00       8.60e-05       1.00000e+00
   9         1.90393e+00       2.37662e+00       2.01e-05       1.00000e+00
  10         1.68147e+00       1.19001e+00       1.58e-05       1.00000e+00
  11         1.55673e+00       5.95836e-01       2.90e-06       1.00000e+00
  12         1.49152e+00       2.98161e-01       2.04e-07       1.00000e+00
  13         1.45856e+00       1.49148e-01       1.22e-08       1.00000e+00
  14         1.44201e+00       7.45919e-02       7.56e-10       1.00000e+00
  15         1.43373e+00       3.73005e-02       4.74e-11       1.00000e+00
  16         1.42959e+00       1.86514e-02       2.96e-12       1.00000e+00
  17         1.42752e+00       9.32599e-03       1.85e-13       1.00000e+00
  18         1.42648e+00       4.66307e-03       1.16e-14       1.00000e+00
  19         1.42596e+00       2.33155e-03       7.24e-16       1.00000e+00
  20         1.42570e+00       1.16578e-03       4.52e-17       1.00000e+00
  21         1.42557e+00       5.82892e-04       2.83e-18       1.00000e+00
  22         1.42551e+00       2.91446e-04       1.77e-19       1.00000e+00
  23         1.42548e+00       1.45723e-04       1.10e-20       1.00000e+00
  24         1.42546e+00       7.28616e-05       6.90e-22       1.00000e+00
  25         1.42545e+00       3.64308e-05       4.31e-23       1.00000e+00
  26         1.42545e+00       1.82154e-05       2.70e-24       1.00000e+00
  27         1.42545e+00       9.10770e-06       1.68e-25       1.00000e+00
  28         1.42544e+00       4.55385e-06       1.05e-26       1.00000e+00
  29         1.42544e+00       2.27692e-06       6.58e-28       1.00000e+00
  30         1.42544e+00       1.13846e-06       4.12e-29       1.00000e+00
  31         1.42544e+00       5.69231e-07       2.60e-30       1.00000e+00
  32         1.42544e+00       2.84616e-07       3.12e-31       1.00000e+00
  33         1.42544e+00       1.42308e-07       4.73e-32       1.00000e+00
  34         1.42544e+00       7.11539e-08       3.49e-32       1.00000e+00
  35         1.42544e+00       3.55769e-08       3.77e-32       1.00000e+00
  36         1.42544e+00       1.77885e-08       5.29e-32       1.00000e+00
  37         1.42544e+00       8.89424e-09       9.28e-32       1.00000e+00
Solved
Problem succesfully solved.

Optimal gate delay for Amax = 24 is 4.1597.
Optimal device widths are: 

w =

    6.7960
    5.1106
    4.7637
    7.3297

Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.
Problem succesfully solved.