Method for eliminating routing congestion in an IC layout
First Claim
1. A method for eliminating routing congestion in an integrated circuit (IC) layout for an IC to be fabricated, wherein a placement plan specifies a position within the layout for each of a plurality of cells that are be included in the IC, and wherein the cells are to be interconnected by nets routed in accordance with a routing plan, the method comprising the steps of:
- a. selecting one of the cells and a target position therefor;
b. selecting a target area at a portion of the layout such that if the placement plan were to be revised to specify that the selected cell is to be positioned anywhere within the target area, the revision to the placement plan would reduce an amount of space within the layout that the routing plan must allocate to the nets to be connected to that cell, the target area being peripherally defined about the target position by a boundary selectively set for the selected cell;
c. dividing the target area into an array of blocks delineated therein, wherein each block spans a separate portion of the target area, and wherein each block includes cell space for accommodating cells and routing space for accommodating nets;
d. selecting one of the blocks having an estimated amount of unoccupied cell space sufficient to accommodate the selected cell; and
e. revising the placement plan so that it specifies that the selected cell is to be positioned within the selected block.
2 Assignments
0 Petitions
Accused Products
Abstract
The invention relates to a method for eliminating routing congestion in an integrated circuit (IC) layout defined by a placement plan indicating a position within the layout of each cell forming the IC and routing plan describing routes followed by nets interconnecting the cells. Routing congestion is eliminated by estimating routing congestion in various areas of the layout and relocating each cell to least routing congested areas of the layout for which cell relocation results in a reduction in the total lengths of the nets connected to the cell that exceeds a predetermined minimum reduction.
-
Citations
36 Claims
-
1. A method for eliminating routing congestion in an integrated circuit (IC) layout for an IC to be fabricated, wherein a placement plan specifies a position within the layout for each of a plurality of cells that are be included in the IC, and wherein the cells are to be interconnected by nets routed in accordance with a routing plan, the method comprising the steps of:
-
a. selecting one of the cells and a target position therefor; b. selecting a target area at a portion of the layout such that if the placement plan were to be revised to specify that the selected cell is to be positioned anywhere within the target area, the revision to the placement plan would reduce an amount of space within the layout that the routing plan must allocate to the nets to be connected to that cell, the target area being peripherally defined about the target position by a boundary selectively set for the selected cell; c. dividing the target area into an array of blocks delineated therein, wherein each block spans a separate portion of the target area, and wherein each block includes cell space for accommodating cells and routing space for accommodating nets; d. selecting one of the blocks having an estimated amount of unoccupied cell space sufficient to accommodate the selected cell; and e. revising the placement plan so that it specifies that the selected cell is to be positioned within the selected block. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for generating a layout for an IC formed by cells interconnected by nets, the layout comprising a detailed placement plan specifying the position each cell is to occupy in the layout and a detailed routing plan specifying a route each net is to follow when interconnecting the cells, the method comprising the steps of:
-
a. generating a global placement plan specifying an approximate position of each cell within the layout; b. generating a first trial routing plan specifying an approximate route each net is to follow within the layout; c. selecting each one of the cells referenced in the global placement plan and a target position therefor; d. selecting a first target area of the layout such that if the global placement plan were to be revised to specify that the selected cell is to be positioned anywhere with the first target area, such revision to the global placement plan would reduce an amount of space within the layout that must be allocated to the nets to be connected to the selected cell, the target area being peripherally defined about the target position by a boundary selectively set for the selected cell; e. organizing the target area into a first array of blocks, wherein each block of the first array spans a separate portion of the first target area, and wherein each block of the first array includes cell space for holding cells and routing for holding nets; f. selecting one of the blocks having an estimated amount of unoccupied cell space sufficient to hold the selected cell; and g. revising the global placement plan to produce a revised global placement plan specifying that the selected cell is to be positioned within the block selected at step f. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. Computer readable media containing software which when read and executed by a computer causes the computer to carry out a method for eliminating routing congestion in an integrated circuit (IC) layout for an IC to be fabricated, wherein a placement plan specifies a position within the layout for each of a plurality of cells that are to be included in the IC, and wherein the cells are to be interconnected by nets within the IC routed within the layout in accordance with a routing plan, wherein the method comprising the steps of:
-
a. selecting one of the cells and a target position therefor; b. selecting a target area of the layout such that if the placement plan were to be revised to specify that the selected cell is to be positioned anywhere within the target area, the revision to the placement plan would reduce an amount of space within the layout that the routing plan must allocate to the nets to be connected to that cell, the target area being peripherally defined about the target position by a boundary selectively set for the selected cell; c. organizing the target area into an array of blocks, wherein block spans a separate portion of the target area, and wherein each block includes cell space for accommodating cells and routing space for accommodating nets; d. selecting one of the blocks having an estimated amount of unoccupied cell space sufficient to accommodate the selected cell; and e. revising the placement plan so that it specifies that the selected cell is to be positioned within the selected block. - View Dependent Claims (19, 20, 21, 22, 23, 24)
-
-
25. Computer readable media storing software which when read and executed by a computer causes the computer to cany out a method for generating a layout for an IC formed by cells interconnected by nets, the layout comprising a detailed placement plan specifying the position each cell is to occupy in the layout and a detailed routing plan specifying a route each net is to follow when interconnecting the cells, the method comprising the steps of:
-
a. generating a global placement plan specifying an approximate position of each cell within the layout; b. generating a first trial routing plan specifying an approximate route each net is to follow within the layout; c. selecting one of the cells referenced in the global placement plan and a target position therefor; d. selecting a first target area of the layout such that if the global placement plan were to be revised to specify that the selected cell is to be positioned anywhere within the first target area, such revision to the global placement plan would reduce an amount of space within the layout that must be allocated to the nets to be connected to the selected cell, the first target area being peripherally defined about the target position by a boundary selectively set for the selected cell; e. organizing the target area into a first array of blocks, wherein each block of the first array spans a separate portion of the first target area and wherein each block of the first array includes cell space for holding cells and routing space for holding nets; f. selecting one of the blocks having an estimated amount of unoccupied cell space sufficient to hold the selected cell; and g. revising the global placement plan to produce a revised global placement plan specifying that the selected cell is to be positioned within the block selected at step f. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method for eliminating routing congestion in an integrated circuit (IC) layout defined by a placement plan specifying a position within the layout of each cell forming the IC and routing plan describing routes followed by nets interconnecting the cells, the method comprising the steps of:
-
a. estimating routing congestion in selected areas of the layout based on the routing plan, and selecting respective target positions for cells to be repositioned; and b. revising the placement plan to reposition cells to respective vacant areas within least routing congested ones of selected target areas of the layout for which cell relocation results in a reduction in the total lengths of the nets connected to the cell that exceeds a predetermined minimum reduction, whereby the revision would reduce an amount of space within the layout that the routing plan must allocate to the nets to be connected to the repositioned cells, the target areas each being peripherally defined about a corresponding one of the target positions by a boundary selectively set for the selected cell therefor.
-
-
36. Computer readable media containing software which when read and executed by a computer causes the computer to carry out a method for eliminating routing congestion in an integrated circuit (IC) layout defined by a placement plan specifying a position within the layout of each cell forming the IC and routing plan describing routes followed by nets interconnecting the cells, wherein method comprising the steps of:
-
a. estimating routing congestion in selected areas of the layout based on the routing plan, and selecting respective target positions for cells to be repositioned; and b. revising the placement plan to reposition cells within least routing congested ones of selected target areas of the layout for which cell relocation results in a reduction in the total lengths of the nets connected to the cell that exceeds a predetermined minimum reduction. whereby the revision would reduce an amount of space within the layout that the routing plan must allocate to the nets to be connected to the repositioned cells, the target areas each being peripherally defined about a corresponding one of the target positions by a boundary selectively set for the selected cell therefore.
-
Specification