加速具邊界限制之定形配置設計

On Accelerating Slicing Floorplan Design with Boundary Constraints

林塗興(TuHxing Lin)

指導教授 ： 王廷基 ； 王廷基

中原大學/工學院/資訊工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100138

摘要

最近Young and Wong擴充以模擬退火法(Simulated-Annealing) 為基礎的Wong-Liu演算法(algorithm)來解決”具邊界限制之切開式(slicing)定形配置設計”的問題，Young-Wong演算法的主要概念，是藉由對正規化Polish表示式(normalized Polish expression)從右至左檢視一次，來決定在一個佈局(floorplan)裡所有模組(module)的邊界資訊(boundary information)。在仔細觀察Young-Wong演算法中用來產生新正規化Polish表示式的三種搬動(move)方式後，我們發現在新的正規化Polish表示式裡，極有可能只有一小部分模組的邊界資訊會改變，因此也只有這些模組的邊界資訊需要重新計算。針對此項發現，我們在這篇論文裡提出一些加快計算邊界資訊的新方法來改進Young-Wong演算法。理論的分析和實驗的結果都顯示我們的演算法能在較短的執行時間內產生和Young-Wong演算法完全相同的定形配置解。

關鍵字

加速 ； 邊界限制 ； 定形配置

並列摘要

Recently Young and Wong extended the well-known simulated annealing based Wong-Liu algorithm [6] to solve the problem of slicing floorplan design with boundary constraints. The main idea behind the Young-Wong algorithm [10] is to determine the boundary information of each module in a floorplan by traversing the corresponding normalized Polish expression from right to left once. By having carefully examined each of the three types of moves adopted by the Young-Wong algorithm for generating a new normalized Polish expression, we observe that it is very likely that only a fraction of modules might have their boundary information changed in the new normalized Polish expression, and hence only the boundary information for those modules needs to be re-computed. Based on the observation, we improve the Young-Wong algorithm by providing methods to accelerate the boundary information computation in this thesis. Both the theoretical analysis and experimental results indicate that our algorithm packs the modules as tightly as the Young-Wong algorithm but takes less run time.

並列關鍵字

boundary constraints ； accelerating ； slicing floorplan

參考文獻

[1] W. Dai and E. S. Kuh, “Simultaneous Floor Planning and Global Routing for Hierarchical Building-Block Layout,” IEEE Trans. on CAD, 1987, pp. 828-837.

[2] H. Murata and E. S. Kuh, “Sequence-Pair Based Placement Method for Hard/Soft/Pre-Placed Modules,” Proc. International symposium on Physical Design, 1998, 167-172.

[3] R. H. J. M. Otten, “Automatic Floorplan Design,” Proc. Design Automation Conference, 1982, pp. 261-267.

[4] R. H. J. M. Otten, “Efficient Floorplan Optimization,” Proc. International Conference on Computer Design, 1983, pp. 499-502.

[5] L. Stockmeyer, “Optimal Orientations of Cells in Slicing Floorplan Designs,” Information and Control, 1983, pp. 91-101.