Constructing a clock tree for an integrated circuit design
A method and apparatus for constructing a clock tree for an integrated circuit design is disclosed, the method comprising: extracting the path delays between the sequential devices in a placed netlist by performing timing analysis on the placed netlist; and constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices so as to make the sum of the products of the timing delay between any two sequential devices and a clock tree branch weight of the two sequential devices minimum, wherein the clock tree branch weight of the two sequential devices is positively correlated with the number of clock tree levels from the branch point of the clock tree relative to the two sequential devices to the two sequential devices.
1. A method for constructing a clock tree for an integrated circuit design, comprising:
using a computer, extracting path delays between sequential devices in a placed netlist by performing timing analysis on the placed netlist; and
using a computer, constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices so as to make the sum of the products of the timing delay between any two sequential devices and a clock tree branch weight of the two sequential devices minimum, wherein the clock tree branch weight of the two sequential devices is positively correlated with the number of clock tree levels from of the clock tree from the branch point of the clock tree relative to the two sequential devices to the two sequential devices.
2. The method of claim 1 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix DDly according to the path delays between the sequential devices, wherein the element DDly(j, k) of the path delay matrix DDly denotes the delay of the data path between the sequential devices j and k, wherein the path delay between two sequential devices that do not have a data pathway relationship is 0;
solving a clock tree branch weight matrix CKweight according to the path delay matrix so as to make the sum of the products of every element DDly(j, k) of the path delay matrix DDly and the corresponding element CKweight (j, k) of a clock tree branch weight matrix CKweight minimum, wherein the element CKweight(j, k) of the clock tree branch weight matrix CKweight denotes the clock tree branch weight between the sequential devices j and k; and
constructing the clock tree according to the clock tree branch weight matrix.
3. The method of claim 2 , wherein the clock tree is a binary tree, the clock tree branch weight of the two sequential devices is equal to the number of clock tree levels from the branch point of the clock tree relative to the two sequential devices to the two sequential devices, and the clock tree branch weight between a sequential device and itself is zero.
4. The method of claim 3 , wherein the numbers of rows and columns of the path delay matrix DDly and the clock tree branch weight matrix CKweight are both 2 t , t being a positive integer, and when the number m of the actual sequential devices in the netlist is smaller than 2 t , the rows and columns of the path delay matrix DDly and the clock tree branch weight matrix CKweight further include 2 t −m virtual sequential devices, and the path delays between the virtual devices and the actual sequential devices and between the virtual devices are 0.
5. The method of claim 4 , wherein the solving the clock tree branch weight matrix according to the path delay matrix is performed by applying the transportation theory,
wherein the rows and columns of the path delay matrix are viewed as representing production places and selling places, or selling places and production places, respectively, its elements are viewed as representing the unit transportation costs between the production places and selling places; the rows and columns of the clock tree branch weight matrix are viewed as representing the production places and selling places, or selling places and production places, respectively, and its elements are viewed as representing the volumes of goods transported from the corresponding production places to the corresponding selling places; the sum of the products of each element in the path delay matrix and the corresponding element in the clock tree branch weight matrix is viewed as the total transportation cost; and, the elements in each row and each column of the clock tree branch weight matrix are all one 0, one 1, two 2s, four 3s, . . . , i-2 t−1 ts.
6. The method of claim 1 , further comprising:
inserting the clock tree into the placed netlist, so as to get a clock tree synthesized integrated circuit design.
7. The method of claim 1 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices, wherein the element of the path delay matrix denotes the delay of the data path between two sequential devices, wherein the path delay between two sequential devices that do not have a data pathway relationship is 0;
solving a clock tree branch weight matrix according to the path delay matrix wherein the element of the clock tree branch weight matrix denotes the clock tree branch weight between the sequential devices; and
constructing the clock tree according to the clock tree branch weight matrix.
8. The method of claim 1 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices;
solving a clock tree branch weight matrix according to the path delay matrix; and
constructing the clock tree according to the clock tree branch weight matrix.
9. The method of claim 1 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices, wherein the element of the path delay matrix denotes the delay of the data path between two sequential devices, wherein the path delay between two sequential devices that do not have a data pathway relationship is 0.
10. The method of claim 2 , wherein the minimum is given by the equation:
Σ j=0 2 t −1 Σ k=0 2 t −1 DDLy(j,k)×CKweight(j,k).
11. An apparatus for constructing a clock tree for an integrated circuit design, comprising:
an extracting module for extracting path delays between sequential devices in a placed netlist by performing timing analysis on the placed netlist;
a constructing module for constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices so as to make the sum of the products of the timing delay between any two sequential devices and a clock tree branch weight of the two sequential devices minimum, wherein the clock tree branch weight of the two sequential devices is positively correlated with clock tree series of the clock trees from the pair of sequential devices relative to the branch point of the pair of sequential devices.
12. The apparatus of claim 11 , wherein the constructing module comprises:
a device for constructing a path delay matrix DDly according to the path delay between the sequential devices, wherein element DDly(j, k) of the path delay matrix DDly denotes a delay of a data path between sequential devices j and k, wherein a path delay between two sequential devices that do not have a data pathway relationship is 0;
a device for solving a clock tree branch weight matrix CKweight according to the path delay matrix, wherein element CKweight(j, k) of the clock tree branch weight matrix CKweight denotes a clock tree branch weight between the sequential devices j and k, and wherein a sum of products of every element DDly(j, k) of the path delay matrix DDly and corresponding element CKweight(j, k) of the clock tree branch weight matrix CKweight is minimum; and
a device for constructing a clock tree according to the clock tree branch weight.
13. The apparatus of claim 11 , wherein the clock tree is a binary tree, the clock tree branch weight of the two sequential devices is equal to the number of clock tree levels from the branch point of the clock tree relative to the two sequential devices to the two sequential devices, and the clock tree branch weight between a sequential device and itself is zero.
14. The apparatus of claim 13 , wherein the numbers of rows and columns of the path delay matrix DDly and the clock tree branch weight matrix CKweight are both 2 t , t being a positive integer, and when the number m of the actual sequential devices in the netlist is smaller than 2\ the rows and columns of the path delay matrix DDly and the clock tree branch weight matrix CKweight further include t-m virtual sequential devices, and path delays between the virtual devices and the actual sequential devices and between the virtual devices are O.
15. The apparatus of claim 14 , wherein the solving the clock tree branch weight matrix according to the path delay matrix is performed by applying a transportation theory,
wherein the rows and columns of the path delay matrix are viewed as representing production places and selling places, or selling places and production places, respectively, its elements are viewed as representing the unit transportation costs between the production places and selling places; the rows and columns of the clock tree branch weight matrix are viewed as representing the production places and selling places, or the selling places and production places, respectively, and its elements are viewed as representing the volumes of goods transported from the corresponding production places to the corresponding selling places; the sum of the products of each element in the path delay matrix and the corresponding elements in the clock tree branch weight matrix is viewed as the total transportation cost; moreover, the elements in each row and each column of the clock tree branch weight matrix are all one 0, one 1, two 2s, four 3s, . . . , 2 t−1 ts.
16. The apparatus of claim 11 , further comprising:
an inserting module for inserting the clock tree into the placed netlist, so as to get a clock tree synthesized integrated circuit design.
17. The apparatus of claim 11 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices, wherein the element of the path delay matrix denotes the delay of the data path between two sequential devices, wherein the path delay between two sequential devices that do not have a data pathway relationship is 0;
solving a clock tree branch weight matrix according to the path delay matrix wherein the element of the clock tree branch weight matrix denotes the clock tree branch weight between the sequential devices; and
constructing the clock tree according to the clock tree branch weight matrix.
18. The apparatus of claim 11 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices;
solving a clock tree branch weight matrix according to the path delay matrix; and
constructing the clock tree according to the clock tree branch weight matrix.
19. The apparatus of claim 11 , wherein the constructing a clock tree for driving the sequential devices according to the path delays between the sequential devices comprises:
constructing a path delay matrix according to the path delays between the sequential devices, wherein the element of the path delay matrix denotes the delay of the data path between two sequential devices, wherein the path delay between two sequential devices that do not have a data pathway relationship is 0.
20. The apparatus of claim 12 , wherein the minimum is given by the equation:
Σ j=0 2 t −1 Σ k=0 2 t −1 DDLy(j,k)×CKweight(j,k).