% Optimal interconnect wire sizing
% Section 5.1, L. Vandenberghe, S. Boyd, and A. El Gamal
% "Optimizing dominant time constant in RC circuits"
% Original by Lieven Vandenberghe
% Adapted for CVX by Joelle Skaf - 11/25/05
% Modified by Michael Grant - 3/8/06
%
% we consider the problem of sizing an interconnect wire that connects
% a voltage source and conductance G to a capacitive load C. We divide the
% wire into n segments of length li, and width xi, i = 1,...,n, which is
% constrained as 0 <= xi <= Wmax. The total area of the interconnect wire
% is therefore sum(li*xi). We use a pi-model of each wire segment, with
% capacitors beta_i*xi and conductance alpha_i*xi.
% To minimize the total area subject to the width bound and a bound Tmax on
% dominant time constant, we solve the SDP
%               minimize        sum_{i=1}^20 xi*li
%                   s.t.        Tmax*G(x) - C(x) >= 0
%                               0 <= xi <= Wmax

cvxq = cvx_quiet(true);

%
% Circuit parameters
%

n=21;          % number of nodes; n-1 is number of segments in the wire
m=n-1;         % number of segments
beta = 0.5;    % segment has two capacitances beta*xi
alpha = 1;     % conductance is alpha*xi per segment
Go = 1;        % driver conductance
Co = 10;       % load capacitance
wmax = 1.0;    % upper bound on x

%
% Construct the capacitance and conductance matrices
%   C(x) = C0 + x1 * C1 + x2 * C2 + ... + xn * Cn
%   G(x) = G0 + x1 * G1 + x2 * G2 + ... + xn * Gn
% We assemble the coefficient matrices together as follows:
%   CC = [ C0(:) C1(:) C2(:) ... Cn(:) ]
%   GG = [ G0(:) G1(:) G2(:) ... Gn(:) ]
%

CC = zeros(n,n,m+1);
GG = zeros(n,n,m+1);
% constant terms
CC(n,n,1) = Co;
GG(1,1,1) = Go;
% segment values
for i = 1 : n - 1,
    CC(i,  i,  i+1) = beta;
    CC(i+1,i+1,i+1) = beta;
    GG(i,  i,  i+1) = +alpha;
    GG(i+1,i,  i+1) = -alpha;
    GG(i,  i+1,i+1) = -alpha;
    GG(i+1,i+1,i+1) = +alpha;
end
% Reshape for easy Matlab use
CC = reshape(CC,n*n,m+1);
GG = reshape(GG,n*n,m+1);

%
% Compute points the tradeoff curve, and the four sample points
%

npts    = 50;
delays  = linspace(400,2000,npts);
xdelays = [ 370, 400, 600, 1800 ];
xnpts   = length(xdelays);
areas   = zeros(1,npts);
xareas  = zeros(1,xnpts);
sizes   = zeros(m,xnpts);
for i = 1 : npts + xnpts,

    if i > npts,
        xi = i - npts;
        delay = xdelays(xi);
        disp( sprintf( 'Particular solution %d of %d (Tmax = %g)', xi, xnpts, delay ) );
    else,
        delay = delays(i);
        disp( sprintf( 'Point %d of %d on the tradeoff curve (Tmax = %g)', i, npts, delay ) );
    end

    %
    % Construct and solve the convex model
    %

    cvx_begin sdp
        variable x(m)
        variable G(n,n) symmetric
        variable C(n,n) symmetric
        minimize( sum(x) )
        G == reshape( GG * [ 1 ; x ], n, n );
        C == reshape( CC * [ 1 ; x ], n, n );
        delay * G - C >= 0;
        x >= 0;
        x <= wmax;
    cvx_end

    if i <= npts,
        areas(i) = cvx_optval;
    else,
        xareas(xi) = cvx_optval;
        sizes(:,xi) = x;

        %
        % Plot the step response
        %

        figure(xi+2);
        A = -inv(C)*G;
        B = -A*ones(n,1);
        T = linspace(0,2000,1000);
        Y = simple_step(A,B,T(2),length(T));
        hold off; plot(T,Y,'-');  hold on;
        xlabel('time');
        ylabel('v');

        % compute threshold delay, elmore delay, dominant time constant
        tthres=T(min(find(Y(n,:)>0.5)));
        GinvC=full(G\C);
        tdom=max(eig(GinvC));
        telm=max(sum(GinvC'));
        plot(tdom*[1;1], [0;1], '--', telm*[1;1], [0;1],'--', ...
             tthres*[1;1], [0;1], '--');
        text(tdom,0,'d');
        text(telm,0,'e');
        text(tthres,0,'t');
        title(sprintf('Step responses at the 21 nodes for solution (%d), Tmax=%g', xi, delay ));

    end

end

%
% Plot the tradeoff curve
%

figure(1)
ind = finite(areas);
plot(areas(ind), delays(ind));
xlabel('Area');
ylabel('Tdom');
title('Area-delay tradeoff curve');
hold on
for k = 1 : xnpts,
    text( xareas(k), xdelays(k), sprintf( '(%d)', k ) );
end


%
% Draw wires for the four solutions
%

figure(2)
m2 = 2 * m;
x1 = reshape( [ 1 : m ; 1 : m ], 1, m2 );
x2 = x1( 1, end : -1 : 1 );
y  = [ - 0.5 * sizes(x1,:) ; + 0.5 * sizes(x2,:) ; - 0.5 * sizes(1,:)  ];
x1 = reshape( [ 0 : m - 1 ; 1 : m ], m2, 1 );
x2 = x1( end : -1 : 1, 1 );
x  = [ x1 ; x2 ; 0 ];
h = fill( x, y, ones(4*m+1,1)*[0.9,0.8,0.7,0.6] );
hold on
h2 = plot( x, y, '-' );
axis([ -0.1, m + 0.1, min(y(:))-0.25, max(y(:))+0.1 ]);
colormap(gray);
caxis([-1,1]);
title('Solutions at points on the tradeoff curve');
legends = {};
for k = 1 : xnpts,
    set( h(k), 'EdgeColor', get( h2(k), 'Color' ) );
    legends{k} = sprintf( 'Tmax=%g', xdelays(k) );
end
legend(legends{:},4);

cvx_quiet(cvxq);