IP Library › Granted Patent US 12,248,745
Granted Patent B2
US 12,248,745 · App. 18/395,251 · Granted Mar 11, 2025

Generating integrated circuit placements using neural networks

Inventors: Anna Darling Goldie (San Francisco, CA); Azalia Mirhoseini (Mountain View, CA); Ebrahim Songhori (San Jose, CA); Wenjie Jiang (Mountain View, CA); Shen Wang (Sunnyvale, CA); Roger David Carpenter (San Francisco, CA); Young-Joon Lee (San Jose, CA); Mustafa Nazim Yazgan (Cupertino, CA); Chian-min Richard Ho (Palo Alto, CA); Quoc V. Le (Sunnyvale, CA); James Laudon (Madison, WI); Jeffrey Adgate Dean (Palo Alto, CA); Kavya Srinivasa Setty (Sunnyvale, CA); Omkar Pathak (Mountain View, CA)
Assignee: Google LLC
G06F30/392G06F30/398G06N3/08
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,248,745
App. No.
18/395,251
Granted
Mar 11, 2025
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating a computer chip placement. One of the methods includes obtaining netlist data for a computer chip; and generating a computer chip placement, comprising placing a respective macro node at each time step in a sequence comprising a plurality of time steps, the placing comprising, for each time step: generating an input representation for the time step; processing the input representation using a node placement neural network having a plurality of network parameters, wherein the node placement neural network is configured to process the input representation in accordance with current values of the network parameters to generate a score distribution over a plurality of positions on the surface of the computer chip; and assigning the macro node to be placed at the time step to a position from the plurality of positions using the score distribution.

Claims (58)

1. A method of training a node placement neural network that comprises:

an encoder neural network that is configured to, at each of a plurality of time steps, receive an input representation comprising data representing a current state of a placement of a netlist of nodes on a surface of an integrated circuit chip as of the time step and process the input representation to generate an encoder output, and

a policy neural network configured to, at each of the plurality of time steps, receive an encoded representation generated from the encoder output generated by the encoder neural network and process the encoded representation to generate a score distribution over a plurality of positions on the surface of the integrated circuit chip, the method comprising:

obtaining supervised training data comprising:

a plurality of training input representations, each training input representation representing a respective placement of a respective netlist of nodes, and

for each training input representation, a respective target value of a reward function that measures a quality of the respective placement of the respective netlist of nodes; and

training at least the encoder neural network on the plurality of training input representations using the target values of the reward function through supervised learning;

after the training through supervised learning:

receiving a new netlist of nodes; and

training the node placement neural network on the new netlist of nodes through reinforcement learning.

2. The method of claim 1 , wherein training the node placement neural network through reinforcement learning comprises training the policy neural network through reinforcement learning to generate score distributions that result in placements for the new netlist of nodes that maximize the reward function.

3. The method of claim 2 , wherein training the policy neural network through reinforcement learning comprises holding values of parameters of the encoder neural network fixed during the training of the policy neural network through reinforcement learning.

4. The method of claim 1 , further comprising:

after training through reinforcement learning, generating an integrated circuit placement for the new netlist data using the node placement neural network, comprising placing a respective node from the new netlist data at each of a plurality of time steps using score distributions generated by the node placement neural network.

5. The method of claim 1 , wherein the reward function includes a wire length term that measures a wire length of wires on the surface of the integrated circuit chip.

6. The method of claim 1 , wherein the reward function includes a congestion term that measures congestion on the surface of the integrated circuit chip.

7. The method of claim 1 , wherein the reward function includes a timing term that measures a timing performance of the integrated circuit chip.

8. The method of claim 1 , further comprising:

generating the supervised training data, comprising:

obtaining data specifying a training accelerator netlist;

generating a plurality of placements for the training accelerator netlist using a different policy neural network; and

determining a respective value of the reward function for each of the plurality of placements for the training accelerator netlist.

9. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations for training a node placement neural network that comprises:

an encoder neural network that is configured to, at each of a plurality of time steps, receive an input representation comprising data representing a current state of a placement of a netlist of nodes on a surface of an integrated circuit chip as of the time step and process the input representation to generate an encoder output, and

a policy neural network configured to, at each of the plurality of time steps, receive an encoded representation generated from the encoder output generated by the encoder neural network and process the encoded representation to generate a score distribution over a plurality of positions on the surface of the integrated circuit chip, the method comprising:

