Different Electronic Design Automation Eda Tools And Comparison.

Abstract

Chip floorplanning is the engineering task of designing the physical layout of a computer chip. Despite five decades of research¹, chip floorplanning has defied automation, requiring months of intense effort by physical design engineers to produce manufacturable layouts. Here we present a deep reinforcement learning approach to chip floorplanning. In under six hours, our method automatically generates chip floorplans that are superior or comparable to those produced by humans in all key metrics, including power consumption, performance and chip area. To achieve this, we pose chip floorplanning as a reinforcement learning problem, and develop an edge-based graph convolutional neural network architecture capable of learning rich and transferable representations of the chip. As a result, our method utilizes past experience to become better and faster at solving new instances of the problem, allowing chip design to be performed by artificial agents with more experience than any human designer. Our method was used to design the next generation of Google's artificial intelligence (AI) accelerators, and has the potential to save thousands of hours of human effort for each new generation. Finally, we believe that more powerful AI-designed hardware will fuel advances in AI, creating a symbiotic relationship between the two fields.

Data availability

The data supporting the findings of this study are available within the paper and the Extended Data.

Code availability

The code used to generate these data is available from the corresponding authors upon reasonable request.

References

1.
Markov, I. L., Hu, J. & Kim, M. Progress and challenges in VLSI placement research. Proc. IEEE 103, 1985–2003 (2015).

Article Google Scholar
2.
Tang, M. & Yao, X. A memetic algorithm for VLSI floorplanning. IEEE Trans. Syst. Man Cybern. B 37, 62–69 (2007).

Article Google Scholar
3.
Breuer, M. A. A class of min-cut placement algorithms. In Proc. 14th Design Automation Conference (DAC 1977) 284–290 (IEEE, 1977).
4.
Fiduccia, C. M. & Mattheyses, R. M. A linear-time heuristic for improving network partitions. In 19th Design Automation Conference 175–181 (IEEE, 1982).
5.
Roy, J. A., Papa, D. A. & Markov, I. L. in Modern Circuit Placement (eds Nam, G.-J. & Cong, J. J.) 97–133 (Springer, 2007).
6.
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).

ADS MathSciNet Article Google Scholar
7.
Sechen, C. M. & Sangiovanni-Vincentelli, A. L. TimberWolf3.2: a new standard cell placement and global routing package. In 23rd ACM/IEEE Design Automation Conference 432–439 (IEEE, 1986).
8.
Sarrafzadeh, M., Wang, M. & Yang, X. in Modern Placement Techniques 57–89 (Springer, 2003).
9.
Luo, T. & Pan, D. Z. DPlace2.0: a stable and efficient analytical placement based on diffusion. In 2008 Asia and South Pacific Design Automation Conference 346–351 (IEEE, 2008).
10.
Hu, B. & Marek-Sadowska, M. Multilevel fixed-point-addition-based VLSI placement. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 24, 1188–1203 (2005).

Article Google Scholar
11.
Viswanathan, N., Pan, M. & Chu, C. in Modern Circuit Placement (eds Nam, G.-J. & Cong, J. J.) 193–228 (Springer, 2007).
12.
Kim, M., Lee, D., Markov, I. L. & Sim, P. L. An effective placement algorithm. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 31, 50–60 (2012).

Article Google Scholar
13.
Lu, J. et al. ePlace: electrostatics-based placement using fast Fourier transform and Nesterov's Method. ACM Trans. Des. Autom. Electron. Syst. 20, 17 (2015).

ADS Article Google Scholar
14.
Cheng, C.-K., Kahng, A. B., Kang, I. & Wang, L. RePlAce: advancing solution quality and routability validation in global placement. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 38, 1717–1730 (2019).

Article Google Scholar
15.
Silver, D. et al. Mastering the game of Go without human knowledge. Nature 550, 354–359 (2017).

ADS Article Google Scholar
16.
Aslam, B., Amjad, F. & Zou, C. C. Optimal roadside units placement in urban areas for vehicular networks. In 2012 IEEE Symposium on Computers and Communications (ISCC) 000423–000429 (IEEE, 2012).
17.
Medlock, J. & Galvani, A. P. Optimizing influenza vaccine distribution. Science 325, 1705–1708 (2009).

