Routability optimization with buffer planning in floorplan design.

Wong Wai-Chiu.Thesis (M.Phil.)--Chinese University of Hong Kong, 2002.Includes bibliographical references (leaves 94-101).Abstracts in English and Chinese.Abstract --- p.iiiAbstract in Chinese --- p.vAcknowledgements --- p.viChapter 1 --- Introduction --- p.1Chapter 1.1 --- Motivations --- p.2Chapter 1.2 --- Progress on Interconnect-driven Floorplanning --- p.4Chapter 1.2.1 --- Congestion Optimization --- p.4Chapter 1.2.2 --- Buffer Insertion --- p.5Chapter 1.3 --- Contributions --- p.6Chapter 1.4 --- Organization of this Thesis --- p.7Chapter 2 --- "VLSI Circuit Design, Physical Design Cycle and Floorplanning" --- p.8Chapter 2.1 --- VLSI Circuit Design Cycle --- p.9Chapter 2.2 --- Physical Design Cycle --- p.10Chapter 2.2.1 --- Circuit Partitioning --- p.10Chapter 2.2.2 --- Floorplanning and Placement --- p.11Chapter 2.2.3 --- Routing --- p.12Chapter 2.2.4 --- Compaction --- p.12Chapter 2.3 --- Introduction to Floorplanning --- p.13Chapter 2.4 --- Types of Floorplan --- p.14Chapter 2.5 --- Simulated Annealing --- p.15Chapter 2.6 --- Floorplan Representation --- p.16Chapter 2.6.1 --- Polish Expression --- p.17Chapter 2.6.2 --- Sequence Pair --- p.18Chapter 2.6.3 --- Twin Binary Tree --- p.20Chapter 2.6.4 --- Comparisons between Different Floorplan Representations --- p.21Chapter 2.7 --- Chapter Summary --- p.22Chapter 3 --- Interconnect Optimization in Floorplanning --- p.24Chapter 3.1 --- Routing Congestion Optimization --- p.25Chapter 3.2 --- Buffer Planning --- p.26Chapter 3.3 --- Wire Sizing --- p.28Chapter 3.4 --- Simultaneous Wire Sizing and Buffer Planning --- p.30Chapter 3.5 --- Literature Review on Interconnect-driven Floorplanning --- p.31Chapter 3.5.1 --- Congestion Optimization --- p.31Chapter 3.5.2 --- Buffer Insertion --- p.36Chapter 3.6 --- Chapter Summary --- p.40Chapter 4 --- Floorplanning with Congestion Optimization and Buffer Block Planning --- p.41Chapter 4.1 --- Floorplanner Overview --- p.42Chapter 4.1.1 --- Grid Structure and Blocked Grids --- p.44Chapter 4.1.2 --- Buffer Block Planning --- p.44Chapter 4.2 --- Elmore Delay Model --- p.46Chapter 4.2.1 --- Wire Sizing --- p.47Chapter 4.2.2 --- Buffer Insertion --- p.48Chapter 4.2.3 --- Simultaneous Buffer Insertion and Wire Sizing --- p.49Chapter 4.3 --- Dynamic Programming Approach for Buffer Planning and Wire Sizing --- p.49Chapter 4.4 --- Implementation of the Dynamic Programming Approach --- p.51Chapter 4.5 --- Lookup Table Construction --- p.53Chapter 4.6 --- Congestion Model --- p.55Chapter 4.7 --- Cost Function --- p.56Chapter 4.8 --- Algorithm --- p.56Chapter 4.9 --- Experimental Results --- p.57Chapter 4.9.1 --- Experimental Results on Simultaneous Buffer Insertion and Wire Sizing --- p.57Chapter 4.9.2 --- Experimental Results of using the Table Lookup Approach --- p.58Chapter 4.10 --- Chapter Summary --- p.60Chapter 5 --- Floorplanning with Flexible Buffer Planning and Routability Op- timization --- p.63Chapter 5.1 --- Floorplanner Overview --- p.64Chapter 5.1.1 --- Constraints in Buffer Locations --- p.64Chapter 5.2 --- Congestion Estimation --- p.66Chapter 5.3 --- Buffer Location Computation --- p.67Chapter 5.3.1 --- Feasible Locations for Buffer Insertion --- p.67Chapter 5.3.2 --- Cost of Grids for Buffer Insertion --- p.69Chapter 5.3.3 --- Dynamic Programming Approach for Selecting Buffer Lo- cation of a Net --- p.70Chapter 5.3.4 --- An Example --- p.70Chapter 5.4 --- Congestion Model --- p.72Chapter 5.4.1 --- Net-count Congestion Model --- p.72Chapter 5.4.2 --- Grid-count Congestion Model --- p.74Chapter 5.5 --- Buffer Location Bounds --- p.75Chapter 5.6 --- Net Grouping --- p.77Chapter 5.7 --- Cost Function --- p.79Chapter 5.8 --- Algorithm . --- p.79Chapter 5.9 --- Experimental Results --- p.79Chapter 5.9.1 --- Net Grouping Factor --- p.80Chapter 5.9.2 --- Experimental Results of our Floorplanner --- p.80Chapter 5.9.3 --- Comparison on Different Congestion Models --- p.82Chapter 5.10 --- Chapter Summary --- p.83Chapter 6 --- Conclusion --- p.86Chapter 6.1 --- Discussion --- p.87Chapter 6.2 --- Improvements --- p.88Chapter 6.2.1 --- Net Grouping and Ordering --- p.88Chapter 6.2.2 --- Congestion Modelling --- p.89Appendix --- p.90Chapter A --- Overview on VLSI Technology --- p.91Chapter A.l --- Moore's Law and Trends in VLSI --- p.91Chapter A.2 --- Scaling --- p.93Bibliography --- p.10