obtaining supervised training data comprising:

a plurality of training input representations, each training input representation representing a respective placement of a respective netlist of nodes, and

for each training input representation, a respective target value of a reward function that measures a quality of the respective placement of the respective netlist of nodes; and

training at least the encoder neural network on the plurality of training input representations using the target values of the reward function through supervised learning;

after the training through supervised learning:

receiving a new netlist of nodes, and

training the node placement neural network on the new netlist of nodes through reinforcement learning.

10. The system of claim 9 , wherein training the node placement neural network through reinforcement learning comprises training the policy neural network through reinforcement learning to generate score distributions that result in placements for the new netlist of nodes that maximize the reward function.

11. The system of claim 10 , wherein training the policy neural network through reinforcement learning comprises holding values of parameters of the encoder neural network fixed during the training of the policy neural network through reinforcement learning.

12. The system of claim 9 , the operations further comprising:

after training through reinforcement learning, generating an integrated circuit placement for the new netlist data using the node placement neural network, comprising placing a respective node from the new netlist data at each of a plurality of time steps using score distributions generated by the node placement neural network.

13. The system of claim 9 , wherein the reward function includes a wire length term that measures a wire length of wires on the surface of the integrated circuit chip.

14. The system of claim 9 , wherein the reward function includes a congestion term that measures congestion on the surface of the integrated circuit chip.

15. The system of claim 9 , wherein the reward function includes a timing term that measures a timing performance of the integrated circuit chip.

16. The system of claim 9 , the operations further comprising:

generating the supervised training data, comprising:

obtaining data specifying a training accelerator netlist;

generating a plurality of placements for the training accelerator netlist using a different policy neural network; and

determining a respective value of the reward function for each of the plurality of placements for the training accelerator netlist.

17. One or more non-transitory computer-readable storage media storing instructions that when executed by the one or more computers cause the one or more computers to perform operations for training a node placement neural network that comprises:

an encoder neural network that is configured to, at each of a plurality of time steps, receive an input representation comprising data representing a current state of a placement of a netlist of nodes on a surface of an integrated circuit chip as of the time step and process the input representation to generate an encoder output, and

a policy neural network configured to, at each of the plurality of time steps, receive an encoded representation generated from the encoder output generated by the encoder neural network and process the encoded representation to generate a score distribution over a plurality of positions on the surface of the integrated circuit chip, the method comprising:

obtaining supervised training data comprising:

a plurality of training input representations, each training input representation representing a respective placement of a respective netlist of nodes, and

for each training input representation, a respective target value of a reward function that measures a quality of the respective placement of the respective netlist of nodes; and

training at least the encoder neural network on the plurality of training input representations using the target values of the reward function through supervised learning;

after the training through supervised learning:

receiving a new netlist of nodes, and

training the node placement neural network on the new netlist of nodes through reinforcement learning.

18. The non-transitory computer-readable storage media of claim 17 , wherein training the node placement neural network through reinforcement learning comprises training the policy neural network through reinforcement learning to generate score distributions that result in placements for the new netlist of nodes that maximize the reward function.

19. The non-transitory computer-readable storage media of claim 18 , wherein training the policy neural network through reinforcement learning comprises holding values of parameters of the encoder neural network fixed during the training of the policy neural network through reinforcement learning.

20. The non-transitory computer-readable storage media of claim 17 , the operations further comprising:

