Homec4science
Diffusion EMPoWER (master) Browse

R1252/simulation-code/cvx/examples/gp_tutorial/html/elmore_interconnect.html
de096106547amaster

Last Change
Raw File

elmore_interconnect.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Elmore delay sizing for an interconnect network.</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/gp_tutorial/html/elmore_interconnect.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Elmore delay sizing for an interconnect network.</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd, Kim, Vandenberghe, and Hassibi, "A Tutorial on Geometric Programming"</span>
<span class="comment">% Boyd, Kim, Patil, and Horowitz, "Digital circuit optimization via geometric programming"</span>
<span class="comment">% Written for CVX by Almir Mutapcic 02/08/06</span>
<span class="comment">% (a figure is generated)</span>
<span class="comment">%</span>
<span class="comment">% We consider the problem of finding optimal wire widths w_i</span>
<span class="comment">% of N wire segments in an interconnect network, which will</span>
<span class="comment">% minimize the critical Elmore delay, subject to limits on</span>
<span class="comment">% wire widths and the total circuit area. We use a pi-model</span>
<span class="comment">% for each wire segment. Problem can be formulated as GP:</span>
<span class="comment">%</span>
<span class="comment">% minimize D</span>
<span class="comment">% s.t. w_min &lt;= w &lt;= w_max</span>
<span class="comment">% area &lt;= Amax</span>
<span class="comment">%</span>
<span class="comment">% where variables are widths w (and arrival times T that are used</span>
<span class="comment">% to formulate the overall delay D expression).</span>
<span class="comment">%</span>
<span class="comment">% Important: We label root node as 1, and all the other nodes as</span>
<span class="comment">% node_label_in_the_paper + 1 (due to Matlab's convention).</span>
<span class="comment">% Also label nodes with increasing numbers downstream.</span>
<span class="comment">%********************************************************************</span>
<span class="comment">% user supplied data (problem constants and tree topology)</span>
<span class="comment">%********************************************************************</span>
N = 6; <span class="comment">% number of nodes (including the root node which is labeled as 1)</span>
<span class="comment">% parent node array</span>
<span class="comment">% specifies which node is a unique parent for node i (always have a tree)</span>
parent(1) = 0; <span class="comment">% root node does not have a valid parent</span>
parent(2) = 1;
parent(3) = 2;
parent(4) = 3;
parent(5) = 2;
parent(6) = 5;
<span class="comment">% problem constants</span>
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);
<span class="comment">% load capacitance at each node</span>
C1 = 10; C2 = 10; C3 = 10; C4 = 10; C5 = 10;
Cload = [0 C1 C2 C3 C4 C5];
<span class="comment">% minimum and maximum width and area specification</span>
Wmin = 1;
Wmax = 10;
Amax = 15;
<span class="comment">%********************************************************************</span>
<span class="comment">% derived data (computed from user's data)</span>
<span class="comment">%********************************************************************</span>
<span class="comment">% compute children cell array (evaluate who are children for each node)</span>
children = cell(N,1);
leafs = [];
<span class="keyword">for</span> node = [1:N]
children{node} = find(parent == node);
<span class="keyword">if</span> isempty(children{node})
leafs(end+1) = node; <span class="comment">% leafs have no children</span>
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="comment">%********************************************************************</span>
<span class="comment">% optimization (generating optimal tradeoff curve)</span>
<span class="comment">%********************************************************************</span>
disp(<span class="string">'Generating the tradeoff curve...'</span>)
Darray = [];
<span class="keyword">for</span> Amax = [5.05 5.25 5.5 5.75 6:25]
<span class="comment">% formulate the GP problem and solve it</span>
cvx_begin <span class="string">gp</span> <span class="string">quiet</span>
<span class="comment">% optimization variables</span>
variable <span class="string">w(N-1)</span> <span class="comment">% wire width</span>
variable <span class="string">T(N)</span> <span class="comment">% arrival time (Elmore delay to node i)</span>
<span class="comment">% area definition</span>
area = sum(w.*l);
<span class="comment">% wire segment resistance is inversely proportional to widths</span>
R = alpha.*l./w;
R = [Rsource; R];
<span class="comment">% wire segment capacitance is an affine function of widths</span>
C_bar = beta.*l.*w + gamma.*l;
C_bar = [0; C_bar];
<span class="comment">% compute common capacitances for each node (C_tilde in GP tutorial)</span>
C_tilde = cvx( zeros(N,1) );
<span class="keyword">for</span> node = [1:N]
C_tilde(node,1) = Cload(node);
<span class="keyword">for</span> k = parent(node)
<span class="keyword">if</span> k &gt; 0; C_tilde(node,1) = C_tilde(node,1) + C_bar(k); <span class="keyword">end</span>;
<span class="keyword">end</span>
<span class="keyword">for</span> k = children{node}
C_tilde(node,1) = C_tilde(node,1) + C_bar(k);
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="comment">% now compute total downstream capacitances</span>
C_total = C_tilde;
<span class="keyword">for</span> node = N:-1:1
<span class="keyword">for</span> k = children{node}
C_total(node,1) = C_total(node,1) + C_total(k,1);
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="comment">% objective is the critical Elmore delay</span>
minimize( max( T(leafs) ) )
subject <span class="string">to</span>
<span class="comment">% generate Elmore delay constraints</span>
R(1)*C_total(1) &lt;= T(1,1);
<span class="keyword">for</span> node = 2:N
R(node)*C_total(node) + T(parent(node),1) &lt;= T(node,1);
<span class="keyword">end</span>
<span class="comment">% area and width constraints</span>
area &lt;= Amax;
w &gt;= Wmin;
w &lt;= Wmax;
cvx_end
<span class="comment">% display and store computed values</span>
fprintf(1,<span class="string">' Amax = %5.2f delay = %3.2f\n'</span>,Amax,cvx_optval);
Darray = [Darray cvx_optval];
<span class="keyword">end</span>
<span class="comment">% plot the tradeoff curve</span>
figure, clf
Amax = [5.05 5.25 5.5 5.75 6:25];
plot(Darray,Amax);
xlabel(<span class="string">'Elmore delay D'</span>); ylabel(<span class="string">'Amax'</span>);
</pre>
<a id="output"></a>
<pre class="codeoutput">
Generating the tradeoff curve...
Amax = 5.05 delay = 107.82
Amax = 5.25 delay = 98.33
Amax = 5.50 delay = 90.12
Amax = 5.75 delay = 84.35
Amax = 6.00 delay = 80.10
Amax = 7.00 delay = 69.64
Amax = 8.00 delay = 62.95
Amax = 9.00 delay = 58.10
Amax = 10.00 delay = 54.27
Amax = 11.00 delay = 51.17
Amax = 12.00 delay = 48.62
Amax = 13.00 delay = 46.50
Amax = 14.00 delay = 44.71
Amax = 15.00 delay = 43.19
Amax = 16.00 delay = 41.88
Amax = 17.00 delay = 40.76
Amax = 18.00 delay = 39.78
Amax = 19.00 delay = 38.92
Amax = 20.00 delay = 38.18
Amax = 21.00 delay = 37.52
Amax = 22.00 delay = 36.94
Amax = 23.00 delay = 36.43
Amax = 24.00 delay = 35.98
Amax = 25.00 delay = 35.59
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="elmore_interconnect__01.png" alt="">
</div>
</div>
</body>
</html>
c4science · Help