US5557533A — Cell placement alteration apparatus for integrate…

Claim 1

Independent Claim 268 words

A cell placement alteration apparatus for an integrated circuit chip physical design automation system, comprising: a memory for storing a first cell placement as including cell locations on the chip, cells allocated to said cell locations and fitnesses of said cells respectively; a transposition processor for performing a predetermined cell transposition operation on said first cell placement to produce a second cell placement, and storing said second cell placement in the memory; and a selection processor for selecting cells for transposition by the transposition processor such that a probability of each cell being selected is a predetermined function of said fitness of said each cell respectively, in which: the selection processor sorts and ranks said cells in increasing order of fitness and multiplies said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively; said predetermined function of said fitness is such that said probability of said each cell being selected is substantially linearly proportional to said weighted fitness of said each cell respectively; the selection processor computes a weighted fitness summation for said each cell as being substantially equal to the sum of said weighted fitness of said each cell and said weighted fitnesses of said cells having lower fitnesses than said each cell respectively; and the selection processor further comprises: a random number generator for generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for said first cell placement; and a selector for selecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number.

Claim 2

Dependent Claim 268 words

A cell placement alteration apparatus for an integrated circuit chip physical design automation system, comprising: a memory for storing a first cell placement as including cell locations on the chip, cells allocated to said cell locations and fitnesses of said cells respectively; a transposition processor for performing a predetermined cell transposition operation on said first cell placement to produce a second cell placement, and storing said second cell placement in the memory; and a selection processor for selecting cells for transposition by the transposition processor such that a probability of each cell being selected is a predetermined function of said fitness of said each cell respectively, in which: the selection processor sorts and ranks said cells in increasing order of fitness and multiplies said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively; said predetermined function of said fitness is such that said probability of said each cell being selected is substantially linearly proportional to said weighted fitness of said each cell respectively; the selection processor computes a weighted fitness summation for said each cell as being substantially equal to the sum of said weighted fitness of said each cell and said weighted fitnesses of said cells having lower fitnesses than said each cell respectively; and the selection processor further comprises: a random number generator for generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for said first cell placement; and a selector for selecting a cell for transposition which has a weighted fitness summation that is substantially equal to said random number.

Claim 3

Dependent Claim 70 words

An apparatus as in claim 1, in which the selection processor computes said weighted fitness for said each cell as substantially V 1 =F 1 ξ i , where i is a rank of said each cell in increasing order of fitness, ξ is a predetermined value, V 1 is said weighted fitness, F 1 is said fitness and ξ 1 are said weighting factors of said each cell respectively.

Claim 4

Dependent Claim 57 words

An apparatus as in claim 1, in which: said predetermined cell transposition operation comprises genetic crossover; the memory further stores a third cell placement; the selection processor selects first and second cells in said first and third cell placements respectively for transposition; and the transposition processor performs said transposition operation by transposing said first and second cells.

Claim 5

Dependent Claim 28 words

An apparatus as in claim 3, in which the selection processor selects said first cell as having a lowest fitness among said cells in said first cell placement.

Claim 6

Dependent Claim 28 words

An apparatus as in claim 3, in which the selection processor selects said first cell as having a highest fitness among said cells in said first cell placement.

Claim 7

Dependent Claim 47 words

An apparatus as in claim 3, in which the selection processor selects said first cell in accordance with a predetermined fitness criteria and selects said second cell as having a same location in said second cell placement as said first cell has in said first cell placement.

Claim 8

Dependent Claim 47 words

An apparatus as in claim 1, in which: said predetermined cell transposition operation comprises genetic mutation; the selection processor selects first and second cells in said first cell placement respectively for transposition; and the transposition processor performs said transposition operation by transposing said first and second cells.

Claim 9

Dependent Claim 28 words

An apparatus as in claim 7, in which the selection processor selects said first cell as having a lowest fitness among said cells in said first cell placement.

Claim 10

Dependent Claim 28 words

An apparatus as in claim 7, in which the selection processor selects said first cell as having a highest fitness among said cells in said first cell placement.

Claim 11

Dependent Claim 28 words

An apparatus as in claim 7, in which the selection processor selects said first cell in accordance with a predetermined fitness criteria and selects said second cell randomly.

Claim 12

Dependent Claim 32 words

