Advanced modular cell placement system with functional sieve optimization technique
First Claim
Patent Images
1. A method for optimizing placement of elements on a surface, wherein said elements are associated in groups, comprising the steps of:
- (a) combining a plurality of affinities for relocating said elements to alternate locations on said surface;
(b) repositioning elements based on the combined affinities;
(c) computing a cost function;
(d) repeating said combining, repositioning, and computing steps a predetermined number of times;
(e) calculating an average cost function based upon all cost functions from said iterated computing steps;
(f) subsequently repeating said combining, repositioning, computing, repeating, and calculating steps until two consecutive average cost functions satisfy a given accuracy,wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
10 Assignments
0 Petitions
Accused Products
Abstract
A system for optimizing placement of a cell on a surface of a semiconductor chip is disclosed herein. The cells may belong to nets and may belong to neighborhoods. The system initially calculates affinities based on repositioning the cell. The system then combines affinities and repositions cells based on these combined affinities. The system then computes a cost function and repeats the combining, repositioning, and computing functions a predetermined number of times.
104 Citations
19 Claims
-
1. A method for optimizing placement of elements on a surface, wherein said elements are associated in groups, comprising the steps of:
-
(a) combining a plurality of affinities for relocating said elements to alternate locations on said surface; (b) repositioning elements based on the combined affinities; (c) computing a cost function; (d) repeating said combining, repositioning, and computing steps a predetermined number of times; (e) calculating an average cost function based upon all cost functions from said iterated computing steps; (f) subsequently repeating said combining, repositioning, computing, repeating, and calculating steps until two consecutive average cost functions satisfy a given accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for optimizing placement of cells on a surface of a semiconductor chip, wherein said cells are associated in nets and belong to neighborhoods, said system comprising:
-
(a) calculating a plurality of affinities based on repositioning said cells; (b) combining said affinities; (c) repositioning cells based on combined affinities; (d) computing a cost function; and (e) repeating said combining, repositioning, and computing steps a predetermined number of times, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method for optimizing placement of elements on a surface, comprising the steps of:
-
(a) calculating affinities for repositioning elements; (b) repositioning elements based on said affinities; (c) computing a cost associated with repositioning the elements; and (d) repeating said calculating, repositioning, and computing steps until the difference between costs for two subsequent iterations satisfies a predetermined accuracy, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost relates to quality of a placement.
-
-
18. A system for optimizing placement of an element on a surface, comprising:
-
(a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
-
-
19. A computer storage device having stored thereon a computer program comprising the following steps:
-
(a) computing an affinity associated with repositioning said element; (b) repositioning said element if said affinity satisfies a specified criterion; (c) repeating said computing and repositioning steps a predetermined number of times; (d) calculating a cost function; and (e) repeating steps (a), (b), (c) and (d) until cost functions satisfy a predetermined accuracy on two subsequent iterations, wherein affinity relates to preference to place a cell in a given alternate position on a cell-by-cell basis and cost function relates to quality of a placement.
-
Specification