# US 9,519,744 B1 · Merging of storage elements on multi-cycle signal distribution trees into multi-bit cells > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,519,744 B1 - Document ID: US9519744B1 - Status: Granted - Kind: B1 - Application number: 14/960,812 - Filed: 2015-12-07 - Granted: 2016-12-13 - Earliest claimed: 2015-12-07 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: William R. Migatz; Shyam Ramji - Web page: https://patentgrep.com/patent/US9519744B1 ## CPC - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist - G06F 30/396: Clock trees - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method, system, and computer program product to merge storage elements on multi-cycle signal distribution trees into multi-bit cells of an integrated circuit include determining initial placement regions and initial placement locations for a plurality of storage elements arranged in two or more levels on the one or more trees, determining potential merge storage elements among the plurality of storage elements, and merging one or more pairs of the potential merge storage elements across the one or more trees into the multi-bit cells based on satisfying an additional condition. The two or more levels of each of the one or more trees includes a root level closest to a tree source of the respective one or more trees and a leaf level closest to a tree sink of the respective one or more trees. ## Claims ### Claim 1 A computer-implemented method of merging storage elements on one or more multi-cycle signal distribution trees into multi-bit cells of an integrated circuit, the method comprising: determining, using a processor, initial placement regions and initial placement locations for a plurality of storage elements arranged in two or more levels on the one or more trees, the two or more levels of each of the one or more trees including a root level closest to a tree source of the respective one or more trees and a leaf level closest to a tree sink of the respective one or more trees; determining potential merge storage elements among the plurality of storage elements, the potential merge storage elements being eligible for merger; and merging one or more pairs of the potential merge storage elements across the one or more trees into the multi-bit cells based on satisfying an additional condition, wherein the additional condition is based on a source storage element among the plurality of storage elements for each potential merge storage element of the one or more pairs, and each source storage element corresponding with each potential merge storage element is arranged in a level among the two or more levels that is closer to the tree source than the potential merge storage element. ### Claim 2 (depends on 1) The computer-implemented method according to claim 1, wherein the satisfying the additional condition, for each pair of potential merge storage elements, includes the storage elements that are sources of each of the pair of potential merge storage elements being merged or includes the storage elements that are the sources of each of the pair of potential merge storage elements being within a predefined threshold distance of each other. ### Claim 3 (depends on 1) The computer-implemented method according to claim 1, wherein the satisfying the additional condition, for each pair of potential merge storage elements, includes determining whether a region associated with each of the sources of each of the pair of potential merge storage elements and the placement shapes of each of the pair of potential merge storage elements is non-empty. ### Claim 4 (depends on 1) The computer-implemented method according to claim 1, wherein the merging the one or more pairs of the potential merge storage elements includes building a connected graph based on the additional condition being satisfied and identifying cliques in the connected graph. ### Claim 5 (depends on 1) The computer-implemented method according to claim 1, wherein the determining the potential merge storage elements is based on processing one or more of the one or more trees, in parallel, one current level at a time, from the root level to the leaf level based on expanding the initial placement regions of the storage elements among the plurality of storage elements that are located at a level above the current level toward the tree source into expanded placement regions and intersecting the expanded placement regions with placement shapes obtained from the initial placement regions of the storage elements among the plurality of storage elements that are located at the current level, non-empty results of the intersecting indicating the potential merge storage elements. ### Claim 6 (depends on 1) The computer-implemented method according to claim 1, further comprising determining a merge placement region for each pair of potential merge storage elements based on an intersection of a region around the pair of potential merge storage elements with expanded regions around each source of the pair of potential merge storage elements, wherein the determining the merge placement region is performed one level at a time from the leaf level to the root level and the determining the potential merge storage elements and the determining the merge placement region is performed iteratively. ### Claim 7 (depends on 1) The computer-implemented method according to claim 1, further comprising determining a placement location for each merged and unmerged one of the plurality of storage elements based on an intersection of a final placement region of the merged or unmerged one of the plurality of storage elements with the initial placement region of the one or more sources associated with the merged or unmerged one of the plurality of storage elements. ### Claim 8 (depends on 1) The computer-implemented method according to claim 1, further comprising mapping the multi-bit cells into implementable multi-bit storage elements of one, two, four, or eight bits. ### Claim 9 A system to merge storage elements on one or more multi-cycle signal distribution trees into multi-bit cells of an integrated circuit, the system comprising: a memory device configured to store initial placement regions and initial placement locations determined for a plurality of storage elements arranged in two or more levels on the one or more trees, the two or more levels of each of the one or more trees including a root level closest to a tree source of the respective one or more trees and a leaf level closest to a tree sink of the respective one or more trees; and a processor configured to determine potential merge storage elements among the plurality of storage elements, the potential merge storage elements being eligible for merger, and merge one or more pairs of the potential merge storage elements across the one or more trees into the multi-bit cells based on satisfying an additional condition, wherein the additional condition is based on a source storage element among the plurality of storage elements for each potential merge storage element of the one or more pairs, and each source storage element corresponding with each potential merge storage element is arranged in a level among the two or more levels that is closer to the tree source than the potential merge storage element. ### Claim 10 (depends on 9) The system according to claim 9, wherein the additional condition includes the storage elements that are sources of each of the pair of potential merge storage elements being merged, or includes the storage elements that are the sources of each of the pair of potential merge storage elements being within a predefined threshold distance of each other, or includes a region associated with each of the sources of each of the pair of potential merge storage elements and the placement shapes of each of the pair of potential merge storage elements being non-empty. ### Claim 11 (depends on 9) The system according to claim 9, wherein the processor merges the one or more pairs of the potential merge storage elements by building a connected graph based on the additional condition being satisfied and identifying cliques in the connected graph. ### Claim 12 (depends on 9) The system according to claim 9, wherein the processor determines the potential merge storage elements based on processing one or more of the one or more trees, in parallel, one current level at a time, from the root level to the leaf level based on expanding the initial placement regions of the storage elements among the plurality of storage elements that are located at a level above the current level toward the tree source into expanded placement regions and intersecting the expanded placement regions with placement shapes obtained from the initial placement regions of the storage elements among the plurality of storage elements that are located at the current level, non-empty results of the intersecting indicating the potential merge storage elements. ### Claim 13 (depends on 9) The system according to claim 9, wherein the processor determines a merge placement region for each pair of potential merge storage elements based on an intersection of a region around the pair of potential merge storage elements with expanded regions around each source of the pair of potential merge storage elements, and determines the merge placement region for one level at a time from the leaf level to the root level, and the processor determines the potential merge storage elements and the merge placement region iteratively. ### Claim 14 (depends on 9) The system according to claim 9, wherein the processor determines a placement location for each merged and unmerged one of the plurality of storage elements based on an intersection of a final placement region of the merged or unmerged one of the plurality of storage elements with the initial placement region of the one or more sources associated with the merged or unmerged one of the plurality of storage elements, and the system maps the multi-bit cells into implementable multi-bit storage elements of one, two, four, or eight bits. ### Claim 15 A computer program product for merging storage elements on one or more multi-cycle signal distribution trees into multi-bit cells of an integrated circuit, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to perform a method comprising: determining initial placement regions and initial placement locations for a plurality of storage elements arranged in two or more levels on the one or more trees, the two or more levels of each of the one or more trees including a root level closest to a tree source of the respective one or more trees and a leaf level closest to a tree sink of the respective one or more trees; determining potential merge storage elements among the plurality of storage elements, the potential merge storage elements being eligible for merger; and merging one or more pairs of the potential merge storage elements across the one or more trees into the multi-bit cells based on satisfying an additional condition, wherein the additional condition is based on a source storage element among the plurality of storage elements for each potential merge storage element of the one or more pairs, and each source storage element corresponding with each potential merge storage element is arranged in a level among the two or more levels that is closer to the tree source than the potential merge storage element. ### Claim 16 (depends on 15) The computer program product according to claim 15, wherein the satisfying the additional condition, for each pair of potential merge storage elements, includes the storage elements that are sources of each of the pair of potential merge storage elements being merged, or includes the storage elements that are the sources of each of the pair of potential merge storage elements being within a predefined threshold distance of each other, or includes determining whether a region associated with each of the sources of each of the pair of potential merge storage elements and the placement shapes of each of the pair of potential merge storage elements is non-empty. ### Claim 17 (depends on 15) The computer program product according to claim 15, wherein the merging the one or more pairs of the potential merge storage elements includes building a connected graph based on the additional condition being satisfied and identifying cliques in the connected graph. ### Claim 18 (depends on 15) The computer program product according to claim 15, wherein the determining the potential merge storage elements is based on processing one or more of the one or more trees, in parallel, one current level at a time, from the root level to the leaf level based on expanding the initial placement regions of the storage elements among the plurality of storage elements that are located at a level above the current level toward the tree source into expanded placement regions and intersecting the expanded placement regions with placement shapes obtained from the initial placement regions of the storage elements among the plurality of storage elements that are located at the current level, non-empty results of the intersecting indicating the potential merge storage elements. ### Claim 19 (depends on 15) The computer program product according to claim 15, further comprising determining a merge placement region for each pair of potential merge storage elements based on an intersection of a region around the pair of potential merge storage elements with expanded regions around each source of the pair of potential merge storage elements, wherein the determining the merge placement region is performed one level at a time from the leaf level to the root level and the determining the potential merge storage elements and the determining the merge placement region is performed iteratively. ### Claim 20 (depends on 15) The computer program product according to claim 15, further comprising determining a placement location for each merged and unmerged one of the plurality of storage elements based on an intersection of a final placement region of the merged or unmerged one of the plurality of storage elements with the initial placement region of the one or more sources associated with the merged or unmerged one of the plurality of storage elements, and mapping the multi-bit cells into implementable multi-bit storage elements of one, two, four, or eight bits.