Introduction

• VLSI design methodology
• Cell layout styles
• Criteria for layout optimization

• Introduction
  • Problem Description
  • The Taxonomy of Partitioning
  • Analysis of the Partitioning Problem
• Kernighan and Lin Partitioning Algorithm
  • Algorithm
  • Example
  • Time Complexity Analysis
  • Extensions of the Algorithm
• A Linear Time Heuristic for Partitioning
  • The Algorithm
  • Example
  • Time Complexity Analysis
• Improvement of Min-cut Algorithm for Partitioning
  • Lookahead Technique
  • Improving KLFM Algorithm by Clustering
  • Bisection Using a Derivative of KLFM
  • A Different Objective Function
• Multi-way Partioning
• Other Improvements of KL, FM Algorithms
• Simulated Annealing Based Approach for Partitioning
• Evolution Based Approach for Partitioning
• Greedy Algorithms for Graph Bisection
• Circuit Partitioning Using Neural Nets
  • Neural Net Model
  • Using Neural Nets for Circuit Partitioning : Graph Model
  • Using Neural Nets for Circuit partitioning : Net-Cut Model
  • Balancing the Partition
• Kodre's Partitioning Algorithm
  • Algorithm 1
  • Improvement of Algorithm 1
• Metric Allocation Methods
• Constructing Test Cases for Partitioning Heuristics

• Introduction
  • Classification of Placement Algorithms
  • Wire Length Estimates
• Simulated Annealing
  • Introduction
  • The Algorithm
  • Understanding the Operation of Simulated Annealing
  • TimberWolf 3.2
  • Recent Improvements in Simulated Annealing
    • The Effect of Various Probabilistic Acceptance Functions
    • Statistical control of annealing parameters
    • The Improved Annealing Algorithm in TimberWolfSC 4.2
• Force-directed Placement
  • Introduction
  • Force-Directed Placement Techniques
  • The Algorithm
  • Example
  • Goto's Placement Algorithm
  • Analysis
• Placement by Partitioning
  • Introduction
  • Breuer's Algorithms
  • Dunlop's Algorithm and Terminal Propagation
  • Quadrisection
• Numerical Optimization Techniques
  • The Eigenvalue Method
  • Gordian's techniques
  • Resistive Network Optimization
  • PROUD - Placement by Block Gauss-Seidel Optimization
  • ATLAS - A Technique for Layout Using Analytic Shapes
• Placement by the Genetic Algorithm
  • Genie - A Genetic Placement Algorithm
  • ESP - Evolution-Based Placement Algorithm
  • GASP - The genetic Algorithm for Standard Cell Placement

• Introduction
  • Slicing Floorplans and Slicing Trees
  • Skewed Slicing Tree
  • Balloting Sequence
  • Polish Expressions Representing the Slicing Tree.
• Graph Algorithms
  • Layout Equations
  • Solving the Layout Equations
  • Computing Dimensions to Satisfy Perimeter Constraints
  • Satisfying the Area Constraints
• The Min-cut Floorplanning Approach
• The Genetic Algorithm for Macro Cell Placement
  • Function Optimization Formulation
  • Chromosomal Representation
  • Bit-map Crossover Operator
  • Chromosomal Representation
  • Bit-map Crossover Operator
  • Bitmap Inversion Operator
  • Bit-map Mutation Operator
  • Simulation Results
• Simulated Annealing
• Analytical Approach to Floorplan Design Optimization
  • Mixed Integer Programming Model of Floorplanning
    • First Mixed Integer Programming Formulation
    • Flexible Modules in Integer Programming Formulation
    • Constraints on Interconnection Length
    • Constraints on Routability
    • Floorplanning with Routing Around Modules
    • Optimization of the Floorplan with the Given Topology
  • Solution Method for Mixed Integer Programming Formulation
    • An Algorithm for Solving the Floorplanning Problem
    • Covering Rectangles for the Partial Floorplan
    • Global Routing and Final Area Computation

• Introduction
• Maze Routing
• HAM: a hardware accelerator for multi-layer routing
• A minimum bend maze router
  • The alpha -beta routing algorithm
• Line-probe routers
• Rip-up and rerouting
• Channel Routers
  • Channel routing models
  • The left-edge algorithm
  • The dogleg router
  • Greedy channel router
  • YACR2: yet another channel router
  • Multi-layer channel routers
  • Extension of HV solutions to HVH models
  • Merging algorithm for three-layer channel routing
  • Chameleon: a multi-layer channel router
• Switchbox Routing
  • AI-based switchbox routing
  • Computational-geometry based switchbox routing
  • Rip-up and reroute-based routing
  • Simulated evolution for switchbox routing
  • A comparison of the switch box routers
  • Simulated evolution for switchbox routing
  • A comparison of the switch box routers
• Single-Layer Routing
  • The general river routing algorithm
  • Strait-typed river routing
• Global Routing
  • Global routing models
  • Iterative global routing algorithm
  • Spanning tree approach
  • Hierarchical global routing
    • The integer programming approach
    • The dynamic programming approach
  • Greedy global routers
  • Global routing for building block layout
• Minimum Via Topological Routing
  • Topological UVM routing
  • Topological CVM routing
• Specialized Routers
  • Power and ground routing
    • Planar routing of power/ground networks
    • Power/ground net sizing
  • Clock distribution schemes
• PC board routers
  • Heuristic routers
  • Grid-based routers
  • Gridless routers
  • Single-row routing
• Autorouters for Analog VLSI
  • Analog routing for standard-cell layout
  • Analog routing for macro-cell layout

• Interval Graph Formulation and the Consecutive Ones Property
  • Finding a Minimal Augmentation
  • Automated Gate Matrix Layout
  • Building a Minimal v.d.c Matrix Using a Greedy Heuristic
  • Generating a Gate Sequence from a v.d.g Matrix
  • Incorporating Globally-Oriented Criteria into the Column Selection Step
  • Generating B, Given a Predefined Upper Bound on the Size of the
    • Largest Dominant Clique
• Worst-case Performance of the Greedy Heuristics
  • Dynamic Programming Formulation
• Algorithms for Minimizing both n and p parts together
  • A Heuristic for Minimizing the Total Layout
  • An Algorithm That Uses Several Diffusion Elimination Rules
  • A Min-cut Algorithm Using Diffusion Elimination Rules

Field Programmable Gate Arrays