以Corner Block List表示法處理植基於群聚策略之不確定模組平面規劃問題

A Clustering-Based Approach for Floorplanning of Uncertain Modules by Using Corner Block List Representation

隨著VLSI（very large scale integration）/ SOC（system-on-a-chip）的蓬勃發展，如何在電路模組面積及寬高維度皆不確定時，即尚未設計完成時，評估這些不確定模組在後端實體設計階段（physical design phase）所可能形成之晶片面積大小是相當重要的議題。對於絕大多數先前研究而言，只評估由具有固定面積甚至具有固定寬高之確定模組所形成之晶片面積，而對於不確定模組（uncertain module）的平面規劃問題則未有實驗探討。因此在本論文中我們提出一個植基於群聚（clustering）策略之不確定模組平面規劃演算法以便能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首先給定每一個模組幾組不同的寬與高及其相對應之可能機率， 接著採用群聚技巧將模組聚集起來形成一些面積較大但個數較少的組合模組（supermodules），最後以Corner Block List 表示法來記錄組合模組間相對位置關係並在其上執行模擬退火（simulated annealing）程序以求得面積最佳化的結果。由實驗結果得知，對於每個例子我們可以得出不確定模組所形成的最終晶片寬、高與其面積之機率分佈圖，藉此評估尚未設計完成之電路模組在未來所形成可能之晶片面積大小。