Lecture 12Review and Sample Exam Questions.PPT

ASIC/SOC 2000, Lei He, Dr. Lei He Lecture 12Review and Sample Exam Questions Partitioning and Clustering Formulations: min-cut, min ratio cut, two-way partition and N-way partitioning Kernighan and Lin Algorithm Fiduccia and Mattheyses Algorithm Simulated annealing algorithm Lawler’s Labeling Algorithm Overview of multi-level partitioning Floorplanning Stockmeyer algorithm Dynamic programming to decide optimal orientation for slicing floorplanning (i.e., tree for slicing floorplanning is given) Simulated annealing algorithm to find slicing floorplanning Name and explain at least one data structure for non-slicing floorplanning Placement Simulated Annealing Timberwolf package [JSSC-85, DAC-86] Dragon (multi-level placement) [ICCAD-00] Partitioning-Based Placement Capo [DAC-00] Fengshui [DAC-2001] Analytical Placement Gordian (Multi-level placement) [TCAD-91] FastPlace [ISPD-04] Able to outline Pro’s and Con’s of all above algorithms Able to outline at least two algorithms Power and Thermal Modeling Power Components Dynamic power (f * s * C * Vdd**2) f: clock frequency S: switching possibility Short circuit power Leakage power = subthreshold + gate tunneling Power trends Relative significance between power components Which one gains importance in scaled technology and future system Design freedoms to reduce each power component with respect to performance constraints Power and Thermal Modeling Duality between electrical and thermal Thermal time constant is much bigger Interdependency between leakage and temperature Interconnect Modeling Capacitance characteristics and table based capacitance model Capacitance is a local effect Inductance characteristics and table based inductance model Inductance is a long-range effect Partial inductance (PEEC) is independent of current return path Full RCLM model and normalized RCLM model Interconnect Delay Model Elmore delay model and Elmore delay calculation for RC tree Definition of moments and