ADS Article Google Scholar
18.
Cherniak, C., Mokhtarzada, Z., Rodriguez-Esteban, R. & Changizi, K. Global optimization of cerebral cortex layout. Proc. Natl Acad. Sci. USA 101, 1081–1086 (2004).

ADS Article Google Scholar
19.
Langford, J. & Zhang, T. The Epoch-Greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems Vol. 20, 817–824 (2008).
20.
Usunier, N., Synnaeve, G., Lin, Z. & Chintala, S. Episodic exploration for deep deterministic policies: an application to starcraft micromanagement tasks. In Proc. International Conference on Learning Representations (2017).
21.
Bello, I., Pham, H., Le, Q. V., Norouzi, M. & Bengio, S. Neural combinatorial optimization with reinforcement learning. Preprint at https://arxiv.org/abs/1611.09940 (2016).
22.
Mirhoseini, A. et al. Device placement optimization with reinforcement learning. In Proc. International Conference on Machine Learning 2430–2439 (PMLR, 2017).
23.
Mirhoseini, A. et al. A hierarchical model for device placement. In Proc. International Conference on Learning Representations (2018).
24.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A. & Klimov, O. Proximal policy optimization algorithms. Preprint at https://arxiv.org/abs/1707.06347 (2017).
25.
Obermeier, B., Ranke, H. & Johannes, F. M. Kraftwerk: a versatile placement approach. In Proc. 2005 International Symposium on Physical Design 242–244 (ACM, 2005).
26.
Spindler, P., Schlichtmann, U. & Johannes, F. M. Kraftwerk2 – a fast force-directed quadratic placement approach using an accurate net model. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 27, 1398–1411 (2008).

Article Google Scholar
27.
Viswanathan, N. et al. RQL: global placement via relaxed quadratic spreading and linearization. In Proc. Design Automation Conference 453–458 (ACM/IEEE, 2007).
28.
Ioffe, S. & Szegedy, C. Batch normalization: accelerating deep network training by reducing internal covariate shift. In Proc. 32nd International Conference on Machine Learning 448–456 (JMLR, 2015).
29.
Nair, V. & Hinton, G. E. Rectified linear units improve restricted Boltzmann machines. In Proc. International Conference on Machine Learning 807–814 (Omnipress, 2010).
30.
Zaruba, F. & Benini, L. The cost of application-class processing: energy and performance analysis of a Linux-ready 1.7-GHz 64-Bit RISC-V core in 22-nm FDSOI technology. IEEE Trans. Very Large Scale Integr. VLSI Syst. 27, 2629–2640 (2019).

Article Google Scholar
31.
RePlAce software – the OpenROAD project https://github.com/The-OpenROAD-Project/RePlAce (2020).
32.
Karypis, G. & Kumar, V. Hmetis: a hypergraph partitioning package http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview (1998).
33.
Alpert, C. J., Hagen, L. W. & Kahng, A. B. A hybrid multilevel/genetic approach for circuit partitioning. In Proc. APCCAS'96 – Asia Pacific Conference on 1012 Circuits and Systems 298–301 (IEEE, 1996).
34.
Caldwell, A. E., Kahng, A. B. & Markov, I. L. Improved algorithms for hypergraph 1014 bipartitioning. In Proc. 2000 Design Automation Conference 661–666 (IEEE, 2000).
35.
Chen, H. et al. An algebraic multigrid solver for analytical placement with layout 1017 based clustering. In Proc. 40th annual Design Automation Conference 794–799 (ACM, 2003); 10.1145/775832.776034.
36.
Alpert, C., Kahng, A., Nam, G.-J., Reda, S. & Villarrubia, P. A semi-persistent clustering technique for vlsi circuit placement. In Proc. 2005 International Symposium on Physical Design, 200–207 (ACM, 2005).
37.
Fogaça, M., Kahng, A. B., Reis, R. & Wang, L. Finding placement-relevant clusters with fast modularity-based clustering. In Proc. 24th Asia and South Pacific Design Automation Conference 569–576 (ACM, 2019); https://doi.org/10.1145/3287624.3287676.
38.
Fogaça, M. et al. On the superiority of modularity-based clustering for deter mining placement-relevant clusters. Integration 74, 32–44 (2020).

