US6067409A — Advanced modular cell placement system

Claim 1

Independent Claim 117 words

A method for locating a plurality of elements on a surface, said method comprising the steps of: assigning the elements to portions of the surface; preplacing the elements onto the surface; repositioning the elements depending on affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises: (1) dividing the surface into a plurality of regions; (2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and (3) repositioning at least some of the elements to locations in other regions based on the affinities.

Claim 2

Independent Claim 117 words

A method for locating a plurality of elements on a surface, said method comprising the steps of: assigning the elements to portions of the surface; preplacing the elements onto the surface; repositioning the elements depending on affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises: (1) dividing the surface into a plurality of regions; (2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and (3) repositioning at least some of the elements to locations in other regions based on the affinities.

Claim 3

Dependent Claim 25 words

A method according to claim 1, wherein the elements are cells of an integrated circuit chip (IC), and the surface is surface of said IC.

Claim 4

Dependent Claim 26 words

A method according to claim 1, further comprising the step of planning the element layout on the surface prior to preplacing the elements onto the surface.

Claim 5

Dependent Claim 71 words

A method according to claim 3, wherein said step of planning the element layout comprises steps: partitioning the surface into a grid comprising a plurality of regions; defining pieces, each piece comprising at least one of said regions, and each piece having a capacity; allocating said capacity of each of said pieces to predefined groups of the elements; and reallocating said capacity of said pieces to said groups of the elements.

Claim 6

Dependent Claim 13 words

A method according to claim 1, wherein the plurality of processors operate simultaneously.

Claim 7

Dependent Claim 67 words

A method according to claim 1, wherein said step of connecting the elements comprises the steps: partitioning the elements into a plurality of sets, each set having at least a predetermined number of elements; constructing a minimal spanning tree having vertices and edges, said vertices of said spanning tree representing the elements and said sets; and connecting the elements per said edges of said minimal spanning tree.

Claim 8

Dependent Claim 40 words

A method according to claim 1, wherein a new region is assigned to each of the processors as said each processor completes its current region, and wherein at any given time the regions assigned to all the processors are non-adjacent.

Claim 9

Dependent Claim 30 words

A method according to claim 7, wherein the regions are ordered in a list and each processor selects a next unprocessed region in the list after completing its current region.

Claim 10

Dependent Claim 150 words

A computer-implemented method for locating a plurality of elements on a surface, said method comprising the steps of: forming a neighborhood defined as a set of the elements; ordering the elements within each said neighborhood according to their relative distance from a target element; preplacing the elements within a two-dimensional abstraction of the surface; iteratively subdividing the surface into a plurality of regions; assigning the elements to said plurality of regions; assigning non-adjacent regions to a plurality of processors; calculating affinities of at least some of the elements to locations in other regions using the plurality of processors, each processor determining affinities of the elements in its assigned region; repositioning at least some of the elements to other regions based on affinities of the elements; levelizing element density over the surface based on relationships between the elements; relocating any overlapping elements; and performing a final cell adjustment for element positions.

Claim 11

Dependent Claim 150 words

A computer-implemented method for locating a plurality of elements on a surface, said method comprising the steps of: forming a neighborhood defined as a set of the elements; ordering the elements within each said neighborhood according to their relative distance from a target element; preplacing the elements within a two-dimensional abstraction of the surface; iteratively subdividing the surface into a plurality of regions; assigning the elements to said plurality of regions; assigning non-adjacent regions to a plurality of processors; calculating affinities of at least some of the elements to locations in other regions using the plurality of processors, each processor determining affinities of the elements in its assigned region; repositioning at least some of the elements to other regions based on affinities of the elements; levelizing element density over the surface based on relationships between the elements; relocating any overlapping elements; and performing a final cell adjustment for element positions.

Claim 12

Dependent Claim 64 words

A computer-implemented method according to claim 9, wherein the elements are grouped into functions and the surface can be partitioned into portions, each of said portions having a capacity, and further comprising the step of assigning said groups of the elements to said portions of the surface to meet a predetermined utilization requirement of said capacity of each of said portions of the surface.

Claim 13

Dependent Claim 41 words

A computer-implemented method according to claim 9, wherein a new region is assigned to each of the processors as said each processor completes its current region, and wherein at any given time the regions assigned to all the processors are non-adjacent.

Claim 14

Dependent Claim 31 words

A computer-implemented method according to claim 11, wherein the regions are ordered in a list and each processor selects a next unprocessed region in the list after completing its current region.

Claim 15

Independent Claim 127 words

An apparatus for placing a plurality of elements on a surface, said apparatus comprising: a plurality of processors; memory connected to said processors; said memory having instructions for said processors to assign the elements to portions of the surface; to preplace the elements onto the surface; to reposition the elements depending on affinities of the elements; and to connect the elements on the surface, wherein said instructions to reposition the elements comprise instructions to: (1) divide the surface into a plurality of regions; (2) assign non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and (3) reposition at least some of the elements to locations in other regions based-on the affinities.

Claim 16

Independent Claim 127 words

An apparatus for placing a plurality of elements on a surface, said apparatus comprising: a plurality of processors; memory connected to said processors; said memory having instructions for said processors to assign the elements to portions of the surface; to preplace the elements onto the surface; to reposition the elements depending on affinities of the elements; and to connect the elements on the surface, wherein said instructions to reposition the elements comprise instructions to: (1) divide the surface into a plurality of regions; (2) assign non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions; and (3) reposition at least some of the elements to locations in other regions based-on the affinities.

Claim 17

Dependent Claim 12 words

An apparatus according to claim 13 wherein said plurality processors operate simultaneously.

Claim 18

Dependent Claim 13 words

An apparatus according to claim 13 further comprising a harddrive and a monitor.

Claim 19

Dependent Claim 14 words

An apparatus according to claim 13 wherein said apparatus is a general purpose computer.

Claim 20

Dependent Claim 23 words

An apparatus according to claim 13 wherein said elements are cells of an integrated circuit chip (IC), and said surface is the IC.

Claim 21

Dependent Claim 40 words

An apparatus according to claim 13, wherein a new region is assigned to each of the processors as said each processor completes its current region, and wherein at any given time the regions assigned to all the processors are non-adjacent.

Claim 22

Dependent Claim 30 words

An apparatus according to claim 18, wherein the regions are ordered in a list and each processor selects a next unprocessed region in the list after completing its current region.

Claim 23

Dependent Claim 127 words

A machine-readable storage medium containing instructions for a processor, said instructions comprising the steps for locating a plurality of elements on a surface and comprising the steps of: assigning the elements to portions of the surface; preplacing the elements onto the surface; repositioning the elements depending on affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises: (1) dividing the surface into a plurality of regions: (2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions and (3) repositioning at least some of the elements to locations in-other regions based on the affinities.

Claim 24

Dependent Claim 127 words

A machine-readable storage medium containing instructions for a processor, said instructions comprising the steps for locating a plurality of elements on a surface and comprising the steps of: assigning the elements to portions of the surface; preplacing the elements onto the surface; repositioning the elements depending on affinities of the elements; and connecting the elements on the surface, wherein said step of repositioning the elements is performed using a plurality of processors and comprises: (1) dividing the surface into a plurality of regions: (2) assigning non-adjacent regions to said processors, each processor determining affinities of at least some of the elements in its assigned region to locations in other regions and (3) repositioning at least some of the elements to locations in-other regions based on the affinities.

Claim 25

Dependent Claim 35 words

A storage medium according to claim 20 wherein said storage medium is selected from a group consisting of magnetic device, optical device, magneto-optical device, floppy diskette, harddrive, CD-ROM, magnetic tape, computer memory, and memory card.

Claim 26

Dependent Claim 42 words

A machine-readable storage medium according to claim 20, wherein a new region is assigned to each of the processors as said each processor completes its current region, and wherein at any given time the regions assigned to all the processors are non-adjacent.

Claim 27

Dependent Claim 32 words

A machine-readable storage medium according to claim 20, wherein the regions are ordered in a list and each processor selects a next unprocessed region in the list after completing its current region.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-05-23	2003-11-22	2004-05-23	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-05-23	2007-11-22	2008-05-23	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-05-23	2011-11-22	2012-05-23	$7700.00	Window Closed / Lapsed

Advanced modular cell placement system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag