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

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

程仲勝(Jong-Sheng Cherng) ； 潘佳信(Chia-Hsin Pan)

《科學與工程技術期刊》 2卷4期 (2006/12) Pp. 45-52

https://doi.org/10.7117/JSET.200612.0045

摘要

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

關鍵字

實體設計 ； 平面規劃 ； 不確定模組 ； 群聚 ； 模擬退火

並列摘要

As the VLSI (very large scale integration)/SOC (system-on-a-chip) technology advances, it is becoming increasingly important for system designers to evaluate a chip area before backend physical design phase by effectively and efficiently floorplanning uncertain modules which have not been completely designed and have uncertain dimensions. Most of the previous research deals with evaluating chip area by considering only soft or hard, rather than uncertain, modules. In this paper, to evaluate the area of a chip of uncertain modules effectively and efficiently, a non-slicing floorplanning algorithm based on a clustering strategy is proposed. In this method, when given certain sets of different widths, heights and corresponding feasible probabilities for each uncertain module, a clustering strategy is applied to group modules to form fewer supermodules of a larger size. Then, the Corner Block List representation for a non-slicing floorplan is used to record the relative positions among supermodules, and the simulated annealing procedure is finally executed according to Corner Block List representation for obtaining a better solution. Experimental results show that a better area distribution graph can be obtained for each benchmark when compared to the slicing-based method; thus, the effectiveness of the proposed algorithm is demonstrated.

並列關鍵字

physical design ； floorplanning ； uncertain module ； clustering ； simulated annealing