# US 10,769,341 B1 · Method of placing macro cells and a simulated-evolution-based macro refinement method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,769,341 B1
- Document ID: US10769341B1
- Status: Granted
- Kind: B1
- Application number: 16/390,840
- Filed: 2019-04-22
- Granted: 2020-09-08
- Earliest claimed: 2019-04-22
- Assignees: NCKU Research and Development Foundation; Himax Technologies Limited
- Applicants: NCKU Research and Development Foundation; Himax Technologies Limited
- Inventors: Chia-Min Lin; You-Lun Deng
- Web page: https://patentgrep.com/patent/US10769341B1

## CPC

- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G06F 7/58: Random or pseudo-random number generators
- G06F 2111/06: Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A simulated-evolution-based macro refinement method includes evaluating a score of each placed macro cell to be refined; generating a random number; determining whether the score satisfies a predetermined condition; placing the macro cell into a queue if the score associated with the macro cell satisfies the predetermined condition; and sorting and placing macro cells of the queue according to scores of the macro cells in the queue.

## Claims

### Claim 1

A method of placing macro cells, comprising:
performing corner-stitching-based macro legalization on a macro group composed of macro cells to be placed;
evaluating a score of each placed macro cell to be refined;
normalizing the score to be in a predetermined range to result in a normalized score;
generating a random number, which is in the same predetermined range as the normalized score;
determining whether the normalized score is greater than the random number;
placing the macro cell into a queue if the normalized score is greater than the random number; and
sorting and placing macro cells of the queue according to scores of the macro cells in the queue.

### Claim 2 (depends on 1)

The method of claim 1, before the corner-stitching-based macro legalization, further comprising the following steps:
determining and allocating a placement region on a chip; and
generating a plurality of empty tiles that occupy empty space not covered by a pre-placed cell.

### Claim 3 (depends on 2)

The method of claim 2, wherein the corner-stitching-based macro legalization comprises the following steps:
enumerating the tiles within the placement region;
trimming down regions of the tiles exceeding a boundary of the placement region;
packing the macro cell to be placed into corners of each trimmed tile if a dimension of the macro cell is not greater than the tile;
evaluating respective packing costs of the macro cell packed in corners; and
placing the macro cell according to the packing costs.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
enlarging the placement region if no tile can accommodate the macro cell.

### Claim 5 (depends on 2)

The method of claim 2, wherein the placement region is determined by recursive partition algorithm.

### Claim 6 (depends on 2)

The method of claim 2, wherein horizontal boundaries of the tiles are extended from horizontal boundaries of adjacent pre-placed cell.

### Claim 7 (depends on 1)

The method of claim 1, wherein a score function utilized to generate the score is a function of wirelength associated with the macro cell to be refined, distance between the macro cell to be refined and gravity of a macro group to which to the macro cell to be refined belongs, and a sequence number of iterations for refining the macro group.

### Claim 8 (depends on 7)

The method of claim 7, wherein the score function comprises a term used to adjust the score to a larger value such that the normalized score may be greater than the random number more probably.

### Claim 9 (depends on 7)

The method of claim 7, wherein the gravity of the macro group is determined after each iteration.

### Claim 10 (depends on 7)

The method of claim 7, wherein the larger the sequence number is, the less influence said distance has on the score.

### Claim 11 (depends on 7)

The method of claim 7, wherein the score function is expressed as follows:
F
i
=
{
Q
if
⁢
⁢
D
=
0
Q
+
λ
D
*
log
⁡
(
k
+
1
)
otherwise
⁢
⁢
Q
=
W
+
D
where D represents said distance, W represents the wirelength, λ is a user-specified number, k is a sequence number of iterations, and log represents a logarithm function.