基于SS序列集成電路不規(guī)則模塊布圖算法
1 模塊的劃分
對于不規(guī)則模塊的先期處理是將其劃分為許多小矩形,從而避免了傳統(tǒng)算法將整個不規(guī)則模塊算為1個大矩形而帶來的面積浪費。如圖1所示,由2個矩形合并而成,傳統(tǒng)分割法將其視為1個矩形整體,再利用SS序列算法將其放入版圖,如圖1(a)所示,造成了底面積的浪費。SS序列無法區(qū)分模塊空白區(qū)域,而是將其視為一整體放入版圖,導(dǎo)致下部空白區(qū)域永遠無法被其他模塊空間占用,帶來了較大浪費,隨著模塊面積增大和不規(guī)則模塊數(shù)量增多,面積浪費現(xiàn)象將更為嚴重。因此在輸入模塊數(shù)據(jù)前就應(yīng)將模塊進行劃分,為了程序計算方便,規(guī)定為對模塊自上而下、以左邊為基準進行劃分,如圖1(b)所示將該不規(guī)則模塊劃分為A、B兩個小矩形輸入數(shù)據(jù),在SS算法處理過程中將其視為兩個連在一起不同的模塊,運用區(qū)域模塊連接算法使其在變換的過程中始終保持緊密的連接在一起,如此則可充分利用下部空余的面積部分。對于有弧形的不規(guī)則模塊,應(yīng)以弧形最邊緣切線為起點畫一矩形將其包圍,如圖1(c)所示模塊。首先以整體模塊最左邊為基準,即起始點,以上半部弧形右邊最頂點為終點,上弧形最頂點為上邊作一矩形,將該不規(guī)則模塊分為上下兩部分矩形。對于更為復(fù)雜的不規(guī)則模塊也是如此劃分。本文引用地址:http://butianyuan.cn/article/188220.htm
2 模塊區(qū)域連接算法
在劃分模塊后,存在許多相互需要連接在一起的小模塊,這時必須要建立新的序列來反映這些模塊間的相互關(guān)系。如圖2所示,SS布圖算法[4]分別變換SS序列及模塊數(shù)據(jù)序列的排列順序,將模塊數(shù)據(jù)序列一一對應(yīng)放入SS序列所生成的單元圖中,使得版圖不斷發(fā)生變化。因此加入了模塊區(qū)域連接序列后,應(yīng)在變換模塊數(shù)據(jù)序列前先將連接在一起的模塊放入SS序列所生成的單元中。算法規(guī)則如下:
(1)將劃分過的小矩形根據(jù)輸入的順序編號,將同一不規(guī)則模塊的小矩形歸為一組,不同組間由0相隔,從而生成反映模塊間相互連接關(guān)系的模塊區(qū)域連接序列。
(2)變換SS序列后,由于模塊是自上而下的劃分,因此需要找出SS單元圖中呈上下連接關(guān)系的單元號先放入不規(guī)則模塊。首先隨機選取1個SS序列號A,找出其相鄰下方的單元且水平位置最接近A的單元號B,即滿足公式Mbl(A)-1=Mas(B)并且Min(|Mbs(A)-Mbs(B)|)的SS序列號。
(3)將模塊區(qū)域連接序列中對應(yīng)的模塊(劃分后的小矩形)放入規(guī)則(2)所找出的單元中。
(4)根據(jù)模塊區(qū)域連接序列,交換與規(guī)則(2)所得的單元號相對應(yīng)的模塊數(shù)據(jù)序列。
(5)生成版圖。
評論