基于連接關系的標準單元布局算法研究

李叢

摘 要：本文對一種基于連接關系的快速布局算法進行了探索研究，該算法以優化一次線長為目標，利用單元給定連接關系信息消除單元重疊。

關鍵詞：權重 分層 布局算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1672-3791（2014）02（c）-0010-01

超大規模集成電路的單元布局問題是一個在給定單元信息的基礎上對單元集合進行布局的問題。它即使在最簡單的情況下也是一個NP難的問題。因此，隨著集成電路規模的增大，對超大規模的布局算法是一個挑戰。布局階段要求把模塊分配到芯片上的合適位置，算法分為兩種：一種是線長驅動的布局算法，一種是性能驅動的布局算法。其中線長驅動以線長最短為目標，在保證單元之間沒有重疊擺放的前提下優化線長，線長越短，算法效果越好。[1～3]

因此，在保證算法質量的情況下，本文提出了一種基于單元的物理位置的連接關系分層算法。連接關系是指在給定NetList中包含線網的信息，在布局優化的趨勢來看，在同一個線網中的單元被分布到相近的區域有助于總線長的減少，因此在初始階段，提出以下兩點方法：

（1）根據單元的連接關系對單元進行分層。

（2）根據分層后單元的分布情況，對權重進行調整。

1 布局問題描述

本文利用一次線長模型進行線長估計，分為三個部分：初始布局、總體布局、詳細布局。[4]其中初始布局部分的流程如圖1所示。

2 連接關系算法介紹

布局區域版面有I/O等固定點，如圖2所示。

初始布局后多數單元在版面中心處堆疊，根據單元與固定點的連接關系，對單元進行分層處理，將這些堆疊的單元散開。如圖2所示，最外層邊框上有I/O點，首先將與I/O直接相連的單元移動到最外層；第二步，將與第一層的單元直接相連的單元移動至次外層；第三步，將與第二層的單元直接相連的單元移動至第三層圓角矩形的邊緣，依此進行迭代重復。最終使單元被均勻分布到設計版面上。

本算法描述如下：

（1）找到文件中的固定單元，形成一個單元集合i（i=0），此時設置一個level標記變量，置為0。（2）根據單元集合i（i=0）找到與它們直接相連的可移動的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動單元與固定單元的連接權重增加，計算求出結果，將坐標結果記錄，并將i中單元的移動狀態置為fixed。（4）level+1，根據集合i找到與之直接相連的可移動單元的集合，i+1，重復（3）。直到單元都為固定狀態時，結束。

3 算法結果分析

本文用C++進行算法實現，并在Intel Xeon3.0Hz CPU，6G內存的服務器上運行。分層之后的布局結果表明，迭代求解次數減少，在保證求解質量的前提下，提高了算法的效率。

4 結語

在這篇文章中，提出一種基于連接關系的總體布局算法，并通過大量實驗探索研究影響該算法結果的各個因子。通過大量實驗發現了該算法的有效性和合理性。

參考文獻

[1] 徐寧，洪先龍.超大規模集成電路物理設計理論與算法[M].北京：清華大學出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint

摘 要：本文對一種基于連接關系的快速布局算法進行了探索研究，該算法以優化一次線長為目標，利用單元給定連接關系信息消除單元重疊。

關鍵詞：權重 分層 布局算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1672-3791（2014）02（c）-0010-01

超大規模集成電路的單元布局問題是一個在給定單元信息的基礎上對單元集合進行布局的問題。它即使在最簡單的情況下也是一個NP難的問題。因此，隨著集成電路規模的增大，對超大規模的布局算法是一個挑戰。布局階段要求把模塊分配到芯片上的合適位置，算法分為兩種：一種是線長驅動的布局算法，一種是性能驅動的布局算法。其中線長驅動以線長最短為目標，在保證單元之間沒有重疊擺放的前提下優化線長，線長越短，算法效果越好。[1～3]

因此，在保證算法質量的情況下，本文提出了一種基于單元的物理位置的連接關系分層算法。連接關系是指在給定NetList中包含線網的信息，在布局優化的趨勢來看，在同一個線網中的單元被分布到相近的區域有助于總線長的減少，因此在初始階段，提出以下兩點方法：

（1）根據單元的連接關系對單元進行分層。

（2）根據分層后單元的分布情況，對權重進行調整。

1 布局問題描述

本文利用一次線長模型進行線長估計，分為三個部分：初始布局、總體布局、詳細布局。[4]其中初始布局部分的流程如圖1所示。

2 連接關系算法介紹

布局區域版面有I/O等固定點，如圖2所示。

