1_Introduction

– Mixed-size (large macro blocks and small standard cells) – Optimality study shows that placement still a bottleneck – Not even to mention performance driven, and coupled with buffering, interconnect optimizations, and so on (all you name)
– Capo: Based on recursive min-cut (UCLA-UMich) – Dragon: Recursive min-cut + SA refinement at each level (NWU-UCLA) – mPL: multi-level placer (UCLA)
There is significant room for improvement in placement algorithms: existing algorithms are 50-150% away from optimal!
2011-2-22
17
2011-2-22
18
VLSI Design Cycle
System Specification
Functional Design X=(AB*CD)+(A+D)+(A(B+C)) Logic Design Y=(A(B+C))+AC+D+A(BC+D))
Circuit Design
2011-2-22
14
Physical Design Automation Interlock
Automation Techniques Graph algorithms Graph algorithms mathematical programming Shortest path Mathematical programming Greedy algorithm VLSI Physical Design Partition Placement Routing
The most important thing often is to find the right problem formulation
2011-2-22
15
Basic Components In VLSI Circuits
Pad Metal1 Via Metal2
• Devices
– Transistors – Logic gates and cells – Function blocks
9
2011-2-22
10
2011-2-22
11
Course Reader
• Recommended text books
– Wang, Chang, and Cheng (Ed.), Electronic Design Automation: Synthesis, Verification, and Test, Morgan Kaufmann, 2009. – Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, 1999. – S. M. Sait and H. Youssef, VLSI Physical Design Automation: Theory and Practice, World Scientific, 1999. – T. H. Cormen, C. E. Leiserson, R. L. Rivest, “Introduction to Algorithms”, MIT Press, 2003 (2nd edition) (optional)
Manual
System Specification
Chip
Automation
Large number of devices Optimization requirements for high performance Time-to-market competition Power (and other) constraints
• More new physical and manufacturing effects pop up
– Crosstalk noise, … – OPC (manufacturability), etc.
• More vertical integration needed • Physical design is the KEY linking step between higher level planning/optimization and lower level modeling
2011-2-22 13
Course Outline
• • • • • • • • Introduction Partitioning Floorplanning Placement Global Routing Detailed Routing Clock and Power Routing Emerging topics
Why Physical Design is still HOT?
• Many existing solutions are still very suboptimal
– E.g., placement
• Interconnect dominates
– No physical layout, no accurate interconnect
2011-2-22
19
VLSI Design Cycle (cont.)
Physical Design
Fabrication
Packaging
2011-2-22
20
2011-2-22
21
Physical Design Cycle
2011-2-22
22
History of Physical Design
2011-2-22 26
2011-2-22
27
2011-2-22
28
2011-2-22
29
2011-2-22
30
2011-2-22
31
Structured ASICs (hot topics nowadays) are essentially gate array
2011-2-22 32
• Born in early 60’s (board layout) • Passed teenage in 70’s (standard cell place and route) • Entered early adulthood in 80’s (over-the-cell routing) • Declared dead in late 80’s !!! • Found alive and kicking in 90’s • Physical Design (PD) has become a dominant force in overall design cycle,
Data Path PLA I/O
• Interconnects
– – – – Local signals Global signals Clock signals Power/ground nets
ROM/ RAM
A/D Converter
Random logic
2011-2-22
16
VLSI Design Cycle
– thanks to the deep submicron scaling – expand vertically with logic synthesis and interconnect optimization, analysis…. => Design closure!
2011-2-22 23
• Selected papers from the literature.
2011-2-22
12
Physical Design Related Conferences/Journals
Important Conferences: ⎯ ACM/IEEE Design Automation Conference (DAC) ⎯ IEEE/ACM Int'l Conference on Computer-Aided Design (ICCAD) ⎯ ACM Int'l Symposium on Physical Design (ISPD) ⎯ ACM/IEEE Asia and South Pacific Design Automation Conf. (ASP-DAC) ⎯ ACM/IEEE Design, Automation, and Test in Europe (DATE) ⎯ IEEE Int'l Conference on Computer Design (ICCD) ⎯ IEEE Int'l Symposium on Circuits and Systems (ISCAS) ⎯ IEEE-TSA VLSI Design, Automation and Test (VLSI-DAT) ⎯ Many more, e.g., GLSVLSI, ISLPED, ISQED, SOCC, VLSI, VLSI Design/CAD Symposium/Taiwan Important Journals: ⎯ IEEE Transactions on Computer-Aided Design (TCAD) ⎯ ACM Transactions on Design Automation of Electronic Systems (TODAES) ⎯ IEEE Transactions on VLSI Systems (TVLSI) ⎯ IEEE Transactions on Computers (TC) ⎯ INTEGRATION: The VLSI Journal ⎯ IEE Proceedings