基于連接關(guān)系的標(biāo)準(zhǔn)單元布局算法研究

李叢

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

關(guān)鍵詞：權(quán)重 分層 布局算法

中圖分類號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）02（c）-0010-01

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

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

（1）根據(jù)單元的連接關(guān)系對(duì)單元進(jìn)行分層。

（2）根據(jù)分層后單元的分布情況，對(duì)權(quán)重進(jìn)行調(diào)整。

1 布局問題描述

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

2 連接關(guān)系算法介紹

布局區(qū)域版面有I/O等固定點(diǎn)，如圖2所示。

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

本算法描述如下：

（1）找到文件中的固定單元，形成一個(gè)單元集合i（i=0），此時(shí)設(shè)置一個(gè)level標(biāo)記變量，置為0。（2）根據(jù)單元集合i（i=0）找到與它們直接相連的可移動(dòng)的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動(dòng)單元與固定單元的連接權(quán)重增加，計(jì)算求出結(jié)果，將坐標(biāo)結(jié)果記錄，并將i中單元的移動(dòng)狀態(tài)置為fixed。（4）level+1，根據(jù)集合i找到與之直接相連的可移動(dòng)單元的集合，i+1，重復(fù)（3）。直到單元都為固定狀態(tài)時(shí)，結(jié)束。

3 算法結(jié)果分析

本文用C++進(jìn)行算法實(shí)現(xiàn)，并在Intel Xeon3.0Hz CPU，6G內(nèi)存的服務(wù)器上運(yùn)行。分層之后的布局結(jié)果表明，迭代求解次數(shù)減少，在保證求解質(zhì)量的前提下，提高了算法的效率。

4 結(jié)語

在這篇文章中，提出一種基于連接關(guān)系的總體布局算法，并通過大量實(shí)驗(yàn)探索研究影響該算法結(jié)果的各個(gè)因子。通過大量實(shí)驗(yàn)發(fā)現(xiàn)了該算法的有效性和合理性。

參考文獻(xiàn)

[1] 徐寧，洪先龍.超大規(guī)模集成電路物理設(shè)計(jì)理論與算法[M].北京：清華大學(xué)出版社，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

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

關(guān)鍵詞：權(quán)重 分層 布局算法

中圖分類號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）02（c）-0010-01

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

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

（1）根據(jù)單元的連接關(guān)系對(duì)單元進(jìn)行分層。

（2）根據(jù)分層后單元的分布情況，對(duì)權(quán)重進(jìn)行調(diào)整。

1 布局問題描述

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

2 連接關(guān)系算法介紹

布局區(qū)域版面有I/O等固定點(diǎn)，如圖2所示。

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

本算法描述如下：

（1）找到文件中的固定單元，形成一個(gè)單元集合i（i=0），此時(shí)設(shè)置一個(gè)level標(biāo)記變量，置為0。（2）根據(jù)單元集合i（i=0）找到與它們直接相連的可移動(dòng)的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動(dòng)單元與固定單元的連接權(quán)重增加，計(jì)算求出結(jié)果，將坐標(biāo)結(jié)果記錄，并將i中單元的移動(dòng)狀態(tài)置為fixed。（4）level+1，根據(jù)集合i找到與之直接相連的可移動(dòng)單元的集合，i+1，重復(fù)（3）。直到單元都為固定狀態(tài)時(shí)，結(jié)束。

3 算法結(jié)果分析

本文用C++進(jìn)行算法實(shí)現(xiàn)，并在Intel Xeon3.0Hz CPU，6G內(nèi)存的服務(wù)器上運(yùn)行。分層之后的布局結(jié)果表明，迭代求解次數(shù)減少，在保證求解質(zhì)量的前提下，提高了算法的效率。

4 結(jié)語

在這篇文章中，提出一種基于連接關(guān)系的總體布局算法，并通過大量實(shí)驗(yàn)探索研究影響該算法結(jié)果的各個(gè)因子。通過大量實(shí)驗(yàn)發(fā)現(xiàn)了該算法的有效性和合理性。

參考文獻(xiàn)

[1] 徐寧，洪先龍.超大規(guī)模集成電路物理設(shè)計(jì)理論與算法[M].北京：清華大學(xué)出版社，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

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

關(guān)鍵詞：權(quán)重 分層 布局算法

中圖分類號(hào)：TP393.02 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）02（c）-0010-01

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

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

（1）根據(jù)單元的連接關(guān)系對(duì)單元進(jìn)行分層。

（2）根據(jù)分層后單元的分布情況，對(duì)權(quán)重進(jìn)行調(diào)整。

1 布局問題描述

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

2 連接關(guān)系算法介紹

布局區(qū)域版面有I/O等固定點(diǎn)，如圖2所示。

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

本算法描述如下：

（1）找到文件中的固定單元，形成一個(gè)單元集合i（i=0），此時(shí)設(shè)置一個(gè)level標(biāo)記變量，置為0。（2）根據(jù)單元集合i（i=0）找到與它們直接相連的可移動(dòng)的單元的集合i（i=1），level自加1。（3）修改矩陣中的值，將集合i中的可移動(dòng)單元與固定單元的連接權(quán)重增加，計(jì)算求出結(jié)果，將坐標(biāo)結(jié)果記錄，并將i中單元的移動(dòng)狀態(tài)置為fixed。（4）level+1，根據(jù)集合i找到與之直接相連的可移動(dòng)單元的集合，i+1，重復(fù)（3）。直到單元都為固定狀態(tài)時(shí)，結(jié)束。

3 算法結(jié)果分析

本文用C++進(jìn)行算法實(shí)現(xiàn)，并在Intel Xeon3.0Hz CPU，6G內(nèi)存的服務(wù)器上運(yùn)行。分層之后的布局結(jié)果表明，迭代求解次數(shù)減少，在保證求解質(zhì)量的前提下，提高了算法的效率。

4 結(jié)語

在這篇文章中，提出一種基于連接關(guān)系的總體布局算法，并通過大量實(shí)驗(yàn)探索研究影響該算法結(jié)果的各個(gè)因子。通過大量實(shí)驗(yàn)發(fā)現(xiàn)了該算法的有效性和合理性。

參考文獻(xiàn)

[1] 徐寧，洪先龍.超大規(guī)模集成電路物理設(shè)計(jì)理論與算法[M].北京：清華大學(xué)出版社，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