初始布局后多數單元在版面中心處堆疊，根據單元與固定點的連接關系，對單元進行分層處理，將這些堆疊的單元散開。如圖2所示，最外層邊框上有I/O點，首先將與I/O直接相連的單元移動到最外層；第二步，將與第一層的單元直接相連的單元移動至次外層；第三步，將與第二層的單元直接相連的單元移動至第三層圓角矩形的邊緣，依此進行迭代重復。最終使單元被均勻分布到設計版面上。

本算法描述如下：

（1）找到文件中的固定單元，形成一個單元集合i（i=0），此時設置一個level標記變量，置為0。（2）根據單元集合i（i=0）找到與它們直接相連的可移動的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動單元與固定單元的連接權重增加，計算求出結果，將坐標結果記錄，并將i中單元的移動狀態置為fixed。（4）level+1，根據集合i找到與之直接相連的可移動單元的集合，i+1，重復（3）。直到單元都為固定狀態時，結束。

3 算法結果分析

本文用C++進行算法實現，并在Intel Xeon3.0Hz CPU，6G內存的服務器上運行。分層之后的布局結果表明，迭代求解次數減少，在保證求解質量的前提下，提高了算法的效率。

4 結語

在這篇文章中，提出一種基于連接關系的總體布局算法，并通過大量實驗探索研究影響該算法結果的各個因子。通過大量實驗發現了該算法的有效性和合理性。

參考文獻

[1] 徐寧，洪先龍.超大規模集成電路物理設計理論與算法[M].北京：清華大學出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint

摘 要：本文對一種基于連接關系的快速布局算法進行了探索研究，該算法以優化一次線長為目標，利用單元給定連接關系信息消除單元重疊。

關鍵詞：權重 分層 布局算法

中圖分類號：TP393.02 文獻標識碼：A 文章編號：1672-3791（2014）02（c）-0010-01

超大規模集成電路的單元布局問題是一個在給定單元信息的基礎上對單元集合進行布局的問題。它即使在最簡單的情況下也是一個NP難的問題。因此，隨著集成電路規模的增大，對超大規模的布局算法是一個挑戰。布局階段要求把模塊分配到芯片上的合適位置，算法分為兩種：一種是線長驅動的布局算法，一種是性能驅動的布局算法。其中線長驅動以線長最短為目標，在保證單元之間沒有重疊擺放的前提下優化線長，線長越短，算法效果越好。[1～3]

因此，在保證算法質量的情況下，本文提出了一種基于單元的物理位置的連接關系分層算法。連接關系是指在給定NetList中包含線網的信息，在布局優化的趨勢來看，在同一個線網中的單元被分布到相近的區域有助于總線長的減少，因此在初始階段，提出以下兩點方法：

（1）根據單元的連接關系對單元進行分層。

（2）根據分層后單元的分布情況，對權重進行調整。

1 布局問題描述

本文利用一次線長模型進行線長估計，分為三個部分：初始布局、總體布局、詳細布局。[4]其中初始布局部分的流程如圖1所示。

2 連接關系算法介紹

布局區域版面有I/O等固定點，如圖2所示。

初始布局后多數單元在版面中心處堆疊，根據單元與固定點的連接關系，對單元進行分層處理，將這些堆疊的單元散開。如圖2所示，最外層邊框上有I/O點，首先將與I/O直接相連的單元移動到最外層；第二步，將與第一層的單元直接相連的單元移動至次外層；第三步，將與第二層的單元直接相連的單元移動至第三層圓角矩形的邊緣，依此進行迭代重復。最終使單元被均勻分布到設計版面上。

本算法描述如下：

（1）找到文件中的固定單元，形成一個單元集合i（i=0），此時設置一個level標記變量，置為0。（2）根據單元集合i（i=0）找到與它們直接相連的可移動的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動單元與固定單元的連接權重增加，計算求出結果，將坐標結果記錄，并將i中單元的移動狀態置為fixed。（4）level+1，根據集合i找到與之直接相連的可移動單元的集合，i+1，重復（3）。直到單元都為固定狀態時，結束。

3 算法結果分析

本文用C++進行算法實現，并在Intel Xeon3.0Hz CPU，6G內存的服務器上運行。分層之后的布局結果表明，迭代求解次數減少，在保證求解質量的前提下，提高了算法的效率。

4 結語

在這篇文章中，提出一種基于連接關系的總體布局算法，并通過大量實驗探索研究影響該算法結果的各個因子。通過大量實驗發現了該算法的有效性和合理性。

參考文獻

[1] 徐寧，洪先龍.超大規模集成電路物理設計理論與算法[M].北京：清華大學出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint