Sector-based clock routing methods and apparatus

1. A clock-tree construction method for a configurable clock grid structure, comprising:

defining a clock region within a configurable clock grid structure having a plurality of sectors and a plurality of wire segments;

constructing an H-tree that covers the clock region;

aligning the clock region within the H-tree;

reducing a size or a height of the H-tree to generate a clock tree; and

configuring a programmable integrated circuit device using the configurable clock grid structure of the generated clock tree.

2. The method of claim 1 , wherein the clock region is defined based on physical locations of a plurality of registers.

3. The method of claim 2 , further comprising:

modifying the clock region based on the configurable clock grid structure; and

modifying the physical locations of the plurality of registers within the modified clock region.

4. The method of claim 2 , further comprising:

synthesizing the clock tree for the clock region;

determining delay characteristics of the clock tree based on timing analysis; and

iteratively re-placing the plurality of registers to improve delay performance.

5. The method of claim 1 , wherein the clock region is aligned to a lower-left H-tree quadrant.

6. The method of claim 1 , wherein the clock region has an arbitrary size or shape.

7. The method of claim 1 , wherein a root of the clock tree is placed in proximity to a clock source to reduce clock insertion delay.

8. The method of claim 1 ,

wherein reducing a size or a height of the H-tree includes:

pruning the H-tree and removing an unused segment from the H-tree; and

performing a tree height reduction procedure to the pruned H-tree.

9. The method of claim 8 , wherein the tree height reduction procedure includes:

identifying a first path connecting a first root of a first subtree and a second root of a second subtree, a second path connecting the first root of the first subtree and a third root of a third subtree, wherein

the second and third subtrees are next-level subtrees to the first subtree;

identifying two segments with a same direction from the first and the second paths, wherein

the two segments are traversed by a straight line partition horizontally or vertically through the configurable clock grid structure; and

removing the two segments from the pruned H-tree.

10. The method of claim 8 , wherein the tree height reduction procedure further includes:

identifying a path connecting a first root of a first subtree and a second root of a second subtree, wherein

the second subtree is a next-level subtree to the first subtree;

identifying two segments with an opposite direction on the path, wherein

the two segments are traversed by a straight line partition horizontally or vertically through the configurable clock grid structure;

removing the two segments from the pruned H-tree; and

moving the first root towards a third subtree at a same level of the first subtree.

11. The method of claim 8 , wherein the H-tree has a smallest size to cover the clock region.

12. The method of claim 1 , further comprising:

assigning a plane of the configurable clock grid structure to the clock tree.

13. The method of claim 1 , further comprising:

determining a first top-level partition for the clock tree;

choosing a first subset of the H-tree to prune based on the first top-level partition; and

obtaining a first pruned H-tree and a first insertion delay from the first pruned H-tree.

14. The method of claim 13 , further comprising:

determining a second top-level partition for the clock tree;

choosing a second subset of the H-tree to prune based on the second top-level partition;

obtaining a second pruned H-tree and a second insertion delay from the second pruned H-tree; and

selecting the second top-level partition for pruning when the second insertion delay is less than the first insertion delay.

15. The method of claim 1 , wherein the H-tree is a combined H-tree including a first H-tree that covers a first region smaller than the clock region and

a second H-tree that covers a second region smaller than the clock region.

16. The method of claim 15 , wherein the first H-tree has an X-dimension and a Y-dimension of a power of two.

17. The method of claim 15 , wherein the first H-tree and the second H-tree have an overlapping subtree.

18. The method of claim 17 , further comprising:

determining a first top-level partition for the combined H-tree;

pruning the overlapping subtree based on the first top-level partition;

determining a first critical path that traverses the first top-level partition; and

estimating a first clock loss for a clock signal transmitting along the first critical path.

19. The method of claim 18 , further comprising:

determining a second top-level partition for the combined H-tree;

pruning the overlapping subtree based on the second top-level partition;

determining a second critical path that traverses the second top-level partition;

estimating a second clock loss for a second clock signal transmitting along the second critical path; and

selecting the second top-level partition to prune the overlapping subtree when the second clock loss is less than the first clock loss.

20. The method of claim 15 , further comprising:

selecting the first H-tree to transmit a clock signal.

21. The method of claim 20 , further comprising:

performing timing analysis to generate a set of timing constraints for the first H-tree.

22. The method of claim 1 , further comprising:

obtaining an initial placement of a plurality of registers within the configurable clock grid structure, wherein

the initial placement includes a first location of the plurality of registers;

the clock region is defined based on the initial placement of the plurality of registers;

selectively pruning a first subset of the H-tree to generate a first pruned clock tree, wherein

the first pruned clock tree has a first clock timing factor; and

modifying the initial placement of the plurality of registers based on the first pruned clock tree.

23. The method of claim 22 , further comprising:

pruning a second subset of the H-tree to generate a second pruned clock tree, wherein

the second pruned clock tree has a second clock timing factor; and

selecting the first pruned clock tree when the first clock timing factor is less than the second clock timing factor.

24. The method of claim 22 , further comprising:

modifying the clock region based on the first pruned clock tree.

25. The method of claim 22 , wherein the first clock timing factor includes any of a clock insertion delay, or a clock loss incurred by pruning of the first clock tree.

26. A processor-readable non-transitory medium storing processor-executable instructions for clock-tree construction on a configurable clock grid structure having a plurality of sectors and a plurality of wire segments, the processor-executable instructions comprising:

instructions executable by a processor to define a clock region within the configurable clock grid structure;

instructions executable by the processor to construct an H-tree that covers the clock region;

instructions executable by the processor to align the clock region within the H-tree;

instructions executable by the processor to reduce a size or a height of the H-tree to generate a clock tree; and

instructions executable by the processor to configure a programmable integrated circuit device using the configurable clock grid structure of the generated clock tree.

27. Circuitry operated with a clock signal transmitted through a configurable clock tree, comprising:

a plurality of sectors, wherein

a clock region is defined to cover one or more sectors from the plurality of sectors; and

a plurality of wire segments, wherein

a subset of the plurality of wire segments are selected to form the configurable clock tree,

wherein the configurable clock tree is generated by reducing a size or a height of an H-tree, and

wherein the H-tree is constructed from the plurality of wire segments to cover the clock region.