10 dragon

Dragonfor ISPD2005 Contest: 

Dragon for ISPD2005 Contest Xiaojian Yang (Synplicity Inc.) Taraneh Taghavi Bo-Kyung Choi Maogang Wang Majid Sarrafzadeh Computer Science Department, UCLA

Outline: 

Outline Background Dragon work flow Modifications for the contest Summary

Background of Dragon: 

Background of Dragon History 2000: first version, wirelength driven 2001-2002: congestion driven 2002: timing driven 2003-2004: mixed size placement Basic algorithms for wirelength minimization Multilevel Partitioning: hMetis Simulated Annealing: cluster moves and cell moves

Background of Dragon (cont’d): 

Background of Dragon (cont’d) Support bookshelf formats One of the earliest (along with Capo and Feng Shui) Benchmark generation Target benchmarks (MCNC, IBM-PLACE1,2) High utilization (98% for IBM-PLACE1, 85-90% for IBM-PLACE2) Full core area available (no blockages) Mainly focus on pure standard-cell placement Small/Intermediate circuits (< 220K)

Background of Dragon (cont’d): 

Background of Dragon (cont’d) No. 1 in wirelength minimization until 2004 A target to compare in recent placement papers 2004: APlace, mPL4 outperformed Dragon, Capo was similar on IBM-PLACE2 (routability benchmarks) 2005: mPL5 outperformed Dragon on IBM-FastPlace benchmarks Limitations Runtime Unable to handle blockages Bad performance on PEKO

Dragon Flow: 

Dragon Flow Top-down recursive quadrisection (hMetis) Cluster Moves to improve global placement Cell moves to improve detailed placement

Modifications: 

Modifications Handling large size circuits Reduce memory usage: Removed congestion/timing data Reduce runtime Removed unnecessary annealing Fixed runtime problems Blockages aware placement Blockage aware partitioning Blockage aware cluster/cell move Legalization

Modifications (cont’d): 

Modifications (cont’d) Terminal Propagation Old: no terminal propagation. Focus on interconnects inside clusters. Cluster moves to improve external connections Current: terminal propagation with feedback mechanism

Modifications (cont’d): 

Modifications (cont’d) Low utilization design handling Packing Global placement area Use entire placement area with large partitioning tolerance None of them is a good enough solution Inherently a hard problem for min-cut placers

Modifications (cont’d): 

Modifications (cont’d) Mixed size placement: two-pass flow Global placement for both macros and standard-cells Macros legalized and fixed Second pass standard-cell placement

Summary: 

Summary Contest benchmarks require nontrivial changes on Dragon Scalability Blockage aware placement Handling low utilization circuits

Summary: 

Summary Contest benchmarks require nontrivial changes on Dragon Scalability Blockage aware placement Handling low utilization circuits Lack of quality improvements due to limited resources

Thanks to:: 

Thanks to: ISPD, IBM and Gi-Joon for this event!