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