Article Google Scholar
39.
Kahng, A. B. Futures for partitioning in physical design (tutorial). In Proc. 1998 International Symposium on Physical Design 190–193 (ACM, 1998); https://doi.org/10.1145/274535.274563.
40.
Shahookar, K. & Mazumder, P. VLSI cell placement techniques. ACM Comput. Surv. 23, 143–220 (1991).

Article Google Scholar
41.
Caldwell, A. E., Kahng, A. B., Mantik, S., Markov, I. L. & Zelikovsky, A. On wirelength estimations for row-based placement. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 18, 1265–1278 (1999).

Article Google Scholar
42.
Kahng, A. B. & Xu, X. Accurate pseudo-constructive wirelength and congestion estimation. In Proc. 2003 International Workshop on System-Level Interconnect Prediction 61–68 (ACM, 2003); https://doi.org/10.1145/639929.639942.
43.
Kahng, A. B. & Reda, S. A tale of two nets: studies of wirelength progression in physical design. In Proc. 2006 International Workshop on System-Level Interconnect Prediction |17–24 (ACM, 2006); https://doi.org/10.1145/1117278.1117282.
44.
Kim, M.-C., Viswanathan, N., Alpert, C. J., Markov, I. L. & Ramji, S. MAPLE: Multilevel Adaptive Placement for Mixed-Size Designs. In Proc. 2012 ACM International Symposium on International Symposium on Physical Design 193–200 (ACM, 2012).
45.
Nazi, A., Hang, W., Goldie, A., Ravi, S. & Mirhoseini, A. GAP: generalizable approximate graph partitioning framework. In International Conference on Learning Representations Workshop (2019).
46.
Zhou, Y. et al. GDP: generalized device placement for dataflow graphs. Preprint at https://arxiv.org/abs/1910.01578 (2019).
47.
Zhang, M. & Chen, Y. Link prediction based on graph neural networks. In Proc. International Conference on Neural Information Processing 5171–5181 (Curran Associates Inc., 2018).
48.
Xie, Z. et al. RouteNet: routability prediction for mixed-size designs using convolutional neural network. In 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) 1–8 (IEEE, 2018).
49.
hMETIS – hypergraph and circuit partitioning manual http://glaros.dtc.umn.edu/gkhome/metis/hmetis/download.
50.
Dunlop, A. E. & Kernighan, B. W. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 4, 92–98 (1985).

Article Google Scholar
51.
Cheng C. K. & Kuh. E. S. Module placement based on resistive network optimization. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 3, 218–225 (1984).

Article Google Scholar
52.
Tsay, R.-S., Kuh, E. & Hsu, C.-P. Proud: a fast sea-of-gates placement algorithm. In Proc. Design Automation Conference 1988, 318–323 (IEEE, 1988).
53.
Agnihotri, A., Ono, S. & Madden, P. Recursive bisection placement: Feng Shui 5.0 implementation details. In Proc. International Symposium on Physical Design 230–232 (ACM, 2005).
54.
Alpert, C. et al. Analytical engines are unnecessary in top-down partitioning based placement. VLSI Des. 10, 99–116 (2002).

Article Google Scholar
55.
Kahng, A. B., Reda, S. & Wang, Q. Architecture and details of a high quality, large-scale analytical placer. In IEEE/ACM International Conference on Computer-Aided Design 2005 891–898 (IEEE, 2005).
56.
Kahng, A. B. & Wang, Q. An analytic placer for mixed-size placement and timing.driven placement. In IEEE/ACM International Conference on Computer Aided Design 2004 565–572 (IEEE, 2004).
57.
Kahng, A. B. & Wang, Q. Implementation and extensibility of an analytic placer. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 24, 734–747 (2005).

Article Google Scholar
58.
Chen, T.-C., Jiang, Z.-W., Hsu, T.-C., Chen, H.-C. & Chang, Y.-W. A High-quality mixed-size analytical placer considering preplaced blocks and density constraints. In Proc. 2006 IEEE/ACM International Conference on Computer-Aided Design 187–192 (ACM, 2006).
59.
Naylor, W., Donelly, R. & Sha, L. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. US Patent US6301693B1 (2001).
60.
Chen, T., Jiang, Z., Hsu, T., Chen, H. & Chang, Y. NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 27, 1228–1240 (2008).