An apparatus as in claim 7, the selection processor selects said first cell in accordance with a predetermined fitness criteria and selects said second cell as being adjacent to said first cell.

Claim 13

Dependent Claim 38 words

An apparatus as in claim 7, in which the selection processor selects said first cell as having a lowest fitness and said second cell as having a second lowest fitness among said cells in said first cell placement.

Claim 14

Dependent Claim 46 words

An apparatus as in claim 7, in which the selection processor selects said first cell in accordance with a predetermined fitness criteria and selects said second cell as being at substantially a center of mass of an interconnection net to which said first cell is connected.

Claim 15

Dependent Claim 50 words

An apparatus as in claim 1, in which: said predetermined cell transposition operation comprises genetic mutation; the selection processor selects first, second and third cells in said first cell placement respectively for transposition; and the transposition processor performs said transposition operation by cyclically transposing said first, second and third cells.

Claim 16

Dependent Claim 33 words

An apparatus as in claim 14, in which the selection processor selects said first, second and third cells as having lowest, second lowest and third lowest fitnesses in said first cell placement respectively.

Claim 17

Dependent Claim 51 words

An apparatus as in claim 15, in which the transposition processor transposes said first cell into a location of said first cell, transposes said second cell into a location of said third cell and transposes said third cell into a location of said first cell in said first cell placement respectively.

Claim 18

Dependent Claim 70 words

An apparatus as in claim 14, in which the transposition processor selects said first cell as having a lowest fitness among said cells of the first cell placement, selects said second cell as having a lowest fitness among cells that are adjacent to said first cell, and selects said third cell as having a lowest fitness among cells other than said first cell that are adjacent to said second cell.

Claim 19

Dependent Claim 51 words

An apparatus as in claim 17, in which the transposition processor transposes said first cell into a location of said first cell, transposes said second cell into a location of said third cell and transposes said third cell into a location of said first cell in said first cell placement respectively.

Claim 20

Dependent Claim 21 words

An apparatus as in claim 1, in which said fitnesses of said cells correspond to interconnect congestions of said cells respectively.

Claim 21

Dependent Claim 235 words

A permutation transposition method, comprising the steps of: (a) providing a first entity permutation including entity locations, entities allocated to said entity locations and fitnesses of said entities respectively; (b) selecting entities for transposition such that a probability of each entity being selected is a predetermined function of said fitness of said each entity respectively; and (c) performing a predetermined entity transposition operation on said first entity placement to produce a second entity placement, in which: step (b) comprises the substeps of: (d) sorting and ranking said entities in increasing order of fitness; and (e) multiplying said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively; said predetermined function of said fitness is such that said probability of said each entity being selected is substantially linearly proportional to said weighted fitness of said each entity respectively; and step (b) further comprises the substeps of: (f) computing a weighted fitness summation for said each entity as being substantially equal to the sum of said weighted fitness of said each entity and said weighted fitnesses of said entities having lower fitnesses than said each entity respectively; (g) generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for said first entity placement; and (h) selecting a entity for transposition which has a weighted fitness summation that is substantially equal to said random number.

Claim 22

Dependent Claim 235 words

A permutation transposition method, comprising the steps of: (a) providing a first entity permutation including entity locations, entities allocated to said entity locations and fitnesses of said entities respectively; (b) selecting entities for transposition such that a probability of each entity being selected is a predetermined function of said fitness of said each entity respectively; and (c) performing a predetermined entity transposition operation on said first entity placement to produce a second entity placement, in which: step (b) comprises the substeps of: (d) sorting and ranking said entities in increasing order of fitness; and (e) multiplying said fitnesses by weighting factors that increase non-linearly with cell rank to produce weighted fitnesses respectively; said predetermined function of said fitness is such that said probability of said each entity being selected is substantially linearly proportional to said weighted fitness of said each entity respectively; and step (b) further comprises the substeps of: (f) computing a weighted fitness summation for said each entity as being substantially equal to the sum of said weighted fitness of said each entity and said weighted fitnesses of said entities having lower fitnesses than said each entity respectively; (g) generating a random number having a maximum value that is substantially equal to a maximum weighted fitness summation for said first entity placement; and (h) selecting a entity for transposition which has a weighted fitness summation that is substantially equal to said random number.

