```% Elmore delay sizing for an interconnect network.
% (a figure is generated)
%
% This is an example taken directly from papers:
%
%   A Tutorial on Geometric Programming (see pages 31-34)
%   by Boyd, Kim, Vandenberghe, and Hassibi.
%
%   Digital circuit optimization via geometrical programming
%   by Boyd, Kim, Patil, and Horowitz
%   Operations Research 53(6): 899-932, 2005.
%
% We consider the problem of finding optimal wire widths w_i
% of N wire segments in an interconnect network, which will
% minimize the critical Elmore delay, subject to limits on
% wire widths and the total circuit area. We use a pi-model
% for each wire segment. Problem can be formulated as GP:
%
%   minimize   D
%       s.t.   w_min <= w <= w_max
%              area  <= Amax
%
% where variables are widths w (and arrival times T that are used
% to formulate the overall delay D expression).
%
% Important: We label root node as 1, and all the other nodes as
%            node_label_in_the_paper + 1 (due to Matlab's convention).
%            Also label nodes with increasing numbers downstream.
%
% Almir Mutapcic 02/01/2006
clear all; close all;

%********************************************************************
% user supplied data (problem constants and tree topology)
%********************************************************************
N = 6; % number of nodes (including the root node which is labeled as 1)

% parent node array
% specifies which node is a unique parent for node i (always have a tree)
parent(1) = 0; % root node does not have a valid parent
parent(2) = 1;
parent(3) = 2;
parent(4) = 3;
parent(5) = 2;
parent(6) = 5;

% problem constants
Rsource = 0.1;
l = 1*ones(N-1,1);
alpha = 1*ones(N-1,1);
beta  = 1*ones(N-1,1);
gamma = 1*ones(N-1,1);

% load capacitance at each node
C1 = 10; C2 = 10; C3 = 10; C4 = 10; C5 = 10;
Cload = [0 C1 C2 C3 C4 C5];

% minimum and maximum width and area specification
Wmin = 1;
Wmax = 10;
Amax = 15;

%********************************************************************
% derived data (computed from user's data)
%********************************************************************
% compute children cell array (evaluate who are children for each node)
children = cell(N,1);
leafs = [];
for node = [1:N]
children{node} = find(parent == node);
if isempty(children{node})
leafs(end+1) = node; % leafs have no children
end
end

%********************************************************************
% optimization
%********************************************************************
% optimization variables
gpvar w(N-1)     % wire width
gpvar T(N)       % arrival time (Elmore delay to node i)

% wire segment resistance is inversely proportional to widths
R = alpha.*l./w;
R = [Rsource; R];

% wire segment capacitance is an affine function of widths
C_bar = beta.*l.*w + gamma.*l;
C_bar = [0; C_bar];

% compute common capacitances for each node (C_tilde in GP tutorial)
C_tilde = posynomial; % create empty posynomial
for node = [1:N]
for k = parent(node)
if k > 0; C_tilde(node,1) = C_tilde(node,1) + C_bar(k); end;
end
for k = children{node}
C_tilde(node,1) = C_tilde(node,1) + C_bar(k);
end
end

% now compute total downstream capacitances
C_total = posynomial; % create empty posynomial
for node = N:-1:1
C_total(node,1) = C_tilde(node);
for k = children{node}
C_total(node,1) = C_total(node,1) + C_total(k,1);
end
end

% generate Elmore delay constraints
elm_delay_constr = [R(1)*C_total(1) <= T(1,1)];
for node = 2:N
elm_delay_constr = [elm_delay_constr; ...
R(node)*C_total(node) + T(parent(node),1) <= T(node,1)];
end

% collect all the constraints
area = sum(w.*l);
constr(1) = area <= Amax;
constr = [constr; Wmin*ones(N-1,1) <= w; w <= Wmax*ones(N-1,1)];
constr = [constr; elm_delay_constr];

% objective is the critical Elmore delay
D = max( T(leafs) );

% solve the problem
[D_value, solution, status] = gpsolve(D, constr);
assign(solution);

% save for plotting
ckt_delay_plot = D_value;
Amax_plot = Amax;

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

%********************************************************************
%********************************************************************

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

Darray = []; Duniform = [];
for Amax = [5.05 5.25 5.5 5.75 6:25]
% formulate the GP problem and solve it
constr(1) = area <= Amax;
[D_value, solution, status] = gpsolve(D, constr);
Darray = [Darray D_value];

% evaluate delay to leaf 4 (or 3 in the papers) with uniform sizing
D_to_3 = C_tilde(4)*(R(1) + R(2) + R(3) + R(4)) + ...
C_tilde(3)*(R(1) + R(2) + R(3)) + C_tilde(1)*R(1) + ...
(C_tilde(2) + C_tilde(5) + C_tilde(6))*(R(1) + R(2));
D_to_5 = C_tilde(6)*(R(1) + R(2) + R(5) + R(6)) + ...
C_tilde(5)*(R(1) + R(2) + R(5)) + C_tilde(1)*R(1) + ...
(C_tilde(2) + C_tilde(3) + C_tilde(4))*(R(1) + R(2));
D_3_5 = max(D_to_3,D_to_5);
Duniform = [Duniform eval(D_3_5, {'w' Amax/(N-1)*ones(N-1,1)}) ];
end

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

Amax = [5.05 5.25 5.5 5.75 6:25];
plot(Darray,Amax,Duniform,Amax,'--',ckt_delay_plot,Amax_plot,'bo');
xlabel('Elmore delay D'); ylabel('Amax');
legend('optimal','uniform')

end
```
```
Iteration     primal obj.         gap        dual residual     previous step.

1         5.20469e+00       4.30000e+01       2.24e+01               Inf
2         5.26444e+00       1.79498e+01       6.76e-03       9.90311e-01
3         2.13759e+00       9.81860e+00       4.80e-04       7.95102e-01
4         1.81684e-01       4.50566e+00       5.37e-06       1.00000e+00
5        -2.58233e-01       2.23499e+00       3.75e-06       1.00000e+00

Iteration     primal obj.         gap        dual residual     previous step.

1         1.92704e+02       4.30000e+01       1.00e+00               Inf
2         1.56156e+02       4.10528e+01       9.36e-01       3.36318e-02
3         6.53202e+01       3.78461e+01       8.81e-01       3.00259e-02
4         2.36201e+01       3.45175e+01       7.77e-01       6.05599e-02
5         9.13300e+00       3.12913e+01       6.01e-01       1.25000e-01
6         6.68741e+00       2.54784e+01       1.67e-01       5.00000e-01
7         8.28682e+00       2.20511e+01       1.12e-03       1.00000e+00
8         5.89151e+00       1.10608e+01       7.15e-04       1.00000e+00
9         4.89862e+00       5.56656e+00       1.17e-04       1.00000e+00
10         4.34698e+00       2.79801e+00       2.33e-05       1.00000e+00
11         4.05803e+00       1.40475e+00       2.75e-06       1.00000e+00
12         3.91054e+00       7.04238e-01       2.87e-07       1.00000e+00
13         3.83696e+00       3.52660e-01       2.48e-08       1.00000e+00
14         3.80014e+00       1.76474e-01       1.81e-09       1.00000e+00
15         3.78170e+00       8.82735e-02       1.20e-10       1.00000e+00
16         3.77247e+00       4.41459e-02       7.65e-12       1.00000e+00
17         3.76785e+00       2.20752e-02       4.83e-13       1.00000e+00
18         3.76554e+00       1.10382e-02       3.03e-14       1.00000e+00
19         3.76439e+00       5.51924e-03       1.90e-15       1.00000e+00
20         3.76381e+00       2.75966e-03       1.19e-16       1.00000e+00
21         3.76352e+00       1.37984e-03       7.42e-18       1.00000e+00
22         3.76338e+00       6.89921e-04       4.64e-19       1.00000e+00
23         3.76331e+00       3.44961e-04       2.90e-20       1.00000e+00
24         3.76327e+00       1.72481e-04       1.81e-21       1.00000e+00
25         3.76325e+00       8.62404e-05       1.13e-22       1.00000e+00
26         3.76324e+00       4.31202e-05       7.08e-24       1.00000e+00
27         3.76324e+00       2.15601e-05       4.43e-25       1.00000e+00
28         3.76324e+00       1.07800e-05       2.77e-26       1.00000e+00
29         3.76324e+00       5.39002e-06       1.74e-27       1.00000e+00
30         3.76324e+00       2.69501e-06       1.09e-28       1.00000e+00
31         3.76323e+00       1.34751e-06       5.93e-30       1.00000e+00
32         3.76323e+00       6.73753e-07       1.79e-30       1.00000e+00
33         3.76323e+00       3.36877e-07       1.99e-31       1.00000e+00
34         3.76323e+00       1.68438e-07       3.99e-31       1.00000e+00
35         3.76323e+00       8.42191e-08       3.88e-31       1.00000e+00
36         3.76323e+00       4.21096e-08       3.35e-31       1.00000e+00
37         3.76323e+00       2.10548e-08       1.93e-31       1.00000e+00
38         3.76323e+00       1.05274e-08       5.81e-32       1.00000e+00
39         3.76323e+00       5.26370e-09       2.92e-31       1.00000e+00
Solved
Problem succesfully solved.

Optimal Elmore delay for Amax = 15 is 43.0876.
Optimal wire widths are:

w =

5.8924
2.6416
1.9122
2.6416
1.9122

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.
```