Title :
Multilevel floorplanning/placement for large-scale modules using B*-trees
Author :
Lee, Hsun-Cheng ; Chang, Yao-Wen ; Hsu, Jer-Ming ; Yang, Hannah H.
Author_Institution :
Synopsis Inc., Taipei, Taiwan
Abstract :
We present in this paper a multilevel floorplanning/placement framework based on the B*-tree representation, called MB*-tree, to handle the floorplanning and packing for large-scale building modules. The MB*-tree adopts a two-stage technique, clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity, and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B*-tree for them. The declustering stage iteratively ungroup a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB*-tree preserves the geometric relations among modules during declustering, which makes the MB*-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB*-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, MB*-tree scales very well as the circuit size increases.
Keywords :
circuit layout CAD; circuit optimisation; integrated circuit layout; modules; network topology; tree data structures; B*-tree representation; Lagrangian relaxation; MB*-tree; area utilization; building module; clustered module; clustering stage; cost metric; data structure; declustering stage; geometric relation; large-scale module; module connectivity; multilevel floorplanning; multilevel placement framework; silicon area; simulated annealing scheme; Algorithm design and analysis; Application specific integrated circuits; Buildings; Computer applications; Data structures; Design optimization; Large-scale systems; Permission; Routing; Silicon;
Conference_Titel :
Design Automation Conference, 2003. Proceedings
Print_ISBN :
1-58113-688-9
DOI :
10.1109/DAC.2003.1219130