Claim 23

Dependent Claim 69 words

A method as in claim 20, in which step (d) comprises computing said weighted fitness for said each entity as substantially V 1 =F 1 ξ i , where i is a rank of said each entity in increasing order of fitness, ξ is a predetermined value, V 1 is said weighted fitness, F 1 is said fitness and ξ 1 said weighting factor of said each entity respectively.

Claim 24

Dependent Claim 57 words

A method as in claim 20, in which: said predetermined entity transposition operation comprises genetic crossover; step (a) comprises further providing a third entity placement; step (b) comprises selecting first and second entities in said first and third entity placements respectively for transposition; and step (c) comprises performing said transposition operation by transposing said first and entities.

Claim 25

Dependent Claim 28 words

A method as in claim 22, in which step (b) comprises selecting said first entity as having a lowest fitness among said entities in said first entity placement.

Claim 26

Dependent Claim 28 words

A method as in claim 22, in which step (b) comprises selecting said first entity as having a highest fitness among said entities in said first entity placement.

Claim 27

Dependent Claim 47 words

A method as in claim 22, in which step (b) comprises selecting said first entity in accordance with a predetermined fitness criteria and selecting said second entity as having a same location in said second entity placement as said first entity has in said first entity placement.

Claim 28

Dependent Claim 47 words

A method as in claim 20, in which: said predetermined entity transposition operation comprises genetic mutation; step (b) comprises selecting said first and second entities in said first entity placement respectively for transposition; and step (c) comprises performing said transposition operation by transposing said first and entities.

Claim 29

Dependent Claim 28 words

A method as in claim 26, in which step (b) comprises selecting said first entity as having a lowest fitness among said entities in said first entity placement.

Claim 30

Dependent Claim 28 words

A method as in claim 26, in which step (b) comprises selecting said first entity as having a highest fitness among said entities in said first entity placement.

Claim 31

Dependent Claim 28 words

A method as in claim 26, in which step (b) comprises selecting said first entity in accordance with a predetermined fitness criteria and selecting said second entity randomly.

Claim 32

Dependent Claim 34 words

A method as in claim 26, in which step (b) comprises selecting said first entity in accordance with a predetermined fitness criteria and selecting said second entity as being adjacent to said first entity.

Claim 33

Dependent Claim 38 words

A method as in claim 26, in which step (b) comprises selecting said first entity as having a lowest fitness and said second entity as having a second lowest fitness among said entities in said first entity placement.

Claim 34

Dependent Claim 46 words

A method as in claim 26, in which step (b) comprises selecting said first entity in accordance with a predetermined fitness criteria and selecting said second entity as being at substantially a center of mass of an interconnection net to which said first entity is connected.

Claim 35

Dependent Claim 50 words

A method as in claim 20, in which: said predetermined entity transposition operation comprises genetic mutation; step (b) comprises selecting first, second and third entities in said first entity placement respectively for transposition; and step (c) comprises performing said transposition operation by cyclically transposing said first, second and third entities.

Claim 36

Dependent Claim 33 words

A method as in claim 33, in which step (b) comprises selecting said first, second and third entities as having lowest, second lowest and third lowest fitnesses in said first entity placement respectively.

Claim 37

Dependent Claim 51 words

A method as in claim 34, in which step (c) comprises transposing said first entity into a location of said first entity, transposing said second entity into a location of said third entity and transposing said third entity into a location of said first entity in said first entity placement respectively.

Claim 38

Dependent Claim 70 words

A method as in claim 33, in which step (b) comprises selecting said first entity as having a lowest fitness among said entities of the first entity placement, selecting said second entity as having a lowest fitness among entities that are adjacent to said first entity, and selecting said third entity as having a lowest fitness among entities other than said first entity that are adjacent to said second entity.

Claim 39

Dependent Claim 51 words

A method as in claim 36, in which step (c) comprises transposing said first entity into a location of said first entity, transposing said second entity into a location of said third entity and transposing said third entity into a location of said first entity in said first entity placement respectively.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-09-17	2000-03-18	2000-09-17	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-09-17	2004-03-18	2004-09-17	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-09-17	2008-03-18	2008-09-17	$7700.00	Window Closed / Lapsed

Cell placement alteration apparatus for integrated circuit chip physical design automation system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag