A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step.pdf

A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A fundamental step in VLSI physical design A

2. Xplace: An Extremely Fast and Extensible
Global Placement Framework
Lixin Liu,BangqiFu, Martin D.F. Wong, Evangeline F.Y. Young
CSE Department
The Chinese University of Hong Kong

3. Global Placement Problem
A fundamental step in VLSI physical design
•Highly affect the circuit’s PPA
Modern circuits contain millions of standard cells
•Highly increase the computational complexity of GP
•Bring huge challenges to the leading-edge global placers

4. Global Placement Problem
[1] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, et al., “ePlace-MS: Electrostatics-
based placement for mixed-size circuits,” IEEE TCAD 2015
Objective:
•Minimize the total HPWL of all the nets
•Satisfy the cell density constraint
Analytical Global Placement:
•A smooth approximation of HPWL
•A density penalty

5. GPU-accelerated Global Placers
•Rapid development of GPU’s computational power
•GPU acceleration becomes an important direction
Recently, DREAMPlace[1]
•Implemented the approach of ePlace[2] on GPU
•Produced the SOTA solution quality and performance
[1] Y. Lin, Z. Jiang, J. Gu, W. Li, S. Dhar, H. Ren, B. Khailany, and D. Z. Pan, “DREAMPlace: Deep learning toolkit-enabled GPU acceleration for
modern VLSI placement,” IEEE TCAD 2020
[2] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, et al., “ePlace-MS: Electrostatics-
based placement for mixed-size circuits,” IEEE TCAD 2015
https://assets.nvidia.partners/images/png/nvidia-geforce-rtx-3090.png
https://www.nvidia.com/en-in/data-center/a100/
It is a big challenge to further improve on DREAMPlace’s
performance.

6. Proposed Framework: Xplace

7. Operator-Level Optimization
1. Wirelength Operator Combination (OC)
Observation:BoththeHPWLfunctionand
thestableWAwirelengthfunctionneedthe
minandmaxcellpositionsinanet.
Stable WA wirelength
HPWL function
Method:combiningthethreeoperatorswith
heavywirelength-relatedworkload,WA
wirelength,WAgradientandHPWL,into
oneoperator
Result:avoidredundantcomputationofthe
minandmaxfunction

8. Operator-Level Optimization
2. Density Operator Extraction (OE)
Overflowratioanddensitycomputation:
�
??????:targetdensity,�
??????:bin??????’scelldensity,??????
??????and??????
??????denotetheareaforbin??????andcell??????,

9. Operator-Level Optimization
Overflowratioanddensitycomputation:
�
??????:targetdensity,�
??????:bin??????’scelldensity,??????
??????and??????
??????denotetheareaforbin??????andcell??????,
Need to insert filler cells inside the electrostatic system [1]
??????: the set of cells, ??????
????????????: the set of fillers, ෪�
??????: bin ??????’s total density (incl. filler density)
�
????????????,??????: Bin ??????’s filler density
2. Density Operator Extraction (OE)
[1] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, et al., “ePlace-MS: Electrostatics-
based placement for mixed-size circuits,” IEEE TCAD 2015

10. Operator-Level Optimization
Overflowratioanddensitycomputation:
�
??????:targetdensity,�
??????:bin??????’scelldensity,??????
??????and??????
??????denotetheareaforbin??????andcell??????,
Need to insert filler cells inside the electrostatic system [1]
Matrix form of the total density map. ෩�,�,�
????????????∈ℝ
��
, �is the grid size
2. Density Operator Extraction (OE)
[1] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, et al., “ePlace-MS: Electrostatics-
based placement for mixed-size circuits,” IEEE TCAD 2015

11. Operator-Level Optimization
Observation:Boththecalculationof??????????????????�
andtotaldensitymap෩�needthecelldensity
map�.
Method:commonsub-operator�extraction,
computethecelldensitymap�andthefiller
densitymap�
????????????separately
2. Density Operator Extraction (OE)

12. Operator-Level Optimization
Result:reducethetotalcomputationtime
ofthecelldensitymap�.
2. Density Operator Extraction (OE)
Observation:Boththecalculationof??????????????????�
andtotaldensitymap෩�needthecelldensity
map�.

13. Operator-Level Optimization
3. Operator Reduction (OR)
Observation:
•Thenumberofforwardoperatorsarealmostthesameasthatinthebackward
•Invokingtheheavyautogradenginewillalmostdoublethenumberofoperators
andbringlargekernellaunchingoverheadonCPU
Method:
•Avoidinvokingtheheavyautogradengine
•DirectlyderivethenumericalsolutionsoftheWL/densitygrad
•Assignaweightedaccumulatedgradienttoeachcell
Result:Reducethetotalkernellaunchingtime

14. Operator-Level Optimization
3. Operator Reduction (OR)
OtherMethods:
•Usein-placeoperatorsasmuchaspossible
•Avoidredundantcopying
•Reordertheoperatorsthatneedsynctotheendoftheexecutionqueue
•ReducethefrequencyofinterruptingtheGPUpipeline

15. Operator-Level Optimization
4. Operator Skipping (OS)
Observation:
•Theratio??????=
??????|∇??????
�,�|
|∇��
�,�|
isultra-smallintheearlyplacementstage
Method:
•When??????<0.01∧(????????????????????????<100),thedensitygradoperatorwillonlybeexecuted
onceper20iterations
Result:
•Skipsomedensitygradcalculationinearlyplacementstage

16. Placement-Stage-Aware Parameters Scheduling
[1] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, et al., “ePlace-MS: Electrostatics-
based placement for mixed-size circuits,” IEEE TCAD 2015
Precondition matrix of is applied to accelerate convergence [1]
We introduce the precondition weighted ratio &#3627409172;= ∈[0,1]to measure the
placement stage
??????
??????: the number of nets connecting cell ??????, ??????
??????the area of cell ??????

17. Placement-Stage-Aware Parameters Scheduling
Precondition weighted ratio &#3627409172;= ∈[0,1]
ISPD 2005 / adaptec1
0.95
0.5
0.05
&#3627409172;<0.05wirelength-dominated and cells are driven
to the position with minimum wirelength
0.05<&#3627409172;<0.95cells are spreading over the whole
map and the overlap ratio significantly decreases
&#3627409172;>0.95cells are forced to a final position with
minimum local penalty

18. Placement-Stage-Aware Parameters Scheduling
Precondition weighted ratio &#3627409172;= ∈[0,1]
To fully exploit the optimization space
ISPD 2005 / adaptec1
0.95
0.5
0.05

19. Extending the Framework via Neural Enhancement
[1] Z. Li, N. B. Kovachki, K. Azizzadenesheli, B. Liu,K. Bhattacharya, A. M. Stuart, and A. Anandkumar, “Fourier neural operator for parametric
partial differential equations,” in Proc. ICLR, 2021.
The architecture of the fourierneural operators [1]
How to solve a 2D PDE problem by deep learning?
Many PDEs can be solved by Fourier transform.
Image-to-image networks -> Solve PDE in spatial domain conv
2D Fourier-Neural-Operator (FNO) [1] -> Solve PDE in frequency domain conv

20. Extending the Framework via Neural Enhancement
Image-to-image networks -> Solve PDE in spatial domain conv
2D Fourier-Neural-Operator (FNO) [1] -> Solve PDE in frequency domain conv
[1] Z. Li, N. B. Kovachki, K. Azizzadenesheli, B. Liu,K. Bhattacharya, A. M. Stuart, and A. Anandkumar, “Fourier neural operator for parametric
partial differential equations,” in Proc. ICLR, 2021.
How to solve a 2D PDE problem by deep learning?
Electron Distribution??????-> 2D Density map &#3627408439;of placement
Electric Field ∇&#3627409171;
&#3627408485;,∇&#3627409171;
&#3627408486;-> moving force on x and y-axis
Density Map
Poisson'sEquation
Many PDEs can be solved by Fourier transform.
Electric Field

21. Extending the Framework via Neural Enhancement
Input ??????={&#3627408439;;&#3627408448;
&#3627408485;;&#3627408448;
&#3627408486;}
Density map &#3627408439;
&#3627408448;
&#3627408485;&#3627408485;,&#3627408486;=
&#3627408485;
&#3627408459;
&#3627408448;
&#3627408486;&#3627408485;,&#3627408486;=
&#3627408486;
&#3627408460;
&#3627408459;,&#3627408460;are the map sizes
: linear transform, : FFT, : IFFT
??????&#3627408438;: fully-connected layer, &#3627408447;: low-pass-filter
Input transform:
Output transform:
Relative L2 Loss:

22. Extending the Framework via Neural Enhancement
Model Training Data Collection
1.ISPD 2005 contest benchmarks with their respective macros
2.Standard cells are randomlygenerated at a starting position
3.Pushed cells all over the map with only the density objective &#3627408439;(??????)
4.The density map and electric fields are used as training data and labels
Why train the model in low-resolution data
1.The resolution of the input maps will not affect the convolution results
2.Low frequency components describe the global information
3.Improve the adaptability of the model and speedup inference

23. Extending the Framework via Neural Enhancement
How to apply the nn-predicted density gradient
Smooth function:
Total gradient:

24. Experimental Results
Validation on Contest Benchmarks
ISPD 2005 ISPD 2015

25. Experimental Results
Ablation Studies of the Operator-Level Optimization Techniques

26. Experimental Results
Neural-Enhanced Performance

27. Conclusions and Future Works
Conclusions
We develop Xplace, a new, fast and extensible GPU accelerated GP framework built
on top of PyTorch, to consider factors at operator-level optimization.
•Efficiency: Xplaceachieves around 3x speedup per GP iterwith better quality
compared to DREAMPlace
•Extensiblity: we plug into Xplacea novel Fourier neural network and illustrate a
possibility of adopting neural guidance in analytical global placement
Future Works
•Handling additional constraints in placement like routability and fence regions

28. Q&A