Article Google Scholar
61.
Kim, M.-C. & Markov, I. L. ComPLx: a competitive primal-dual Lagrange optimization for global placement. In Design Automation Conference 2012 747– 755 (ACM, 2012).
62.
Brenner, U., Struzyna, M. & Vygen, J. BonnPlace: placement of leading-edge chips by advanced combinatorial algorithms. Trans. Comp.-Aided Des. Integ.Cir. Sys. 27, 1607–1620 (2008).

Article Google Scholar
63.
Lin, T., Chu, C., Shinnerl, J. R., Bustany, I. & Nedelchev, I. POLAR: placement based on novel rough legalization and refinement. In Proc. International Conference on Computer-Aided Design 357–362 (IEEE, 2013).
64.
Lu, J. et al. ePlace-MS: electrostatics-based placement for mixed-size circuits. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 34, 685–698 (2015).

Article Google Scholar
65.
Lu, J., Zhuang, H., Kang, I., Chen, P. & Cheng, C.-K. Eplace-3d: electrostatics based placement for 3d-ics. In International Symposium on Physical Design 11–18 (ACM, 2016).
66.
Lin, Y. et al. DREAMPlace: deep learning toolkit-enabled GPU acceleration for modern VLSI placement. In Design Automation Conference 1–6 (ACM/IEEE, 2019).
67.
Kahng, A. B. Machine learning applications in physical design: recent results and directions. In Proc. 2018 International Symposium on Physical Design 68–73 (ACM, 2018); https://doi.org/10.1145/3177540.3177554.
68.
Kahng, A. B. Reducing time and effort in ic implementation: a roadmap of challenges and solutions. In Proc. 55th Annual Design Automation Conference (ACM, 2018); https://doi.org/10.1145/3195970.3199854.
69.
Ajayi, T. et al. Toward an open-source digital flow: first learnings from the openroad project. In Proc. 56th Annual Design Automation Conference 2019 (ACM, 2019); https://doi.org/10.1145/3316781.3326334.
70.
Huang, Y. et al. Routability-driven macro placement with embedded CNN-based prediction model. In Design, Automation & Test in Europe Conference & Exhibition 180–185 (IEEE, 2019).
71.
Khalil, E., Dai, H., Zhang, Y., Dilkina, B. & Song, L. Learning combinatorial optimization algorithms over graphs. Adv. Neural Inf. Process Syst. 30, 6348–6358 (2017).

Google Scholar
72.
Zoph, B. & Le, Q. V. Neural architecture search with reinforcement learning. In Proc. International Conference on Learning Representations (2017).
73.
Addanki, R., Venkatakrishnan, S. B., Gupta, S., Mao, H. & Alizadeh, M. Learning generalizable device placement algorithms for distributed machine learning. Adv. Neural Inf. Process Syst. 32, 3981–3991 (2019).

Google Scholar
74.
Paliwal, A. et al. Reinforced genetic algorithm learning for optimizing computation graphs. In Proc. International Conference on Learning Representations (2020).
75.
Zhou, Y. et al. Transferable graph optimizers for ML compilers. Prepint at https://arxiv.org/abs/2010.12438 (2021).
76.
Barrett, T. D., Clements, W. R., Foerster, J. N. & Lvovsky, A. I. Exploratory combinatorial optimization with reinforcement learning. Preprint at https://arxiv.org/abs/1909.04063 (2020).
77.
Kipf, T. N. & Welling, M. Semi-supervised classification with graph convolutional networks. Prepint at https://arxiv.org/abs/1609.02907 (2016).

Download references

Acknowledgements

This project was a collaboration between Google Brain and the Google Chip Implementation and Infrastructure (CI2) Team. We thank M. Bellemare, C. Young, E. Chi, C. Stratakos, S. Roy, A. Yazdanbakhsh, N. Myung-Chul Kim, S. Agarwal, B. Li, S. Bae, A. Babu, M. Abadi, A. Salek, S. Bengio and D. Patterson for their help and support.

Author information

Author notes

These authors contributed equally: Azalia Mirhoseini, Anna Goldie

Affiliations

Google Research, Brain Team, Google, Mountain View, CA, USA

Azalia Mirhoseini, Anna Goldie, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Eric Johnson, Azade Nazi, Quoc V. Le, James Laudon & Jeff Dean
Google Chip Implementation and Infrastructure (CI2) Team, Google, Sunnyvale, CA, USA

