以三維序列表示法為基礎之空間規劃演算法

A Spaceplan Algorithm Using Sequence-Triplet Representation

陳玟伶(Wen Ling Chen)

指導教授 ： 謝財明

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

https://doi.org/10.6840/cycu200100042

摘要

平面規劃(Floorplan)在超大型積體電路實體設計流程(VLSI Physical Design)中是相當重要的一個步驟，它的結果將會對晶片的效能造成很大的影響。

在本論文中，我們延伸平面規劃概念，並提出三維空間規劃問題。我們延伸被廣為使用的序列組(sequence pair)表示法來表示一空間規劃，稱之為三維序列組(sequence-triplet)，以便來處理三維空間規劃問題。

我們發展出以模擬退火法為基礎之演算法，同時將包含所有模組之體積及模組間連線長度最小化。實驗結果顯示我們的演算法不僅成功地將平面規劃問題推展至空間規劃，更能在一定時間內達到不錯的空間使用率，同時在加入連線考量時，體積及連線長度皆可得到很大的改善。

關鍵字

平面規劃 ； 序列組 ； 空間規劃 ； 三維序列組

並列摘要

Floorplan design is an important step in physical design of VLSI circuits. The result of the floorplan design will deeply influence performance of the chip.

In this thesis, we extended the concept of floorplan and proposed the spaceplan problem. An novel data structure, called the sequence triplet, which is an extension of the sequence pair widely used in the floorplan problem is used to deal with the 3D design problem. A simulated annealing based algorithm is proposed to minimize the volume and the total wire length among blocks.

The Experiment results show that we successfully extend the 2D floorplan problem to 3D spaceplan problem and achieve the good space untilization.

並列關鍵字

Spaceplan ； Floorplan ； Sequence triplet ； Sequence pair

參考文獻

[1] Kiarash Bazargan, Ryan Kastner and Majid Sarrafzadeh “3-D Floorplanning: Simulated Annealing and Greedy Placement Methods for Reconfigurable Computing Systems,” Rapid System Prototyping, 1999. IEEE International Workshop on 1999, Page(s): 38 –43

[3] K. Fujiyosi and H. Murata, “Arbitrary Convex and Concave Rectilinear Block Packing Using Sequence-Pair,” Proc. Intl. Symp. on Physical Design, pp. 103-110, 1999.

[4] P.-N. Guo, C.-K. Cheng and T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and Its Application,” Proc. Design Automation Conf., pp. 268-273, 1999.

[5] R. H. J. M. Otten, “ Efficient Floorplan Optimization,” Proc. Intl. Conf. on Computer Design, 1984.

[6] Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng, Jun Gu “A non-slicing floorplanning algorithm using corner block list topological representation,” IEEE APCCAS, pp. 833 –836, 2000.