Sham Chiu Wing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 107-113). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.1 / Chapter 1.2 --- Progress on the Problem --- p.2 / Chapter 1.3 --- Our Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.5 / Chapter 2 --- Preliminaries --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.1.1 --- The Role of Floorplanning --- p.6 / Chapter 2.1.2 --- Wirelength Estimation --- p.7 / Chapter 2.1.3 --- Different Types of Floorplan --- p.8 / Chapter 2.2 --- Representations of Floorplan --- p.10 / Chapter 2.2.1 --- Polish Expressions --- p.10 / Chapter 2.2.2 --- Sequence Pair --- p.11 / Chapter 2.2.3 --- Bounded-Sliceline Grid (BSG) Structure --- p.13 / Chapter 2.2.4 --- O-Tree --- p.14 / Chapter 2.2.5 --- B*-Tree --- p.16 / Chapter 2.2.6 --- Corner Block List --- p.18 / Chapter 2.2.7 --- Twin Binary Tree --- p.19 / Chapter 2.2.8 --- Comparisons between Different Representations --- p.20 / Chapter 2.3 --- Algorithms of Floorplan Design --- p.20 / Chapter 2.3.1 --- Constraint Based Floorplanning --- p.21 / Chapter 2.3.2 --- Integer Programming Based Floorplanning --- p.21 / Chapter 2.3.3 --- Neural Learning Based Floorplanning --- p.22 / Chapter 2.3.4 --- Rectangular Dualization --- p.22 / Chapter 2.3.5 --- Simulated Annealing --- p.23 / Chapter 2.3.6 --- Genetic Algorithm --- p.23 / Chapter 2.4 --- Summary --- p.24 / Chapter 3 --- Literature Review on Interconnect-Driven Floorplanning --- p.25 / Chapter 3.1 --- Introduction --- p.25 / Chapter 3.2 --- Simulated Annealing Approach --- p.25 / Chapter 3.2.1 --- """Pepper - A Timing Driven Early Floorplanner""" --- p.25 / Chapter 3.2.2 --- """A Timing Driven Block Placer Based on Sequence Pair Model""" --- p.26 / Chapter 3.2.3 --- """Integrated Floorplanning and Interconnect Planning""" --- p.27 / Chapter 3.2.4 --- """Interconnect Driven Floorplanning with Fast Global Wiring Planning and Optimization""" --- p.27 / Chapter 3.3 --- Genetic Algorithm Approach --- p.28 / Chapter 3.3.1 --- "“Timing Influenced General-cell Genetic Floorplanning""" --- p.28 / Chapter 3.4 --- Force Directed Approach --- p.29 / Chapter 3.4.1 --- """Timing Influenced Force Directed Floorplanning""" --- p.29 / Chapter 3.5 --- Congestion Planning --- p.30 / Chapter 3.5.1 --- """On the Behavior of Congestion Minimization During Placement""" --- p.30 / Chapter 3.5.2 --- """Congestion Minimization During Placement""" --- p.31 / Chapter 3.5.3 --- "“Estimating Routing Congestion Using Probabilistic Anal- ysis""" --- p.31 / Chapter 3.6 --- Buffer Planning --- p.32 / Chapter 3.6.1 --- """Buffer Block Planning for Interconnect Driven Floor- planning""" --- p.32 / Chapter 3.6.2 --- """Routability Driven Repeater Block Planning for Interconnect- centric Floorplanning""" --- p.33 / Chapter 3.6.3 --- """Provably Good Global Buffering Using an Available Block Plan""" --- p.34 / Chapter 3.6.4 --- "“Planning Buffer Locations by Network Flows""" --- p.34 / Chapter 3.6.5 --- """A Practical Methodology for Early Buffer and Wire Re- source Allocation""" --- p.35 / Chapter 3.7 --- Summary --- p.36 / Chapter 4 --- Floorplanner with Fixed Buffer Planning [34] --- p.37 / Chapter 4.1 --- Introduction --- p.37 / Chapter 4.2 --- Overview of the Floorplanner --- p.38 / Chapter 4.3 --- Congestion Model --- p.38 / Chapter 4.3.1 --- Construction of Grid Structure --- p.39 / Chapter 4.3.2 --- Counting the Number of Routes at a Grid --- p.40 / Chapter 4.3.3 --- Buffer Location Computation --- p.41 / Chapter 4.3.4 --- Counting Routes with Blocked Grids --- p.42 / Chapter 4.3.5 --- Computing the Probability of Net Crossing --- p.43 / Chapter 4.4 --- Time Complexity --- p.44 / Chapter 4.5 --- Simulated Annealing --- p.45 / Chapter 4.6 --- Wirelength Estimation --- p.46 / Chapter 4.6.1 --- Center-to-center Estimation --- p.47 / Chapter 4.6.2 --- Corner-to-corner Estimation --- p.47 / Chapter 4.6.3 --- Intersection-to-intersection Estimation --- p.48 / Chapter 4.7 --- Multi-pin Nets Handling --- p.49 / Chapter 4.8 --- Experimental Results --- p.50 / Chapter 4.9 --- Summary --- p.51 / Chapter 5 --- Floorplanner with Flexible Buffer Planning [35] --- p.53 / Chapter 5.1 --- Introduction --- p.53 / Chapter 5.2 --- Overview of the Floorplanner --- p.54 / Chapter 5.3 --- Congestion Model --- p.55 / Chapter 5.3.1 --- Probabilistic Model with Variable Interval Buffer Inser- tion Constraint --- p.57 / Chapter 5.3.2 --- Time Complexity --- p.61 / Chapter 5.4 --- Buffer Planning --- p.62 / Chapter 5.4.1 --- Estimation of Buffer Usage --- p.62 / Chapter 5.4.2 --- Estimation of Buffer Resources --- p.69 / Chapter 5.5 --- Two-phases Simulated Annealing --- p.70 / Chapter 5.6 --- Wirelength Estimation --- p.72 / Chapter 5.7 --- Multi-pin Nets Handling --- p.73 / Chapter 5.8 --- Experimental Results --- p.73 / Chapter 5.9 --- Remarks --- p.76 / Chapter 5.10 --- Summary --- p.76 / Chapter 6 --- Global Router --- p.77 / Chapter 6.1 --- Introduction --- p.77 / Chapter 6.2 --- Overview of the Global Router --- p.77 / Chapter 6.3 --- Buffer Insertion Constraint and Congestion Constraint --- p.78 / Chapter 6.4 --- Multi-pin Nets Handling --- p.79 / Chapter 6.5 --- Routing Methodology --- p.79 / Chapter 6.6 --- Implementation --- p.80 / Chapter 6.7 --- Summary --- p.86 / Chapter 7 --- Interconnect-Driven Floorplanning by Alternative Packings --- p.87 / Chapter 7.1 --- Introduction --- p.87 / Chapter 7.2 --- Overview of the Method --- p.87 / Chapter 7.3 --- Searching Alternative Packings --- p.89 / Chapter 7.3.1 --- Rectangular Supermodules in Sequence Pair --- p.89 / Chapter 7.3.2 --- Finding rearrangable module sets --- p.90 / Chapter 7.3.3 --- Alternative Sequence Pairs --- p.94 / Chapter 7.4 --- Implementation --- p.97 / Chapter 7.4.1 --- Re-calculation of Interconnect Cost --- p.98 / Chapter 7.4.2 --- Cost Function --- p.101 / Chapter 7.4.3 --- Time Complexity --- p.101 / Chapter 7.5 --- Experimental Results --- p.101 / Chapter 7.6 --- Summary --- p.103 / Chapter 8 --- Conclusion --- p.105 / Bibliography --- p.107
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_323810 |
| Date | January 2002 |
| Contributors | Sham, Chiu Wing., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | print, xiii, 113 leaves : ill. ; 30 cm. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0026 seconds