# Tri-state bus sizing and topology design

Jump to: Source code Text output Plots Library index

    % Section 5.4,  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/27/05
    % Modified by Michael Grant - 3/8/06
    %
    % We optimize a tri-state bus connecting six nodes ( The model for the bus
    % is shown in the paper, fig.16). The total wire area is sum_{i>j} lij*xij
    % The bus can be driven from any node. When node i drives the bus, the ith
    % switch is closed and the others are all open. Thus we really have six
    % different circuits, each corresponding to a given node driving the bus.
    % we require that the dominant time constant of each of the six drive
    % configuration circuits has dominant time constant less than Tmax.
    % The problem can be formulated with the following SDP:
    %               minimize        sum_{i>j}(x_ij*l_ij)
    %                   s.t.        0 <= xij <= wmax
    %                               Tmax*(G(x) + GE_kk) - C(x) >= 0 , 1 <=k<= 6
    % The matrix E_kk is zero except for the kth diagonal element, which is 1.

    %
    % Circuit parameters
    %

    n=6;         % number of nodes
    m=15;        % number of wires
    beta = 0.5;  % capacitance per segment is twice beta times xi*li
    alpha = 1;   % conductance per segment is alpha times xi/li
    G0 = 1;      % source conductance
    C0 = 10;     % load capacitor
    wmax = 1;    % upper bound on x

    %
    % Node positions
    %

    xpos = [ 0   1   6   8  -4  -1 ;
             0  -1   4  -2   1   4 ] ;
    X11 = repmat(xpos(1,:),n,1);
    X12 = repmat(xpos(1,:)',1,n);
    X21 = repmat(xpos(2,:),n,1);
    X22 = repmat(xpos(2,:)',1,n);
    LL  = abs(X11-X12) + abs(X21-X22);
    L   = tril(LL);
    L   = L(L>0);

    %
    % Construct the capacitance and conductance matrices
    %   C(x) = C0 + w11 * C1 + w21 * C2 + ...
    %   G(x) = G0 + w11 * G1 + w21 * G2 + ...
    % and we assemble the coefficient matrices together as follows:
    %   CC = [ C0(:) C1(:) C2(:) ... ]
    %   GG = [ G0(:) G1(:) G2(:) ... ]
    %

    CC = zeros(n,n,m+1);
    GG = zeros(n,n,m+1);
    CC(:,:,1) = C0 * eye(n);
    % segment capacitances and conductances
    k3 = 1;
    for k1 = 1 : 5,
        for k2 = k1 + 1 : 6,
            CC([k1,k2],[k1,k2],k3) = beta *[1, 0; 0,1]*L(k3);
            GG([k1,k2],[k1,k2],k3) = alpha*[1,-1;-1,1]/L(k3);
            k3 = k3 + 1;
        end
    end
    GG = reshape( GG, n*n, m+1 );
    CC = reshape( CC, n*n, m+1 );

    %
    % Compute points the tradeoff curve and the two desired points
    %

    % points on the tradeoff curve
    npts    = 50;
    delays  = linspace( 410, 2000, npts );
    xdelays = [ 410, 2000 ];
    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 quiet
            variable x(m)
            variable G(n,n) symmetric
            variable C(n,n) symmetric
            minimize( L'*x )
            G == reshape( GG * [ 1 ; x ], n, n );
            C == reshape( CC * [ 1 ; x ], n, n );
            for k = 1 : n,
                delay * G - C + sparse(k,k,delay,n,n) >= 0;
            end
            0 <= x <= wmax;
        cvx_end

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

            %
            % Plot the step response
            %

            T = linspace(0,2*delay,1000);
            for inp = 1 : 6,
                figure(6*xi-5+inp);
                GQ = G + sparse(inp,inp,delay,n,n);
                A = -inv(C)*GQ;
                B = -A*ones(n,1);
                Y = simple_step(A,B,T(2),length(T));
                hold off; plot(T,Y,'-');  hold on;
                ind=0;
                for j=1:size(Y,1),
                    ind = max(min(find(Y(j,:)>=0.5)),ind);
                end
                tdom   = max(eig(inv(GQ)*C));
                elmore = max(sum((inv(GQ)*C)'));
                tthres = T(ind);
                plot( tdom   * [1;1], [0;1], '--', ...
                      elmore * [1;1], [0;1], '--', ...
                      tthres * [1;1], [0;1], '--');
                text(tdom,  0,'d');
                text(elmore,0,'e');
                text(tthres,0,'t');
                ylabel('Voltage');
                title(sprintf('Step response for solution %d, Tmax=%d, with switch %d is closed',xi,delay,inp));
           end

        end

    end;

    %
    % Plot the tradeoff curve
    %

    figure(1)
    ind = isfinite(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

    Point 1 of 50 on the tradeoff curve (Tmax = 410)
    Point 2 of 50 on the tradeoff curve (Tmax = 442.449)
    Point 3 of 50 on the tradeoff curve (Tmax = 474.898)
    Point 4 of 50 on the tradeoff curve (Tmax = 507.347)
    Point 5 of 50 on the tradeoff curve (Tmax = 539.796)
    Point 6 of 50 on the tradeoff curve (Tmax = 572.245)
    Point 7 of 50 on the tradeoff curve (Tmax = 604.694)
    Point 8 of 50 on the tradeoff curve (Tmax = 637.143)
    Point 9 of 50 on the tradeoff curve (Tmax = 669.592)
    Point 10 of 50 on the tradeoff curve (Tmax = 702.041)
    Point 11 of 50 on the tradeoff curve (Tmax = 734.49)
    Point 12 of 50 on the tradeoff curve (Tmax = 766.939)
    Point 13 of 50 on the tradeoff curve (Tmax = 799.388)
    Point 14 of 50 on the tradeoff curve (Tmax = 831.837)
    Point 15 of 50 on the tradeoff curve (Tmax = 864.286)
    Point 16 of 50 on the tradeoff curve (Tmax = 896.735)
    Point 17 of 50 on the tradeoff curve (Tmax = 929.184)
    Point 18 of 50 on the tradeoff curve (Tmax = 961.633)
    Point 19 of 50 on the tradeoff curve (Tmax = 994.082)
    Point 20 of 50 on the tradeoff curve (Tmax = 1026.53)
    Point 21 of 50 on the tradeoff curve (Tmax = 1058.98)
    Point 22 of 50 on the tradeoff curve (Tmax = 1091.43)
    Point 23 of 50 on the tradeoff curve (Tmax = 1123.88)
    Point 24 of 50 on the tradeoff curve (Tmax = 1156.33)
    Point 25 of 50 on the tradeoff curve (Tmax = 1188.78)
    Point 26 of 50 on the tradeoff curve (Tmax = 1221.22)
    Point 27 of 50 on the tradeoff curve (Tmax = 1253.67)
    Point 28 of 50 on the tradeoff curve (Tmax = 1286.12)
    Point 29 of 50 on the tradeoff curve (Tmax = 1318.57)
    Point 30 of 50 on the tradeoff curve (Tmax = 1351.02)
    Point 31 of 50 on the tradeoff curve (Tmax = 1383.47)
    Point 32 of 50 on the tradeoff curve (Tmax = 1415.92)
    Point 33 of 50 on the tradeoff curve (Tmax = 1448.37)
    Point 34 of 50 on the tradeoff curve (Tmax = 1480.82)
    Point 35 of 50 on the tradeoff curve (Tmax = 1513.27)
    Point 36 of 50 on the tradeoff curve (Tmax = 1545.71)
    Point 37 of 50 on the tradeoff curve (Tmax = 1578.16)
    Point 38 of 50 on the tradeoff curve (Tmax = 1610.61)
    Point 39 of 50 on the tradeoff curve (Tmax = 1643.06)
    Point 40 of 50 on the tradeoff curve (Tmax = 1675.51)
    Point 41 of 50 on the tradeoff curve (Tmax = 1707.96)
    Point 42 of 50 on the tradeoff curve (Tmax = 1740.41)
    Point 43 of 50 on the tradeoff curve (Tmax = 1772.86)
    Point 44 of 50 on the tradeoff curve (Tmax = 1805.31)
    Point 45 of 50 on the tradeoff curve (Tmax = 1837.76)
    Point 46 of 50 on the tradeoff curve (Tmax = 1870.2)
    Point 47 of 50 on the tradeoff curve (Tmax = 1902.65)
    Point 48 of 50 on the tradeoff curve (Tmax = 1935.1)
    Point 49 of 50 on the tradeoff curve (Tmax = 1967.55)
    Point 50 of 50 on the tradeoff curve (Tmax = 2000)
    Particular solution 1 of 2 (Tmax = 410)
    Particular solution 2 of 2 (Tmax = 2000)