Mustafa Yazgan, Young-Joon Lee, Omkar Pathak, Jiwoo Pak, Andy Tong, Kavya Srinivasa, Emre Tuncer, Richard Ho & Roger Carpenter
Computer Science Department, Stanford University, Stanford, CA, USA

Anna Goldie & William Hang

Contributions

A.G. and A.M. are co-first authors and the order of the names was determined by coin flip. M.Y., J.W.J., E.S., S.W. and Y.-J.L. were major contributors to this work. The following authors contributed to the overall evaluation and provided insights on physical design: E.J., O.P., A.N., J.P., A.T., K.S., W.H. and E.T. The following authors managed and advised on the project: Q.V.L., J.L., R.H., R.C. and J.D.

Corresponding authors

Correspondence to Azalia Mirhoseini or Anna Goldie.

Ethics declarations

Competing interests

The following US patents are related to this work: 'Generating integrated circuit floorplans using neural networks' (granted as US10699043) and 'Domain adaptive reinforcement learning approach to macro placement' (filed).

Additional information

Peer review information Nature thanks Jakob Foerster and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.

Publisher's note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Extended data figures and tables

Extended Data Fig. 1 Evaluation workflow for producing the results in Table 1.

We allow each method access to the same clustered netlist hypergraph. We use the same hyperparameters (to the extent possible) in all the methods. Once the placement is completed by each method (this includes the legalization step for RePlAce), we snap the macros to the power grids, freeze the macro locations and use a commercial EDA tool to place the standard cells and report the final results.

Extended Data Fig. 2 Zero-shot performance of Edge-GNN versus GCN (graph convolutional neural network)77.

The agent with an Edge-GNN architecture is more robust to over-fitting and yields higher-quality results, as measured by average zero-shot performance on the test blocks shown in Extended Data Fig. 1.

Extended Data Fig. 3 Generalization performance as a function of pre-training dataset size.

We pre-train the policy network on three different training datasets (the small dataset with 2 blocks is a subset of the medium one with 5 blocks, and the medium dataset is a subset of the large one with 20 blocks). For each policy, at various snapshots during pre-training we report its inference performance on an unseen test block. As the dataset size increases, both the quality of generated placements on the test block and the generalization performance of the policy improve. The policy trained on the largest dataset is most robust to over-fitting.

Extended Data Fig. 4 Visualization of Ariane placements.

Left, zero-shot placements from the pre-trained policy; right, placements from the fine-tuned policy. The zero-shot placements are generated at inference time on a previously unseen chip. The pre-trained policy network (with no fine-tuning) reserves a convex hull in the centre of the canvas in which standard cells can be placed, a behaviour that reduces wirelength and that emerges only after many hours of fine-tuning in the policy trained from scratch.

Extended Data Fig. 5 Visualization of a real TPU chip.

Human expert placements are shown on the left and results from our approach are shown on the right. The white area represents macros and the green area represents standard cells. The figures are intentionally blurred because the designs are proprietary. The wirelength for the human expert design is 57.07 m, whereas ours is 55.42 m. Furthermore, our method achieves these results in 6 h, whereas the manual baseline took several weeks.

Extended Data Table 1 Hyperparameters used for fine-tuning the RL agent

Full size table

Extended Data Table 2 Hyperparameters used for the FD algorithm that places standard cell clusters

Full size table

Extended Data Table 3 Hyperparameters used to generate standard cell clusters with hMETIS³²

Full size table

Extended Data Table 4 Effect of different cost trade-offs on the post-PlaceOpt performance of Block 1 in Table 1

Full size table

Extended Data Table 5 Sensitivity of results to the choice of random seed, as measured on a Ariane RISC-V block

Full size table

Extended Data Table 6 Performance of our method compared to SA

Full size table

About this article

Verify currency and authenticity via CrossMark

Cite this article

Mirhoseini, A., Goldie, A., Yazgan, M. et al. A graph placement methodology for fast chip design. Nature 594, 207–212 (2021). https://doi.org/10.1038/s41586-021-03544-w

Download citation

Received: 03 November 2020
Accepted: 13 April 2021
Published: 09 June 2021
Issue Date: 10 June 2021
DOI : https://doi.org/10.1038/s41586-021-03544-w

Comments

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.