Method and system for removing hardware design overlap
First Claim
Patent Images
1. A method for removing hardware design overlap after an initial target location for each cell has been determined, said method comprising the steps of:
- identifying all fixed blocks and free blocks in each of a plurality of circuit partitions, wherein free blocks are areas of space which are stationary, and wherein free blocks are available to hold cells that are moveable;
identifying all free blocks having overlap;
removing overlap for each partition having free blocks with overlap, by performing the steps of;
identifying free blocks with available space; and
assigning cells to new free blocks to utilize said available free space while maintaining the same relative cell ordering within the partition and also minimizing the distance from said initial target location to said new free block.
3 Assignments
0 Petitions
Accused Products
Abstract
Disclosed is a method and system for removing hardware overlap for use with a computer aided design apparatus. The method and system remove overlap by separately classifying all free blocks and blocks fixed in place, and then shifting cells between free blocks while maintaining the same relative ordering of the cells. Thus, all move bounds are respected and only cells that exist in free blocks actually move. The operation takes place one partition at a time, whereby a typical partition includes a row of cells.
37 Citations
24 Claims
-
1. A method for removing hardware design overlap after an initial target location for each cell has been determined, said method comprising the steps of:
-
identifying all fixed blocks and free blocks in each of a plurality of circuit partitions, wherein free blocks are areas of space which are stationary, and wherein free blocks are available to hold cells that are moveable; identifying all free blocks having overlap; removing overlap for each partition having free blocks with overlap, by performing the steps of; identifying free blocks with available space; and assigning cells to new free blocks to utilize said available free space while maintaining the same relative cell ordering within the partition and also minimizing the distance from said initial target location to said new free block. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of removing residual cell overlap after cells have been assigned during a floor planning to an initial target location, said method including the steps of:
-
choosing a partition of cells within a floor plan; identifying all free blocks and fixed blocks within said partition, wherein free blocks are areas of space which are stationary, and wherein free blocks are available to hold cells that are moveable; reassigning cells amongst the free blocks in said partition to eliminate any over-capacity occurring in any of said free blocks while maintaining the same relative cell ordering within the partition; and assigning cells within each free block in a manner that will eliminate any overlap occurring within each of said free blocks while minimizing perturbation from the initial target location. - View Dependent Claims (9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16)
-
-
17. A method of providing an overlap-free placement of cells within a free block while minimizing perturbation wherein said free block includes adequate space for demand, wherein said free block is an area of space that is stationary, said method including the steps of:
-
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; stopping the recursive dividing of the block upon reaching a predetermined condition; and assigning cells to their new target locations. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
-
24. 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.
-
Specification