Back to results
US 6,665,851 B1Granted
Quick placement of electronic circuits using orthogonal one dimensional placements
AssigneeSynopsys, Inc.
InventorsRoss A. Donelly, William C. Naylor
Life of this patent
Estimating the term…
Abstract
A method and system for the quick placement of electronic circuits using orthogonal one dimensional placements. All circuits of a design may be placed in a linear dimension to obtain a first placement. Next, those same circuits may be placed in a second linear dimension, orthogonal to the first dimension, in order to obtain a second placement. Finally, a two dimensional placement for the circuits may be created by selecting for each circuit element a first coordinate from the first placement and a second coordinate from the second placement.
Claims27
A method for placing electronic circuits, the method comprising:
- a) placing said circuits in a first linear dimension to obtain a first placement;
- b) placing said circuits in a second linear dimension to obtain a second placement, wherein said second linear dimension is orthogonal to said first linear dimension;
- and
- c) assigning a two dimensional placement for said circuits by selecting for each circuit element a first coordinate from said first placement and a second coordinate from said second placement,
- wherein placing said circuits in said first linear dimension and said second linear dimension include assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval is a desired length of placement.
2 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- and
- c) placing remaining cells in available positions along said interval.
1 more element
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- and
- c) placing remaining cells alternately in an available positions nearest to said beginning of said interval and alternately in an available position nearest to said end of said interval.
1 more element
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- c) placing remaining cells in available positions along said interval;
- d) organizing said remaining cells into a priority queue;
- and
- e) selecting one of said remaining cells from said priority queue.
3 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- and
- c) placing remaining cells in available positions along said interval,
- wherein said c) comprises:
- c1) organizing said remaining cells into a first priority queue, a second priority queue and an unattached list;
- c2) selecting one of said remaining cells from selectively said first priority queue, said second priority queue and said unattached list;
- and
- c3) placing said one of said remaining cells in an available position nearest to said beginning of said interval if said one of said remaining cells was selected from said first priority queue, placing said one of said remaining cells in an available position nearest to said end of said interval if said one of said remaining cells was selected from said second priority queue, and placing said one of said remaining cells in available position selectively in an available position nearest to said beginning of said interval and in an available position nearest to said end of said interval if both said first priority queue and said second priority queue are empty, wherein said placing results in a fixed cell.
6 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- c) placing remaining cells in available positions along said interval;
- and
- d) assigning a pull direction to a net attached to one of said fixed cells.
2 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- c) placing remaining cells in available positions along said interval;
- and
- d) assigning a pull value to a net attached to one of said remaining cells.
2 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) assigning a linear length to each cell proportional to its cell area and scaled by a constant factor, wherein the sum of all said lengths is an interval, and wherein said interval has a beginning and an end;
- b) placing fixed cells at the linear location of their fixing ports;
- c) placing remaining cells in available positions along said interval;
- d) dividing said interval into a first interval and a second interval;
- e) computing a pull value for a net attached to one of said remaining cells;
- f) assigning a pull direction to said pull value as low pull if said net is attached to one of said fixed cells located within said first interval;
- and
- g) assigning a pull direction to said pull value as high pull if said net is attached to one of said fixed cells located within said second interval.
5 more elements
A method of placing electronic circuits in one dimension, the method comprising:
- a) placing cells in one dimension to produce a first placement;
- b) moving cells in said first placement to improve wire length, wherein said moving produces a new placement;
- and
- c) creating a data structure for determining the number of wires crossing a point in said new placement.
1 more element
A method of placing electronic circuits in one dimension, the method comprising:
- a) placing cells in one dimension to produce a first placement;
- b) clustering cells to form a super cell;
- and
- c) moving cells in said first placement to improve wire length, wherein said moving produces a new placement,
- wherein said b) comprises:
- b1) calculating the number of wires passing through every point in said first placement;
- b2) initializing a current range value to be empty;
- b3) beginning at the cell at the beginning of the placement interval;
- b4) adding the number of wires passing through said cell to said current range value;
- b5) finding the best cut point within a span of said current range value;
- b6) recording said best cut point as a final cut point and setting the current range value to be empty;
- and
- b7) moving to the next cell and repeating said b4) through b7).
10 more elements
Dependencies are inferred from the claim text.