# US 2019/0173781 A1 · Constructing staging trees in hierarchical circuit designs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0173781 A1 - Document ID: US20190173781A1 - Status: Published application - Kind: A1 - Application number: 15/828,715 - Filed: 2017-12-01 - Published: 2019-06-06 - Earliest claimed: 2017-12-01 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Harald Folberth; Sven Nitzsche; Sven Peyer - Web page: https://patentgrep.com/patent/US20190173781A1 ## CPC - G06F 30/30: Circuit design - G06F 1/10: Distribution of clock signals {, e.g. skew} - G06F 30/396: Clock trees - G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) - G06F 30/394: Routing (G06F30/396 takes precedence) - G06F 2119/12: Timing analysis or timing optimisation - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method can include receiving design data of the integrated circuit, the design data indicates a set of sub-units partitioning an area of an integrated circuit, and a clock tree coupling the sub-units, the clock tree including a selected memory element, a predecessor memory element, and successor elements; determining a valid placement region for relocating the selected memory element; generating grid comprising first set of perpendicularly intersecting lines through the selected memory element, predecessor memory element, and successor elements; extending the grid to include second set of perpendicularly intersecting lines through vertices of the valid placement region and through intersections between edges of the valid placement region and the first set of perpendicularly intersecting lines; determining, within the valid placement region, a point in the extended grid having a minimum total rectilinear distance to the predecessor memory element and the successor elements; relocating the memory element to the determined point. ## Claims ### Claim 1 A method for improving a layout of a clock tree in an integrated circuit, the method comprising: receiving design data of the integrated circuit, the design data indicating: a set of sub-units partitioning an area of the integrated circuit, and a clock tree coupling the sub-units, the clock tree having a selected memory element, a predecessor memory element, and successor elements; determining a valid placement region for relocating the selected memory element; generating grid comprising a first set of perpendicularly intersecting lines through the selected memory element, the predecessor memory element, and the successor elements; extending the grid to include a second set of perpendicularly intersecting lines through vertices of the valid placement region and through intersections between edges of the valid placement region and the first set of perpendicularly intersecting lines; determining, within the valid placement region, a point in the extended grid having a minimum total rectilinear distance to the predecessor memory element and to the successor elements; and relocating the memory element to the determined point. ### Claim 2 (depends on 1) The method of claim 1, wherein the selected memory element includes immediate successor memory elements, and determining the valid placement region includes: determining a first maximum distance region around the predecessor memory element; determining second maximum distance regions around each immediate successor memory elements; and determining the valid placement region based on intersections of the first maximum distance region and the second maximum distance regions. ### Claim 3 (depends on 2) The method of claim 2, wherein a maximum distance region indicates a maximum rectilinear distance for placing a first memory element from a second memory element without violating timing requirements of the integrated circuit. ### Claim 4 (depends on 2) The method of claim 2, wherein a maximum distance region comprises a rhombus. ### Claim 5 (depends on 1) The method of claim 1, further comprising: selecting, prior to generating the grid, a sub-unit in the set of sub-units on which to place the selected memory element, the sub-unit selected to reduce clock tree crossings between subunits. ### Claim 6 (depends on 1) The method of claim 1, wherein the clock tree is a staging tree and the memory elements are latches. ### Claim 7 (depends on 1) The method of claim 1, wherein relocating the selected memory element to the determined point includes reducing a wiring length of the clock tree. ### Claim 8 (depends on 1) The method of claim 1, wherein the grid comprising a first set of perpendicularly intersecting lines is a Hanan Grid. ### Claim 9 (depends on 1) The method of claim 1, wherein the successor elements include immediate successor memory elements, and one or more sinks. ### Claim 10 A system for improving a layout of a clock tree in an integrated circuit, this system comprising: one or more computing nodes having a memory and a processor; and a non-transitory computer readable storage medium of the one or more computing nodes having program instructions embodied therewith, the program instructions executable by the processor to cause the system to: receive design data of the integrated circuit, the design data indicating: a set of sub-units partitioning an area of the integrated circuit, and a clock tree coupling the sub-units, the clock tree having a selected memory element, a predecessor memory element, and successor elements; determine a valid placement region for relocating the selected memory element; generate grid comprising a first set of perpendicularly intersecting lines through the selected memory element, the predecessor memory element, and the successor elements; extend the grid to include a second set of perpendicularly intersecting lines through vertices of the valid placement region and through intersections between edges of the valid placement region and the first set of perpendicularly intersecting lines; determine, within the valid placement region, a point in the extended grid having a minimum total rectilinear distance to the predecessor memory element and to the successor elements; and relocate the memory element to the determined point. ### Claim 11 (depends on 10) The system of claim 10, wherein the selected memory element includes immediate successor memory elements, and wherein the program instructions are further executable by the processor to cause the system to: determine a first maximum distance region around the predecessor memory element; determine second maximum distance regions around each immediate successor memory elements; and determine the valid placement region based on intersections of the first maximum distance region and the second maximum distance regions. ### Claim 12 (depends on 11) The system of claim 11, wherein a maximum distance region indicates a maximum rectilinear distance for placing a first memory element from a second memory element without violating timing requirements of the integrated circuit. ### Claim 13 (depends on 11) The system of claim 11, wherein a maximum distance region comprises a rhombus. ### Claim 14 (depends on 10) The system of claim 10, program instructions are further executable by the processor to cause the system to: select, prior to generating the grid, a sub-unit in the set of sub-units on which to place the selected memory element, the sub-unit selected to reduce clock tree crossings between subunits. ### Claim 15 (depends on 10) The system of claim 10, wherein the clock tree is a staging tree and the memory elements are latches. ### Claim 16 (depends on 10) The system of claim 10, wherein relocating the selected memory element to the determined point includes reducing a wiring length of the clock tree. ### Claim 17 (depends on 10) The system of claim 10, wherein the grid comprising a first set of perpendicularly intersecting lines is a Hanan Grid. ### Claim 18 (depends on 10) The system of claim 10, wherein the successor elements include immediate successor memory elements, and one or more sinks. ### Claim 19 A computer program product for improving a layout of a clock tree in an integrated circuit, the computer program product including a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processing circuit to cause the processing circuit to perform a method comprising: receiving design data of the integrated circuit, the design data indicating: a set of sub-units partitioning an area of the integrated circuit, and a clock tree coupling the sub-units, the clock tree having a selected memory element, a predecessor memory element, and successor elements; determining a valid placement region for relocating the selected memory element; generating grid comprising a first set of perpendicularly intersecting lines through the selected memory element, the predecessor memory element, and the successor elements; extending the grid to include a second set of perpendicularly intersecting lines through vertices of the valid placement region and through intersections between edges of the valid placement region and the first set of perpendicularly intersecting lines; determining, within the valid placement region, a point in the extended grid having a minimum total rectilinear distance to the predecessor memory element and to the successor elements; and relocating the memory element to the determined point. ### Claim 20 (depends on 19) The computer program product of claim 19, wherein the selected memory element includes immediate successor memory elements, and determining the valid placement region includes: determining a first maximum distance region around the predecessor memory element; determining second maximum distance regions around each immediate successor memory elements; and determining the valid placement region based on intersections of the first maximum distance region and the second maximum distance regions.