Method for partitioning of connected circuit components before placement in one or more integrated circuits
First Claim
1. A computer implemented method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, the method implemented by a computer and comprising the steps of:
- (a) assigning, by the computer, a connectivity cost to every pair of connected components;
(b) beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, placing, by the computer, the components in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost; and
,(c) traversing, by the computer, the cluster tree to partition the components into clusters.
6 Assignments
0 Petitions
Accused Products
Abstract
In a method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, a connectivity cost is assigned to every pair of connected components. Then, beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, the components are placed in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost. The cluster tree may then traversed to partition the components into clusters. The clusters can be optimized by moving individual components to clusters when such a move results in a lower incremental connectivity cost. Once the components have been partitioned into clusters, the clusters of components may be placed on an integrated circuit.
57 Citations
18 Claims
-
1. A computer implemented method for partitioning components of an integrated circuit into clusters in preparation for placement of the clusters onto an integrated circuit, the method implemented by a computer and comprising the steps of:
-
(a) assigning, by the computer, a connectivity cost to every pair of connected components; (b) beginning with a pair of connected components with a lowest assigned connectivity cost and proceeding to a pair of connected components with a highest assigned connectivity cost, placing, by the computer, the components in a cluster tree so that when merging cluster tree nodes, a cluster tree node with a higher connectivity cost is made a parent cluster tree node of a cluster tree node with a lower connectivity cost; and
,(c) traversing, by the computer, the cluster tree to partition the components into clusters. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
Specification