完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Chang, YC | en_US |
dc.contributor.author | Chang, YW | en_US |
dc.contributor.author | Wu, GM | en_US |
dc.contributor.author | Wu, SW | en_US |
dc.date.accessioned | 2014-12-08T15:27:04Z | - |
dc.date.available | 2014-12-08T15:27:04Z | - |
dc.date.issued | 2000 | en_US |
dc.identifier.isbn | 0-7803-6315-9 | en_US |
dc.identifier.issn | 0738-100X | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/19279 | - |
dc.description.abstract | We present in this paper an efficient, flexible, and effective data structure, B*-trees, for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules. | en_US |
dc.language.iso | en_US | en_US |
dc.title | B*-trees: A new representation for non-slicing floorplans | en_US |
dc.type | Proceedings Paper | en_US |
dc.identifier.journal | 37TH DESIGN AUTOMATION CONFERENCE, PROCEEDINGS 2000 | en_US |
dc.citation.spage | 458 | en_US |
dc.citation.epage | 463 | en_US |
dc.contributor.department | 資訊工程學系 | zh_TW |
dc.contributor.department | Department of Computer Science | en_US |
dc.identifier.wosnumber | WOS:000166739300085 | - |
顯示於類別: | 會議論文 |