Generating interrelated path groups by using machine learning

Patent metadata

Field	Value
Publication number	US-10846453-B1
Application number	US-201916574923-A
Country	US
Kind code	B1
Filing date	Sep 18, 2019
Priority date	Sep 20, 2018
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

Techniques and systems for generating path groups for a set of violating timing path end-points in an integrated circuit (IC) design are described. Some embodiments can determine a set of attribute values for each violating timing path end-point in a set of violating timing path end-points. Next, the embodiments can use an unsupervised machine learning clustering technique to determine a set of clusters by using the attribute values. The embodiments can then generate a path group for each cluster, wherein the path group includes violating timing path end-points that belong to the cluster.

First claim

What is claimed is:

1. A non-transitory storage medium storing instructions, which when executed by a processor, cause the processor to perform operations for generating path groups for a set of violating timing path end-points in an integrated circuit (IC) design, the operations comprising:
determining a set of attribute values for each violating timing path end-point in a set of violating timing path end-points;
determining a distance matrix or an affinity matrix for the set of violating timing path end-points based on the set of attribute values for the set of violating timing path end-points, wherein at least one element in the distance matrix or the affinity matrix is based on a distance between two violating timing path end-points in a multidimensional attribute space;
using an unsupervised machine learning clustering technique to determine a set of clusters based on the distance matrix or the affinity matrix, wherein each violating timing path end-point is assigned to a cluster in the set of clusters; and
generating a path group for each cluster, wherein the path group includes violating timing path end-points that belong to the cluster.

2. The non-transitory storage medium of claim 1 , wherein the operations comprise optimizing the IC design by using the path groups.

3. The non-transitory storage medium of claim 2 , wherein the operations comprise assigning a weight to each path group based on a total negative slack of violating timing path end-points in the path group.

4. The non-transitory storage medium of claim 1 , wherein the set of attribute values includes a required delay value and a slack value.

5. The non-transitory storage medium of claim 4 , wherein the set of attribute values includes a group name, a head name, and a tail name.

6. The non-transitory storage medium of claim 1 , wherein the affinity matrix is determined by:
determining the distance matrix, wherein each element (i, j) in the distance matrix is a distance between a first violating timing path end-point corresponding to row i and a second violating timing path end-point corresponding to column j; and
determining the affinity matrix based on the distance matrix.

7. The non-transitory storage medium of claim 6 , wherein the distance between the first violating timing path end-point corresponding to row i and the second violating timing path end-point corresponding to column j is an Euclidean distance.

8. An apparatus, comprising:
a processor; and
a non-transitory storage medium storing instructions, which when executed by the processor, cause the processor to perform operations for generating path groups for a set of violating timing path end-points in an integrated circuit (IC) design, the operations comprising:
determining a set of attribute values for each violating timing path end-point in a set of violating timing path end-points;
determining a distance matrix or an affinity matrix for the set of violating timing path end-points based on the set of attribute values for the set of violating timing path end-points, wherein at least one element in the distance matrix or the affinity matrix is based on a distance between two violating timing path end-points in a multidimensional attribute space;
using an unsupervised machine learning clustering technique to determine a set of clusters based on the distance matrix or the affinity matrix, wherein each violating timing path end-point is assigned to a cluster in the set of clusters; and
generating a path group for each cluster, wherein the path group includes violating timing path end-points that belong to the cluster.

9. The apparatus of claim 8 , wherein the operations comprise optimizing the IC design by using the path groups.

10. The apparatus of claim 9 , wherein the operations comprise assigning a weight to each path group based on a total negative slack of violating timing path end-points in the path group.

11. The apparatus of claim 8 , wherein the set of attribute values includes a required delay value and a slack value.

12. The apparatus of claim 11 , wherein the set of attribute values includes a group name, a head name, and a tail name.

13. The apparatus of claim 8 , wherein the affinity matrix is determined by:
determining a distance matrix, wherein each element (i, j) in the distance matrix is a distance between a first violating timing path end-point corresponding to row i and a second violating timing path end-point corresponding to column j; and
determining the affinity matrix based on the distance matrix.

14. The apparatus of claim 13 , wherein the distance between the first violating timing path end-point corresponding to row i and the second violating timing path end-point corresponding to column j is an Euclidean distance.

15. A method for generating path groups for a set of violating timing path end-points in an integrated circuit (IC) design, the method comprising:
determining a set of attribute values for each violating timing path end-point in a set of violating timing path end-points;
determining, by a processor, a distance matrix or an affinity matrix for the set of violating timing path end-points based on the set of attribute values for the set of violating timing path end-points, wherein at least one element in the distance matrix or the affinity matrix is based on a distance between two violating timing path end-points in a multidimensional attribute space;
using an unsupervised machine learning clustering technique to determine a set of clusters based on the distance matrix or the affinity matrix, wherein each violating timing path end-point is assigned to a cluster in the set of clusters; and
generating a path group for each cluster, wherein the path group includes violating timing path end-points that belong to the cluster.

16. The method of claim 15 , wherein the method comprises optimizing the IC design by using the path groups.

17. The method of claim 16 , wherein the method comprises assigning a weight to each path group based on a total negative slack of violating timing path end-points in the path group.

18. The method of claim 15 , wherein the set of attribute values includes a required delay value and a slack value.

19. The method of claim 18 , wherein the set of attribute values includes a group name, a head name, and a tail name.

20. The method of claim 15 , wherein the affinity matrix is determined by:
determining a distance matrix, wherein each element (i, j) in the distance matrix is a distance between a first violating timing path end-point corresponding to row i and a second violating timing path end-point corresponding to column j; and
determining the affinity matrix based on the distance matrix.

Assignees

• Synopsys Inc

Inventors

• Castle David E

Classifications

• G06N20/00

  Machine learning · CPC title

• G06F30/394 Primary

  Routing (G06F30/396 takes precedence) · CPC title

• G06F30/27 Primary

  using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model · CPC title

• G06F2119/12

  Timing analysis or timing optimisation · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title