開關(guān)盒布線設(shè)計報告

1、面向?qū)ο缶幊碳夹g(shù)課程設(shè)計報告 姓 名： 何文韜 學(xué) 號： 21509149 院 系： 電信 控制 郵 箱： 1305415168 完成日期： 2015-12-09 開關(guān)盒布線問題1 問題分析開關(guān)盒布線問題，從整個系統(tǒng)實現(xiàn)上分析，應(yīng)包含以下幾方面：開關(guān)盒的創(chuàng)建、載入與保存，可布線判斷，布線算法的實現(xiàn)，界面顯示等等。1.1 開關(guān)盒的創(chuàng)建、載入、與保存需定義相關(guān)C+類描述開關(guān)盒屬性及其相關(guān)操作，屬性包括開關(guān)盒尺寸、線寬、線間距、引腳分布、布線網(wǎng)組等；在軟件界面設(shè)置各參數(shù)后，需將開關(guān)盒參數(shù)保存至數(shù)據(jù)庫，并且，隨時可以從數(shù)據(jù)庫中調(diào)出已經(jīng)建立好的開關(guān)盒進行重新布線、修改等操作；數(shù)據(jù)庫的相關(guān)操作使用MFC的

2、DAO數(shù)據(jù)庫接口。運行環(huán)境選擇VS2005。1.2 可布線判斷可布線判斷，即判斷針對當(dāng)前開關(guān)盒屬性，在各引線不交叉的前提下，是否可以完成各網(wǎng)組的布線。值得注意的是，網(wǎng)組的可布線與否應(yīng)當(dāng)取決于兩方面：網(wǎng)組邏輯是否可布線（網(wǎng)組間存在交叉則肯定不能布），與實際布線是否可完成（受限于開關(guān)盒尺寸、線寬及線間距等參數(shù)，邏輯上可以布線但實際中可能無法完成）。故可布線判斷分為兩部分：初步的可布線邏輯判斷，和最后的實際布線探測。1.3 布線算法實現(xiàn)實現(xiàn)布線，需考慮諸多問題，如布線路徑的表示方法、怎樣引入線間最小間距限制等等，綜合考慮，采用一個二維網(wǎng)格地圖來劃分開關(guān)盒，將很方便的解決這些問題，如圖1.1所示:圖1

3、.1 將開關(guān)盒布線區(qū)域劃分為二維網(wǎng)格每個正方形網(wǎng)格的邊長即等于線寬加上線間距，即可引入線寬、線間距等參數(shù)的限制；每一個網(wǎng)格就是一個路徑節(jié)點，我們要獲得兩個引腳之間的導(dǎo)線路徑，即計算出路徑所經(jīng)過的節(jié)點即可。經(jīng)過上面的預(yù)處理后，布線問題可簡化為二維地圖的約束化路徑搜索問題。具體搜索過程見第二部分-算法選擇與方案設(shè)計。1.4 界面顯示編寫簡單的MFC基于對話框的界面應(yīng)用程序，完成各功能交互，重寫對話框的Opaint()函數(shù)，完成開關(guān)盒及布線的繪制；通過設(shè)置定時器可實現(xiàn)布線過程的動態(tài)繪制。2 算法選擇與方案設(shè)計基于上面的問題分析，下面著重介紹布線的實現(xiàn)過程。2.1 布線過程整體方案設(shè)計值得注意的是，開

4、關(guān)盒的布線過程應(yīng)該是一個整體優(yōu)化的過程，而不是簡單的各條連接線按順序搜索路徑（因為一個局部連線路徑雖然可行，但很有可能會影響其它路徑的連接，導(dǎo)致全局整體布線效果差，最壞的情況還可能導(dǎo)致本可以完成布線，卻最終因一條路徑的選取影響了全局，而導(dǎo)致整體布線失敗）。直覺上，可以在完成當(dāng)前導(dǎo)線連接的過程中，實時的調(diào)節(jié)之前已經(jīng)連接好的線路，進而達到最后的整體最優(yōu)。然而，實際中，調(diào)節(jié)已經(jīng)連接完畢的線路實現(xiàn)復(fù)雜，且沒有很好地理論指導(dǎo)，難于實現(xiàn)。總結(jié)上面所述，就是在連接每一條線路時，由于缺乏對全局的觀測（因為全局到最后才能觀測到），當(dāng)前線路幾乎不可能（或很難）連接成最優(yōu)的。為解決上面的問題，這里提出了一個理念：整

