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

来源:用户上传      作者:

　　关键词：贪婪算法、最优化、最优解、分而治之算法、动态规划法、回溯、分枝定界、先进先出、元件折叠
　　在设计电路的过程中有两种为位－片设计和标准单元设计。在前一种方法中，电路首先被设计为一个元件栈。假如每个元件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 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过保存由（ 1 5 - 1 2）式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的折叠点。
　　二. 变宽位－片元件的折叠：首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。按照相同的推导过程，可得：Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）其中Wn+1=0且w m i n(i,k)= m ini≤j≤k{wj }。可用与（1 5 - 1 0）式一样的方法求解（1 5 - 1 3）式，所需时间为O(n2 )。当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用（ 1 5 - 1 3）式来确定该折叠的宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。
　　三. 标准单元折叠：用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令w s u m(i, s)=s j = iwj。可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一个元件，不存在连线问题，因此Hn, n =h。对于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的高度为ls+ 1（定义ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的.为了寻找最小高度折叠，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）来确定Hi, s （1≤i≤s≤n）。最小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。
　　
　　注：文章内所有公式及图表请以PDF形式查看。

转载注明来源:https://www.xzbu.com/2/view-580158.htm