1、Task 1091.001: Highly Scalable Placement by Multilevel Optimization,Task Leaders: Jason Cong (UCLA CS) and Tony Chan (UCLA Math) Students with Graduation Dates: Michalis Romesis (UCLA CS, March 2005 -graduated) Kenton Sze (UCLA Math, July 2006 - graduated) Min Xie (UCLA CS, September 2006 - graduate
2、d) Guojie Luo (UCLA CS, September 2010) Research Staff: Joe Shinnerl, UCLA CS,2018/10/14,UCLA VLSICAD LAB,2,Industrial Liaisons,Patrick McGuinness, Freescale Semiconductor, Inc. Natesan Venkateswaran, IBM Corporation Amit Chowdhary, Intel Corporation,2018/10/14,UCLA VLSICAD LAB,3,Task Description an
3、d Anticipated Result,Highly scalable multilevel, multiheuristic placement algorithms that address the critical placement needs of nanometer designs: scalability multi-constraint optimization - timing, routability, power, manufacturability, etc. support of mixed-sized placement and incremental design
4、. Quantitative study of the optimality and scalability of placement algorithms Construction of synthetic benchmarks with known optima to identify the deficiencies of existing methods Our goal is to achieve one-process-generation benefit through innovation of physical-design technologies, especially
5、placement.,2018/10/14,UCLA VLSICAD LAB,4,Task Deliverables,Report on new placement benchmarks with known optimal or near optimal solutions for all major objectives and constraints. Scalability and optimization studies on existing placement techniques (Completed 3-Nov-2003) Experiments and reports on
6、 the applicability of integrated AMG-based weighted aggregation and weighted interpolation. Improvement measured on both PEKO examples and industrial examples from SRC member companies (Completed 1-Jun-2004) Experiments and reports on multiheuristic, multilevel relaxation and the scalable incorporat
7、ion of complex constraints into the enhanced multilevel framework. Improvement measured on both PEKO and industrial examples (Completed 1-Jun-2005) A highly scalable placement tool that (i) supports multi-constraint optimization, mixed-sized placement, and incremental design and (ii) produces best-o
8、f-class results for both PEKO and industrial examples from SRC member companies (Completed 1-Jun-2006) Final report summarizing research accomplishments and future direction (Planned-Oct-31, 2006),2018/10/14,UCLA VLSICAD LAB,5,Accomplishments in the Past Year,Improvements in mPL for routing density
9、control Best quality, ISPD 2006 contest Thermal-Driven Placement Heterogeneous Placement,2018/10/14,UCLA VLSICAD LAB,6,Relative Wirelength,year,2000,2001,2002,2003,2004,UNIFORM CELL SIZE,NON-UNIFORM CELL SIZE,A Brief History of mPL,2005,2006,mPL 5.0Multilevel force directedMixed-size capability,mPL
10、6.0Enhanced Routability handling,mPL 1.0 ICCAD00ESC ClusteringGoto relaxation,mPL 1.1FC clusteringPartitioning added to legalization,mPL 2.0RDFL relaxationPrimal-dual netlist pruning,mPL 3.0 ICCAD03QRS relaxationAMG interpolationMultiple V cycles,mPL 4.0Improved DPBacktracking V cycle,2018/10/14,UCL
11、A VLSICAD LAB,7,mPL: Generalized Force-Directed Placement,Use of accurate objective functions Bertsekas, 82, Naylor et al, 01Optimization-based bin-density constraint formulationIterative Uzawa solverMultilevel for better runtime and wirelength,is a generalized force,2018/10/14,UCLA VLSICAD LAB,8,Ac
12、complishments in the Past Year,Improvements in mPL for routing density control Best quality, ISPD 2006 contest Thermal-Driven Placement Heterogeneous Placement,2018/10/14,UCLA VLSICAD LAB,9,Core Engine for Density Control,Overall scheme One V cycle with comparable quality Minimum perturbation in the
13、 last stages of GFD Significant speed up without losing solution quality Routing density handling Residual density in each bin Even distribution of dummy density into bins Cell area inflation for better convergence,GFD with Density Control,Minimun perturbation,2018/10/14,UCLA VLSICAD LAB,10,Macro Sp
14、reading,Need area density below target value Nam, ISPD06 Target distance between neighboring macros: target density Spreading represented as objective,W,H,w,w1,w2,A1,A2,fij,x,Hij,dxi and dyi : perturbation fxij and fyij : piece-wise linear function,2018/10/14,UCLA VLSICAD LAB,11,Experiment Results o
15、n ISPD06,mPL6 produces the best solution quality using ISPD06 routability-driven metric,Demonstration of mPL6,http:/cadlab.cs.ucla.edu/cpmo/videos/mPL6-density.wmv,2018/10/14,UCLA VLSICAD LAB,12,2018/10/14,UCLA VLSICAD LAB,13,Accomplishments in the Past Year,Improvements in mPL core engine for mixed
16、-size global placement Thermal-Driven Placement Heterogeneous Placement,2018/10/14,UCLA VLSICAD LAB,14,Motivation,High power density due to technology scaling Problems caused by high temperature Hot spots become more harmful Higher temperature Higher leakage power More heat Previously negligible eff
17、ects become first-order effects Difficult estimation for power, timing, etc,2018/10/14,UCLA VLSICAD LAB,15,Thermal Model,One layer mesh to model the substrate j (Ti - Tj) Cxy + (Ti Tsink) Cz = Pi Cxy, Cz are the thermal conductance for the substrate and the heat sink Solved by Fast DCT Solve T from
18、CT = P, given C and P Diagonalize C = T is the discrete cosine matrix is a diagonal matrix T = -1-1 P,2018/10/14,UCLA VLSICAD LAB,16,Formulation & Solution,Implement i(x) and ti(x) with filler cells and “filler power” without area Tdes is a given by userSolved by Uzawa AlgorithmAs additional thermal
19、-aware GFD following a WL-driven V-Cycle,2018/10/14,UCLA VLSICAD LAB,17,Experiment Results on IBM-FastPlace,Quality improvementTeven is the ideal temperature with the same total power Max. on-chip temperature: Tinit after Step 1 Tfinal = Tdes after Step More than 90% quality improvement within 5% WL
20、 increase,2018/10/14,UCLA VLSICAD LAB,18,Accomplishments in the Past Year,Improvements in mPL for routing density control 1st quality, ISPD 2006 contest Thermal-Driven Placement Heterogeneous Placement,2018/10/14,UCLA VLSICAD LAB,19,Motivation,Need for placement on array type chips with pre-fabricat
21、ed resources FPGA Structured ASIC Need for heterogeneous capability Memory, DSP, etc Block on sites of the same type,2018/10/14,UCLA VLSICAD LAB,20,Related Work,Academia VPR Betz & Rose 97, PATH Kong 02, SPCD Chen & Cong 04,05, PPFF Maidee et al, 03, CAPRI Gopalakrishnan et al, 06 Most comparisons t
22、o out-dated tools No heterogeneous capability Industry Quartus II Altera Corp., ISE Xilinx Inc. Proprietary chips only Techniques not publicly documented,2018/10/14,UCLA VLSICAD LAB,21,Heterogeneous Placement by mPL-H,First analytical placer for heterogeneous placement Framework based on mPL6 Chan e
23、t al, 05Multiple layered placement One logical layer for each resource Forbidden regions blocked by obstacles Uniform wirelength computation Filler cells on each layer,DSP,M-RAM,LAB,Demonstration of mPL-H,http:/cadlab.cs.ucla.edu/cpmo/videos/mPL-H.wmv,2018/10/14,UCLA VLSICAD LAB,22,2018/10/14,UCLA V
24、LSICAD LAB,23,Experiment Setting,Quartus_map,Verilog netlist,Quartus_fitter,mPL-H,Clustered .vqm netlist,Quartus_router,Chip type,Stratix Description,.xml,.qsf placement,2018/10/14,UCLA VLSICAD LAB,24,Wirelength Comparison,WL still important for architecture evaluation mPL-H is 3% better in HPWL, an
25、d 2% better in routed WL than Quartus II v5.0,2018/10/14,UCLA VLSICAD LAB,25,Runtime Comparison,mPL-H can be 2X faster than Quartus II v5.0 when the circuit becomes sufficiently large,2018/10/14,UCLA VLSICAD LAB,26,Overall Accomplishments Over the Funding Period,34% reduction in WL over 3 years One
26、technology generation advancement,2018/10/14,UCLA VLSICAD LAB,27,Technology Transfer in 2006,Discussions at conferences and workshops ASPDAC 2006, Yokohama, Japan ISPD 2006, San Jose, USA DAC 2006, San Francisco, USA Benchmark Releases (PEKO-MS) http:/cadlab.cs.ucla.edu/pubbenchmPL release: http:/ca
27、dlab.cs.ucla.edu/src_686_mpl/,2018/10/14,UCLA VLSICAD LAB,28,Software Download Record,PEKO/PEKU 2002 now More than 360 downloads SRC member companies Cadence, IBM, Intel, Mentor Graphics,etc. NON-SRC member companies Synopsys, Magma, Monterey Design, etc. Universities CMU, Michigan, MIT, UC Berkeley
28、, UCSD, etc., mPL 2001 now More than 480 downloads SRC member companies Cadence, Intel, Mentor Graphics,etc. NON-SRC member companies Synopsys, Magma, Intrinsity, Oasys, etc. Universities CMU, Michigan, Stanford, UCSD, Natl Taiwan U., etc.,2018/10/14,UCLA VLSICAD LAB,29,Publications in 2006,Conferen
29、ce papers ASPDAC 2006: J. Cong, M. Xie, “A Robust Detailed Placement for Mixed-size IC Designs.” ISPD 2006: T. F. Chan, J. Cong, J. Shinnerl, K. Sze and M. Xie, “mPL6: Enhanced Multilevel Mixed-size Placement.” Thesis Kenton Sze, “Multilevel Optimization for VLSI Circuit Placement.” Min Xie, “Constraint-Driven Large Scale Circuit Placement Algorithms.”,2018/10/14,UCLA VLSICAD LAB,30,Room for Further Improvement?,“Swirls” are difficult to correct with localized refinement,mPL4,mPL5,