after training through reinforcement learning, generating an integrated circuit placement for the new netlist data using the node placement neural network, comprising placing a respective node from the new netlist data at each of a plurality of time steps using score distributions generated by the node placement neural network.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 3, 2024
From: GOLDIE, ANNA DARLING; MIRHOSEINI, AZALIA; SONGHORI, EBRAHIM; JIANG, WENJIE; WANG, SHEN; CARPENTER, ROGER DAVID; LEE, YOUNG-JOON; YAZGAN, MUSTAFA NAZIM; HO, CHIAN-MIN RICHARD; LE, QUOC V.; LAUDON, JAMES; DEAN, JEFFREY ADGATE; SRINIVASA SETTY, KAVYA; PATHAK, OMKAR
To: GOOGLE LLC
Reel/Frame 067305/0440 →
Continuity (5)
Continuation 18082392 · Dec 15, 2022
Continuation 17555085 · Dec 17, 2021
Division 17238128 · Apr 22, 2021
Provisional Application 63014021 · Apr 22, 2020
Related Publication 20240249058A1 · Jul 25, 2024
References Cited (57)
US 6301693B1 · Naylor et al. · 2001 [cited by applicant]
US 8302052B2 · Lee et al. · 2012 [cited by applicant]
US 8589855B1 · Ward · 2013 [cited by applicant]
US 10699043B2 · Ho et al. · 2020 [cited by applicant]
US 20070067748A1 · Amit et al. · 2007 [cited by applicant]
US 20150067625A1 · Ward · 2015 [cited by applicant]
US 20150286766A1 · Singh et al. · 2015 [cited by applicant]
US 20180225817A1 · Yu et al. · 2018 [cited by applicant]
US 20230252215A1 · Zhang · 2023 [cited by examiner]
DE 102019124928 · 2020 [cited by applicant]
JP H03184173 · 1991 [cited by applicant]
Addanki et al., “Placeto: Learning generalizable device placement algorithms for distributed machine learning,” CoRR, Submitted on Jun. 20, 2019, arXiv:1906.08879, 15 pages. [cited by applicant]
Agnihotri et al., “Recursive bisection placement: Feng shui 5.0 implementation details,” Proceedings of the International Symposium on Physical Design, Apr. 2005, pp. 230-232. [cited by applicant]
Aykanat et al., “A fast neural-network algorithm for VLSI cell placement,” Neural Networks, Dec. 1998, 11(9):1671-1684. [cited by applicant]
Brenner et al., “Bonnplace: Placement of leading-edge chips by advanced combinatorial algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Sep. 2008, 27(9):1607-1620. [cited by applicant]
Breuer, “A class of min-cut placement algorithms,” Proceedings of the 14th Design Automation Conference, Jan. 1977, pp. 284-290. [cited by applicant]
Chang et al., “VLSI Circuit Placement with Rectilinear Modules using Three-Layer Force-Directed Self-Organizing Maps,” Institute of Electrical and Electronics Engineers, Sep. 1997, 8(5):1049-1064. [cited by applicant]
Chen et al., “A high-quality mixed-size analytical placer considering preplaced blocks and density constraints,” Institute of Electrical and Electronics Engineers, Jul. 2006, pp. 1228-1240. [cited by applicant]
Chen et al., “NTU-place3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Jul. 2008,… [cited by applicant]
Cheng et al., “Module placement based on resistive network optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984, 3(3):218-225. [cited by applicant]
Cheng et al., “RePlAce: Advancing solution quality and routability validation in global placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Sep. 2019, 38(9):1717-1730. [cited by applicant]
Fiduccia et al., “A linear-time heuristic for improving network partitions,” 19th Design Automation Conference, 1982, pp. 241-247. [cited by applicant]
Gilbert et al., “Steiner minimal trees,” SIAM Journal Applied Mathematics, 1968, 16(1), 29 pages. [cited by applicant]
Goldie et al., “Placement Optimization with Deep Reinforcement Learning,” Proceedings of the 2020 International Symposium on Physical Design, Mar. 2020, pp. 3-7. [cited by applicant]
Hsu et al., “TSV-aware analytical placement for 3D IC designs,” 48th ACM Design Automation Conference, Jun. 2011, pp. 664-669. [cited by applicant]
Hu et al., “Multilevel fixed-point-addition-based VLSI placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Aug. 2005, 24(8): 1188-1203. [cited by applicant]
Huang et al., “Routability-driven macro placement with embedded CNN-based prediction model,” Design, Automation & Test in Europe Conference & Exhibition, May 2019, 6 pages. [cited by applicant]
International Preliminary Report on Patentability in International Appln. No. PCT/US2021/028713, mailed on Nov. 3, 2022, 11 pages. [cited by applicant]
International Search Report and Written Opinion in International Appln. No. PCT/US2021/028713, mailed on Aug. 19, 2021, 19 pages. [cited by applicant]
Kahng et al., “Architecture and details of a high quality, large-scale analytical placer,” IEEE/ACM International Conference on Computer-Aided Design, Dec. 2005, 8 pages. [cited by applicant]
Karypis et al., “A hypergraph partitioning package,” hMETIS, Jan. 1998, 20 pages. [cited by applicant]
Kernighan, “A procedure for placement of standard-cell VLSI circuits,” Institute of Electrical and Electronics Engineers, Jan. 1985, 4(1):92-98. [cited by applicant]
Kim et al., “Complx: A competitive primal-dual lagrange optimization for global placement,” DACC '12: Proceedings of the 49th Annual Design Automation Conference, Jun. 2012, pp. 747-752. [cited by applicant]
Kim et al., “MAPLE: Multilevel adaptive placement for mixed-size designs,” Proceedings of the 2012 ACM International Symposium on International Symposium on Physical Design, Mar. 2012, pp. 193-200. [cited by applicant]
Kim et al., “SimPL: An effective placement algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Dec. 11,31(1):50-60. [cited by applicant]
Kirkpatrick et al., “Optimization by simulated annealing,” Science, May 1983, 220(4598):671-680. [cited by applicant]
Lin et al., “DREAMPlace: Deep learning toolkit-enabled GPU acceleration for modern VLSI placement,” Proceedings of the 56th Annual Design Automation Conference, 2019, 6 pages. [cited by applicant]
Lin et al., “POLAR: Placement based on novel rough legalization and refinement,” Proceedings of the International Conference on Computer-Aided Design, 2013, 6 pages. [cited by applicant]
Lu et al., “ePlace: Electrostatics-Based Placement Using Fast Fourier Transform and Nesterov's Method,” ACM Transactions on Embedded Computing Systems, Mar. 2015, 20(2):1-34. [cited by applicant]
Luo et al., “Dplace2.0: A stable and efficient analytical placement based on diffusion,” ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference, Jan. 2008, pp. 346-351. [cited by applicant]
Mirhoseini et al., “Chip Placement with Deep Reinforcement Learning” CoRR, Submitted on Apr. 22, 2020, arXiv:2004.10746, 15 pages. [cited by applicant]
Nazi et al., “GAP: Generalizable approximate graph partitioning framework” International Conference on Learning Representations, 2019, 7 pages. [cited by applicant]
Notice of Allowance in Japanese Appln. No. 2022-556215, mailed on Jun. 10, 2024, 6 pages (with English machine translation). [cited by applicant]
Obermeier et al., “Kraftwerk: a versatile placement approach” ISPD '05: Proceedings of the 2005 international symposium on Physical design, Apr. 2005, pp. 242-244. [cited by applicant]
Office Action in Indian Appln. No. 202227051091, mailed on Mar. 23, 2023, 6 pages (with English translation). [cited by applicant]
Office Action in Japanese Appln. No. 2022-556215, mailed on Dec. 11, 2023, 9 pages (with English translation). [cited by applicant]
Paliwal et al., “REGAL: Transfer learning for fast optimization of computation graph,” CoRR, Submitted on Feb. 10, 2020, arXiv:1905.02494v4, 24 pages. [cited by applicant]
Ren-Song et al., “PROUD: a sea-of-gates placement algorithm,” Institute of Electrical and Electronics Engineers, Jan. 1988, 13 pages. [cited by applicant]
Schulman et al., “Proximal policy optimization algorithms,” CoRR, Submitted on Aug. 28, 2017, arXiv:1707.06347v2, 12 pages. [cited by applicant]
Sechen et al., “Timber-Wolf 3.2: a new standard cell placement and global routing package,” IEEE Journal of Solid-Statecircuit, Apr. 1985, 20(2):510-522. [cited by applicant]
Shahookar et al., “VLSI cell placement techniques,” ACM Computing Surveys, Jun. 1991, 23(2):143-220. [cited by applicant]
Spinder et al., “Kraftwerk2—A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2008, 27(8):1398-1411. [cited by applicant]
Viswanathan et al., “PQL: Global placement via relaxed quadratic spreading and linearization,” DAC '07: Proceedings of the 44th annual Design Automation Conference, Jun. 2007, pp. 453-458. [cited by applicant]
Xie et al., “Routenet: Routability prediction for mixed-size designs using convolutional neural network,” 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Nov. 2018, 8 pages. [cited by applicant]
Zhang et al., “Link prediction based on graph neural networks,” NeurIPS, 2018, 11 pages. [cited by applicant]
Zhang et al., “Mapping and hierarchical self-organizing neural networks for VLSI placement,” IEEE Transactions on Neural Networks, Mar. 1997, 8(2):299-314. [cited by applicant]
Zhou et al., “GDP: Generalized device placement for dataflow graphs,” CoRR, Submitted on Sep. 28, 2019, arXiv:1910.01578, 11 pages. [cited by applicant]