多晶片模組佈局自動擺置研究

Abstract

晶片佈局自動化擺置問題是多晶片模組設計中極重要的一步，即使是 在點模擬模式下，亦是一個NP問題。而在面對現今佈局模式中〝不同大小 形狀的裸晶片〞及〝不同形狀維度的佈局區域〞的複雜限制條件時，此問 題變得更加的困難。為了嘗試找出一種能解決多晶片模組自動擺置問題的 方法，我們精讀許多有關「以詢問為基底之自我組織類神經網路」(簡稱 QBSONN)的期刊論文，並從中獲得啟發。QBSONN利用機器學習理論中的詢 問神諭方式來增進自我組織類神經網路之學習效果，是具有一般性的一種 類神經網路架構方式。它已被用來解決超大型積體電路元件佈局自動化擺 置問題，並能獲得不錯的擺置結果。 在本論文中，我們嘗試應用 QBSONN來解決多晶片模組自動擺置的問題，並且實作了一個多晶片模組自 動擺置器，名為〝AMPER 1.0〞。AMPER 1.0版是採用Visual C++ 4.0版的 程式語言設計完成。由於AMPER在Windows 95的環境下工作，所以它具有 完整的圖形化使用者介面和高度的可攜性。在發展AMPER的過程中，我學 到了許多寶貴的視窗程式寫作經驗。主要的擺置目標是讓晶片間的總繞線 長度最小和晶片互不重疊。我們的擺置器能考慮到裸晶片的真實形狀，並 能解決在不同佈局方式下(如晶片陣列或不規則形晶片)之任意長寬矩形晶 片在任意直角多邊形區域上的擺置問題。最後，在測試過很多電路的例子 之後，實驗結果顯示我們的多晶片模組自動擺置器是相當有效的。 chip placement is very important in MCM design and the problem has been provento be NP-hard even for the point-model. For the design of full custom MCM, it hasbeen made more harder with various additional constraints on its bare die sizeand layout region shape/dimension. In order to solve the MCM placement problem,we had a intensive study of a series of journal papers about query-based self-organizing neural network (QBSONN) and got inspiration. QBSONN is a general neuralnetwork model which uses the query oracle technique in machine learning to improvethe learning process of the self-organizing neural network. The model was used toresolve VLSI cell placement and succeeded in yielding a proper placement result. In this thesis, we attempt to apply QBSONN to resolve the MCM placement problemand implement a MCM placement tool "AMPER 1.0". The AMPER 1.0 is developed by usingVisual C++4.0 (MFC) and works on Windows 95 environment. So it has a friendlygraphical user interface and a high portability. During the development process ofthe AMPER, we have learned a valuable experience for Windows programming. The wirelength minimization and module overlap-free are as our primary objective. Our placerconsiders the actual shapes of the bare dies and can resolve the rectangular chipplacement problem on a rectilinear region with various layout styles (such as chiparray or full custom). Finally, the placement results of some benchmark test circuitsare presented which demonstrate that our MCM placer is certainly effective.