算法分析在元件折叠当中应用.docVIP

算法分析在元件折叠当中应用关键词：贪婪算法、最优化、最优解、分而治之算法、动态规划法、回溯、分枝定界、先进先出、元件折叠 在设计电路的过程中有两种为位－片设计和标准单元设计。在前一种方法中，电路首先被设计为一个元件栈。假如每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。连线可能连接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。在V L SI芯片上为它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。如何将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。一个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需的片数。若栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的最大值。在中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如在C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为5 i =1hi +r6，栈2所需高度为8 i=6hi +r6+r9。在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设此线性顺序中的元件为C1，.，Cn，下一步元件被折叠成相同宽度的行。1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时所需的通道高度。布线通道1的高度为l4，通道2的高度为l6，通道3的高度为l11。位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。 一. 等宽位－片元件折叠：定义r1 = rn+1 =0。由元件Ci 至Cj 构成的栈的高度要求为j k= ilk+ ri+ rj + 1。设一个位－片设计中所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H时），取Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知时，可得到以下公式：Wi =w+ Wk + 1 （1 5 - 9）由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折叠点。令h s u m(i,k)=k j = ihj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。可通过递归计算Wn , Wn- 1., W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的时间为O (n2 )。通过保留式每次所得的k 值，可回溯地计算出各个最优的折叠点，其时间耗费为O (n)。再来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ., Cn 折叠成一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任何折叠，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n另外，当i=n 时，仅有一个元件，也不可能折叠，因此：Hn ,j=hn+rn , 1≤j≤s在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件也需以最小高度进行折叠.因为第一个折叠点未知，尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）的右侧取最小值的点，该点成为第一个折叠点。可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，.，对应每个j 的Hi, j 的计算