5、體布線最優(yōu)=布線的最小實現(xiàn)+后期優(yōu)化；下面依次解釋一下各個概念：（1）整體布線最優(yōu)：整體最優(yōu)其實有很多種描述方法，比如說整體線路長度最短，或者說整體線路看起來比較美觀（這個其實沒有準(zhǔn)確的描述）；這里，我們選取整體線路看起來比較美觀作為布線最優(yōu)，選取了一個定量的方式來描述“美觀”，即每條線在不影響可布線的前提下，盡可能少拐彎。（2）布線的最小實現(xiàn)：即最大可能的保證當(dāng)每一條連線不會影響到其它連線。實現(xiàn)過程很簡單，通俗的說，就是按照每一條連線的兩個端點距離由小到大的順序，搜索路徑，在搜索路徑的過程中，盡可能讓線路貼邊走，如圖2.1所示：圖2.1 布線的最小實現(xiàn)從圖2.1可以看出，布線的最小實現(xiàn)已經(jīng)完

6、成了布線任務(wù)，只是，看起來不是很美觀。這里值得說明的是，從直觀的觀察上即可看出，能否實現(xiàn)布線的最小實現(xiàn)，是開關(guān)盒可布線與否的充要條件。即回答了1.2中的問題。布線最小實現(xiàn)過程：在1.3中介紹的劃分好二維網(wǎng)格后，由起點到終點，使用深度優(yōu)先搜索探測路徑，在所搜的過程中，要時刻根據(jù)目標(biāo)點與當(dāng)前點的位置關(guān)系，調(diào)整搜索的方向為“貼邊”的方向，這樣最后的路徑才是一條“貼邊”的路徑。（3）后期優(yōu)化：在介紹整體布線最優(yōu)時已經(jīng)提到，本文中的最優(yōu)原則即是每條線在不影響可布線的前提下，盡可能少拐彎。在實現(xiàn)了布線最小實現(xiàn)的前提下，我們再按順序?qū)γ恳粭l線路進行優(yōu)化，此時優(yōu)化可以觀測到全局，因為布線的最小實現(xiàn)即是全局，這

7、樣，每條線的優(yōu)化以已完成的最小實現(xiàn)為限制，不會影響到全局的整體布線。拐彎最少，是一個優(yōu)化問題，在實現(xiàn)的過程中使用了寬度優(yōu)先搜索的方法，先從起點到終點，計算出需最少拐彎個數(shù)；再根據(jù)計算出的最少拐彎個數(shù)，利用深度優(yōu)先搜索，記錄下這條路徑。2.2 整體方案流程根據(jù)2.1中描述的“整體布線最優(yōu)=布線的最小實現(xiàn)+后期優(yōu)化”原則，設(shè)計了如圖2.2的方案流程：圖2.2 開關(guān)盒布線整體方案流程3 編程實現(xiàn)3.1軟件交互界面軟件系統(tǒng)采用MFC基于對話框的界面程序框架，所設(shè)計的軟件系統(tǒng)界面如圖3.1所示：圖3.1 軟件系統(tǒng)界面點擊“手動創(chuàng)建新開關(guān)盒”按鈕，下方參數(shù)控件變?yōu)榭捎茫稍O(shè)置開關(guān)盒參數(shù)；點擊“從數(shù)據(jù)庫中導(dǎo)

8、入新開關(guān)盒”按鈕，即可從數(shù)據(jù)庫中調(diào)出已有的所有開關(guān)盒，選擇其中一條記錄，點擊“導(dǎo)入”，即可導(dǎo)入此開關(guān)盒，見圖3.2：圖3.2 從數(shù)據(jù)庫中導(dǎo)入開關(guān)盒手動創(chuàng)建或從數(shù)據(jù)庫導(dǎo)入開關(guān)盒后，點擊“開始布線”按鈕，可完成布線功能；右側(cè)顯示窗口，顯示開關(guān)盒狀態(tài)及布線結(jié)果，為防止動態(tài)顯示時屏幕閃爍問題，采用雙緩存策略進行實時顯示（即創(chuàng)建內(nèi)存DC）。選擇“實時顯示”單選按鈕后，布線結(jié)果將以動態(tài)形式顯示。3.2 算法編程實現(xiàn)定義了若干C+類用來描述開關(guān)盒各屬性及其相關(guān)操作，定義的類主要包括：開關(guān)盒類CSwitchBox，連接類CConnection，引腳類CPin，二維網(wǎng)格節(jié)點類CNode；實現(xiàn)的過程中主要用到的算法是深度優(yōu)先搜索和寬度優(yōu)先搜索，深度優(yōu)先搜索由遞歸實現(xiàn)，寬搜最少拐彎數(shù)時，采用寬搜+優(yōu)先隊列技術(shù)；具體實現(xiàn)過程見代碼。3.3 運行結(jié)果下面是幾組開關(guān)盒的運行結(jié)果，均已在數(shù)據(jù)庫中保留：圖3.3 示例1結(jié)果圖3.4 示例4結(jié)果3.4 結(jié)果分析及不足由于“后期優(yōu)化”部分的算法實現(xiàn)較復(fù)雜，此處的深搜代碼實現(xiàn)的不是十分正確，剪枝不夠，導(dǎo)致有些連線不能在有限時間內(nèi)計算出