標題: 以B*樹處理邊界條件限制下的擺置問題之研究
Placement with Boundary Constraints Using B*-trees
作者: 衣懷恩
Huai-En Yi
張耀文
Yao-Wen Chang
資訊科學與工程研究所
關鍵字: 擺置;B*樹;邊界條件限制;placement;B*-tree;Boundary Constraint
公開日期: 2000
摘要: 在這篇論文中,我們研究了在邊界條件限制下的擺置問題,並利用B*樹的表示方法,針對非切割平面結構(non-slicing structure)的結構發展出一simulated annealing演算法。B*樹的表示方法已經被證明是一有彈性且有效率的表示方法,它利用二元樹的結構有效地表達出幾何位置的資訊。利用限定那些有邊界條件限制的模組維持在B*樹中特定的位置,就可以產生一棵適當的B*樹來得到一合理的擺置方式(feasible placement),以使有邊界條件限制的模組都被放置在邊界旁。實驗結果顯示,和利用sequence-pair表示法的方式比較,我們的演算法可以得出比較好的結果。
In this thesis, we study the placement problem with boundary constraints and develop a simulated annealing based algorithm using the B*-tree representation for non-slicing structure. The B*-tree has been shown a flexible and efficient representation conveying geometric information well in the binary tree structure. By restricting boundary-constrained modules in some particular positions in a B*-tree, an appropriate B*-tree is generated to get a feasible placement with all its boundary-constrained modules being placed along the boundaries. The experimental results show that our algorithm can obtain superior outcomes in contrast to the method using the sequence-pair representation.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT890394105
http://hdl.handle.net/11536/67012
Appears in Collections:Thesis