# US 10,372,861 B2 · Method of macro placement and a non-transitory computer readable medium thereof > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,861 B2 - Document ID: US10372861B2 - Status: Granted - Kind: B2 - Application number: 15/362,700 - Filed: 2016-11-28 - Published: 2018-05-31 - Granted: 2019-08-06 - Earliest claimed: 2016-11-28 - Assignees: NCKU Research and Development Foundation; Himax Technologies Limited - Applicants: NCKU Research and Development Foundation; Himax Technologies Limited - Inventors: Chia-Min Lin; Te-Wei Peng; Fa-Ta Chen; Chia-Ching Huang - Web page: https://patentgrep.com/patent/US10372861B2 ## CPC - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F 2119/18: Manufacturability analysis or optimisation for manufacturability - Y02P 90/02: Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS] - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS ## Abstract A method of macro placement includes partitioning an entire region of a semiconductor chip into sub-regions; determining a packing sequence of a plurality of movable macros in the sub-region; extracting search points of a plurality of placed blocks in the sub-region with respect to one of the movable macros; determining a feasible region associated with the search point; packing said movable macro in the feasible region; evaluating a legalizing cost function; and determining whether a value of the evaluated legalizing cost function is less than a predetermined threshold value. ## Claims ### Claim 1 A method of macro placement, comprising: partitioning an entire region of a semiconductor chip into sub-regions; determining a packing sequence of a plurality of movable macros in one sub-region of the sub-regions; extracting search points of a plurality of placed blocks in the sub-region with respect to one of the movable macros; determining a feasible region associated with one search point of the extracted search points; packing said movable macro in the feasible region; evaluating a legalizing cost function; and determining whether a value of the evaluated legalizing cost function is less than a predetermined threshold value; wherein for every one of the placed blocks, two opposite points of the placed block are extracted, and two points that are projections of the two opposite points are further extracted. ### Claim 2 (depends on 1) The method of claim 1, wherein the packing sequence of the movable macros is determined by sorting the movable macros according to areas, locations and aspect ratios of the movable macros. ### Claim 3 (depends on 1) The method of claim 1, wherein the packing sequence of the movable macros is determined by sorting the movable macros according to values computed by a packing cost function expressed as follows: cost(mi)=αai+βli+γti where ai is an area of the movable macro mi, li is a reciprocal of a distance between the movable macro mi's initial location and a bottom-left point of the sub-region, ti is an aspect ratio of the movable macro mi, α, β and γ are corresponding weightings. ### Claim 4 (depends on 1) The method of claim 1, wherein four search points S1, S2, S3 and S4 for the placed block are extracted as follows: S1: a top-left point of the placed block; S2: a point which is projection of S1 on a boundary of a neighboring placed block or a boundary of the sub-region when facing left; S3: a bottom-right point of the placed block; and S4: a point which is projection of S3 on a boundary of a neighboring placed block or a boundary of the sub-region when facing down. ### Claim 5 (depends on 4) The method of claim 4, wherein the extracted search points of the placed blocks are sorted according to their locations first in a bottom-to-top order, and then a left-to-right order. ### Claim 6 (depends on 1) The method of claim 1, wherein the step of determining the feasible region comprises: constructing at least one horizontal sweeping line that passes through a first boundary edge of every placed block and is across the sub-region horizontally; constructing at least one vertical sweeping line that passes through a second boundary edge of every placed block and is across the sub-region vertically; said search point moving forward vertically until being obstructed by a placed block, resulting in a first point; said search point moving forward horizontally until being obstructed by a placed block, resulting in a second point; obtaining intersecting points of the horizontal sweeping lines and the vertical sweeping lines within a region defined by the first point and the second point; and determining the feasible region defined by said search point and the intersecting point without encountering a placed block. ### Claim 7 (depends on 6) The method of claim 6, further comprising a step of sorting the intersecting points according to their locations first in a top-to-bottom order, and then a left-to-right order. ### Claim 8 (depends on 6) The method of claim 6, wherein a small region defined by the search point and an intersecting point is a subset of a large region defined by the search point and another intersecting point, and the small region is discarded. ### Claim 9 (depends on 1) The method of claim 1, after the movable macro is packed in the feasible region, a width or a height of the movable macro is adjustably lengthened such that no narrow channel is generated in the feasible region. ### Claim 10 (depends on 1) The method of claim 1, wherein the legalizing cost function is expressed as follows: cost(s)=θO+μD+ωT+δC+εW where O is a total area of overlaps between any two movable macros, D is a total displacement of the movable macros, T is a thickness of the movable macros placed in the sub-region, C is a deadspace, W is a half-perimeter wirelength, θ, μ, ω, δ and ε are weightings. ### Claim 11 (depends on 1) The method of claim 1, before determining the packing sequence, further comprising a step of constructing a grid graph to record feasible placement locations in the sub-region. ### Claim 12 A non-transitory computer readable medium containing program instructions causing a computer to perform the following steps: partitioning an entire region of a semiconductor chip into sub-regions; determining a packing sequence of a plurality of movable macros in one sub-region of the sub-regions; extracting search points of a plurality of placed blocks in the sub-region with respect to one of the movable macros; determining a feasible region associated with one search point of the extracted search points; packing said movable macro in the feasible region; evaluating a legalizing cost function; and determining whether a value of the evaluated legalizing cost function is less than a predetermined threshold value; wherein for every one of the placed blocks, two opposite points of the placed block are extracted, and two points that are projections of the two opposite points are further extracted. ### Claim 13 (depends on 12) The non-transitory computer readable medium of claim 12, wherein the packing sequence of the movable macros is determined by sorting the movable macros according to areas, locations and aspect ratios of the movable macros. ### Claim 14 (depends on 12) The non-transitory computer readable medium of claim 12, wherein the step of determining the feasible region comprises: constructing at least one horizontal sweeping line that passes through a first boundary edge of every placed block and is across the sub-region horizontally; constructing at least one vertical sweeping line that passes through a second boundary edge of every placed block and is across the sub-region vertically; said search point moving forward vertically until being obstructed by a placed block, resulting in a first point; said search point moving forward horizontally until being obstructed by a placed block, resulting in a second point; obtaining intersecting points of the horizontal sweeping lines and the vertical sweeping lines within a region defined by the first point and the second point; and determining the feasible region defined by said search point and the intersecting point without encountering a placed block. ### Claim 15 (depends on 12) The non-transitory computer readable medium of claim 12, after the movable macro is packed in the feasible region, a width or a height of the movable macro is adjustably lengthened such that no narrow channel is generated in the feasible region. ### Claim 16 (depends on 12) The non-transitory computer readable medium of claim 12, before determining the packing sequence, further comprising a step of constructing a grid graph to record feasible placement locations in the sub-region.