VLSI Design Algorithms
- Introduction to digital design cycle and physical design context
- Brief review of physical design stages, partitioning, chip planning, placement, and routing
- Design styles: full-custom, cell-based (macrocell, standard cell) and array-based design styles (MPGA, FPGA, structured ASIC), comparing design styles, applications and physical design issues
- Review of VLSI design and layout design
- Integrated circuits fabrication, design rules and design for manufacturability (DFM)
- Review of graph theory (hypergraphs, multigraph, clique, cut edge), Review of algorithm design, algorithm complexity, NP-Completeness
- Graph algorithms for physical design, (shortest path, minimum spanning tree, Steiner minimum tree, ),
Data structures for physical design
- Partitioning: problem definition, considerations, objective functions, constraints, classification of partitioning algorithms
- Partitioning: problem definition, considerations, objective functions, constraints, classification of partitioning algorithmsCluster growth, Kernighan-Lin algorithm, Fiduccia-Mattheyses algorithm
- Multi-level partitioning, Multi-FPGA partitioning
- Chip planning: Floorplanning, pin assignment, power planning
- Chip planning: Floorplanning, pin assignment, power planning
- Placement: problem definition, considerations, objective functions, constraints, classification of placement algorithms, placement in different design styles
- Global placement and detailed placement,
Global placement algorithms: Min-cut, analytical, force-directed
- Global placement algorithms: Simulated annealing, tabu search, modern placement algorithms
- Detailed placement algorithms and legalization
- Routing: problem definition (global routing vs. detailed routing), considerations, objective functions, constraints, classification of global routing algorithms, routing in different design styles, graphs for global routing
- Net ordering, rip-up and reroute, maze routing algorithms
- Detailed routing, problem definition, considerations, constraints, constraint graphs, channel and switch box, channel-less standard cell routing
- Detailed routing algorithms
- Specialized routing, clock routing, basic concepts and algorithms, non-tree clock routing