Efficient multiprocessing for cell placement of integrated circuits

A method of using multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said method comprising the steps:

• a. dividing the core area into a plurality of regions, each of said regions containing a plurality of cells, and each of said regions being adjacent to one or more of surrounding regions of similar size;
• b. creating, for each of said regions, a list of cells belonging to said region;
• c. creating a non-adjacent set of regions from said plurality of regions wherein said non-adjacency is met when a first region and a second region is separated by a third region;
• d. assigning said regions belonging to said non-adjacent set to the multiple processors, one region per processor;
• e. processing said cells of each of said regions belonging to said non-adjacent set;
• and
• f. updating said lists of cells for each of said regions.

A method of using multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said method comprising the steps:

• a. dividing the core area into rectangular regions of M columns and N rows, each of said rectangular regions being designated R.sub.i,j where a column index i, having a value, represents the i.sup.th column and row index j, having a value, represents the j.sup.th row;
• b. choosing a first parameter KX having a value;
• c. choosing a second parameter KY having a value;
• d. creating a sequence, having, as elements, said rectangular regions R.sub.i,j, by:
• i. assigning value of 1 to a first index p;
• ii. assigning value of 1 to a second index q;
• iii. assigning said value of said p to said i;
• iv. assigning said value of said q to said j;
• v. assigning rectangular area R.sub.i,j as the next element of said sequence;
• vi. incrementing value of said j by value of said KY;
• vii. repeating steps v and vi until value of said j is greater than value of said N;
• viii. incrementing value of said i by value of said KX;
• ix. repeating steps iv to viii until value of said i is greater than value of said M;
• x. incrementing value of said q by 1;
• xi. repeating steps iii to x until value of said q is greater than value of said KY;
• xii. incrementing value of said p by 1;
• xiii. repeating steps ii to xii until value of said q is greater than value of said KY;
• and
• e. assigning said rectangular regions to each of the multiple processors according to said sequence.

A computer storage medium containing instructions using multiple processors to achieve a cell placement layout of a core area of an integrated circuit, said method comprising the steps:

• dividing the core area into a plurality of regions, each of said regions containing a plurality of cells, and each of said regions being adjacent to one or more of surrounding regions of similar size;
• creating, for each of said regions, a list of cells belonging to said region;
• creating a non-adjacent set of regions from said plurality of regions wherein said non-adjacency is met when a first region and a second region is separated by a third region;
• assigning said regions belonging to said non-adjacent set to the multiple processors, one region per processor;
• processing said cells of each of said regions belonging to said non-adjacent set;
• and
• updating said lists of cells for each of said regions.

An apparatus for placing cells on an integrated circuit chip, said apparatus comprising:

• a. a plurality of processors;
• b. memory connected to said processors;
• and
• c. said memory having instructions for said processors to divide the area of said circuit chip into a plurality of similarly sized regions and to successively assign non-adjacent regions to said processors for said processors to place the cells onto said circuit chip wherein said non-adjacency is met when a first region and a second region is separated by a third region.

A cell placement system comprising:

• a. an integrated circuit chip having surface area;
• b. a computer having memory and a plurality of processors;
• and
• c. said memory storing instructions for said processors to divide the area of said circuit chip into a plurality of similarly sized regions and successively assign non-adjacent regions to said processors for said processors to place the cells onto said circuit chip wherein said non-adjacency is met when a first region and a second region is separated by a third region.