Method and system for removing hardware design overlap

Claim 3

The method of claim 1 wherein said step of assigning cells to free blocks includes the step of moving cells from a left side of a right free block to a right side of a left free block thereby maintaining the relative ordering of the cells.

Claim 4

The method of claim 1 wherein said step of assigning cells to free blocks includes the step of moving cells from a right side of a left free block to a left side of a right free block thereby maintaining the relative ordering of the cells.

Claim 5

The method of claim 1 wherein said step of assigning cells to free blocks includes the steps of: choosing a first free block having overlap; identifying a closest free block having available space to accommodate the overlap; and beginning with said first free block and working toward the free block with the available space, shifting cells between intervening blocks until no overlap exists.

Claim 6

The method of claim 4 wherein the closest free block having available space to accommodate the overlap is a closest combination of free blocks having available space to accommodate the overlap.

Claim 7

The method of claim 1 wherein said partition is a horizontal row.

Claim 8

The method of claim 1 wherein said partition is a vertical row.

Claim 11

The method of claim 8 wherein said step of reassigning cells amongst the free blocks includes the steps of: unplacing all of the cells residing in free blocks; defining a positional relationship of all of said cells residing in free blocks; and processing the cells residing in free blocks using the steps of: assigning each unplaced cell to a nearest free block; identifying each free block having over-capacity; and eliminating overlap by moving cells, as needed, between adjacent free blocks while maintaining the same relative ordering of cells within the partition.

Claim 12

The method of claim 8 wherein said step of assigning cells within each free block includes implementing a recursive division algorithm that recursively divides each free block into a pair of smaller blocks and then shifts cells, as needed, from a first smaller block having over-capacity to a second smaller block having under-capacity.

Claim 13

The method of claim 8 wherein said step of assigning cells utilizes a first assignment method if demand is less than a predetermined percentage of capacity, a second reassignment method if demand is greater than said predetermined percentage of capacity and a third reassignment method if demand exceeds capacity.

Claim 14

The method of claim 8 wherein said said partition is a row of cells.

Claim 15

A computer system for removing hardware overlap comprising: a central processing unit; a bus; a computer system memory, said computer system memory being connected to said central processing unit via said bus; a process wherein said process is executable by said central processing unit, said process including: means for identifying each of a plurality of free blocks and fixed blocks in a device floor plan, wherein free blocks are areas of space which are stationary; means for identifying each of a plurality of cells within said plurality of free blocks; means for identifying overlap within said plurality of free blocks; means for shifting cells between adjacent free blocks in order to eliminate over-capacity in each of said free blocks while maintaining the same relative ordering among free block cells; and means for assigning cells within each of said free blocks.

Claim 16

A computer system for removing hardware overlap comprising: a central processing unit; a bus; a computer system memory, said computer system memory being connected to said central processing unit via said bus; a process wherein said process is executable by said central processing unit, said process including: means for identifying each of a plurality of free blocks and fixed blocks in a device floor plan, wherein free blocks are areas of space which are stationary; means for identifying each of a plurality of cells within said plurality of free blocks; means for identifying overlap within said plurality of free blocks; means for shifting cells between adjacent free blocks in order to eliminate over-capacity in each of said free blocks while maintaining the same relative ordering among free block cells; and means for assigning cells within each of said free blocks.

Claim 17

The computer system of claim 13 wherein said plurality free blocks and fixed in place blocks are partitioned into rows.

Claim 18

The computer system of claim 14 wherein said means for shifting cells between adjacent free blocks operates row by row.

Claim 19

The method of claim 13 wherein said means for assigning cells within each of said free blocks includes recursively dividing the free block into two smaller blocks and, for the case wherein a first smaller block includes over-capacity and a second smaller block includes under-capacity moving cells from said first smaller block having over-capacity to said second smaller block that has under-capacity.

Claim 22

The method of claim 17 wherein said cells that are moved out of said first smaller block having over-capacity and into said second smaller block having under-capacity are moved only a minimum distance necessary to eliminate over-capacity in said first smaller block.

Claim 23

The method of claim 17 wherein said moving of cells out of said first smaller block having over-capacity and into said second smaller block having under-capacity is done in a manner such that the same relative ordering of cells within the block is maintained.

Claim 24

The method of claim 17 wherein said step of stopping the recursive dividing occurs when the available space within the free block exactly matches the demand.

Claim 25

The method of claim 20 wherein said step of assigning cells is accomplished by brickwalling the cells in the order induced by the target placement.

Claim 26

The method of claim 17 wherein said step of stopping the recursive dividing occurs when only one cell is left in the free block.

Claim 27

The method of claim 22 wherein said step of assigning cells is accomplished by leaving the lone cell where it resides within its block.

Claim 28

A program product for processing a free block that includes adequate space for its demand, said system comprising: a recordable media; a computer program stored on said recordable media, said computer program including: means for recursively dividing the free block into two smaller child blocks, wherein the free block is an area of space which is stationary; means for moving at least one cell from a first smaller child block having over-capacity to a second smaller child block having under-capacity; means for stopping said recursive dividing upon a predetermined condition; and means for assigning said cells to their new locations.

Claim 29

A program product for processing a free block that includes adequate space for its demand, said system comprising: a recordable media; a computer program stored on said recordable media, said computer program including: means for recursively dividing the free block into two smaller child blocks, wherein the free block is an area of space which is stationary; means for moving at least one cell from a first smaller child block having over-capacity to a second smaller child block having under-capacity; means for stopping said recursive dividing upon a predetermined condition; and means for assigning said cells to their new locations.