Placement and routing on a circuit

Abstract

Methods and apparatuses to place and route cells on integrated circuit chips along paths is described. In one embodiment, the method to layout an integrated circuit, the method comprises routing a wire to connect a first cell of the integrated circuit and a second cell of the integrated circuit, and placing a third cell of the integrated circuit after said routing the wire to connect the first cell and the second cell.

We claim: 
     
         1 . A method to layout an integrated circuit, the method comprising:
 routing a wire to connect a first cell of the integrated circuit and a second cell of the integrated circuit; and   placing a third cell of the integrated circuit after said routing the wire to connect the first cell and the second cell.   
     
     
         2 . The method of  claim 1 , wherein the first, the second and the third cells are on a first path. 
     
     
         3 . The method of  claim 2 , wherein the third cell is connected to one of the first and second cells on the first path by only one net. 
     
     
         4 . The method of  claim 3 , further comprising:
 selecting the first path from a set of paths; and   placing the first and second cells before the routing the wire to connect the first cell and the second cell.   
     
     
         5 . The method of  claim 4 , further comprising:
 analyzing timing using a route of the wire connecting the first cell and the second cell to generate first timing information;   selecting a second path from the set of paths from a timing analysis using the first timing information; and   placing a cell on the second path.   
     
     
         6 . The method of  claim 3 , wherein the placing of the third cell comprises:
 determining whether or not the third cell is previously placed; and   relocating the third cell in response to a determination that:
 the third cell is previously placed on a third path, 
 the third cell is one of a converging point and a diverging point of the first path and the third path, and 
 the third cell has positive slack. 
   
     
     
         7 . The method of  claim 1 , wherein the placing of the third cell comprises:
 determining wire delays for placing the third cell at a plurality of locations; and   selecting a first location from the plurality of locations for the third cell according to timing based on the wire delays.   
     
     
         8 . The method of  claim 7 , wherein the first location results in one or more of:
 a lowest routing congestion and slack larger than a threshold, for the third cell among the plurality of locations; and   a largest slack for the third cell among the plurality of locations.   
     
     
         9 . A machine readable medium containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method to layout an integrated circuit, the method comprising:
 routing a wire to connect a first cell of the integrated circuit and a second cell of the integrated circuit; and   placing a third cell of the integrated circuit after said routing the wire to connect the first cell and the second cell.   
     
     
         10 . The medium of  claim 9 , wherein the first, the second and the third cells are on a first path. 
     
     
         11 . The medium of  claim 10 , wherein the third cell is connected to one of the first and second cells on the first path by only one net. 
     
     
         12 . The medium of  claim 11 , wherein the method further comprises:
 selecting the first path from a set of paths; and   placing the first and second cells before said routing the wire to connect the first cell and the second cell.   
     
     
         13 . The medium of  claim 12 , wherein the method further comprises:
 analyzing timing using a route of the wire connecting the first cell and the second cell to generate first timing information;   selecting a second path from the set of paths from a timing analysis using the first timing information; and   placing a cell on the second path.   
     
     
         14 . The medium of  claim 11 , wherein said placing the third cell comprises:
 determining whether or not the third cell is previously placed; and   relocating the third cell in response to a determination that: the third cell is previously placed on a third path, the third cell is one of a converging point and a diverging point of the first path and the third path, and the third cell has positive slack.   
     
     
         15 . The medium of  claim 19 , wherein said placing the third cell comprises:
 determining wire delays for placing the third cell at a plurality of locations; and   selecting a first location from the plurality of locations for the third cell according to timing based on the wire delays.   
     
     
         16 . The medium of  claim 15 , wherein the first location results in one or more of:
 a lowest routing congestion and a slack larger than a threshold for the third cell among the plurality of locations, and   a largest slack for the third cell among the plurality of locations.   
     
     
         17 . A digital processing system to layout an integrated circuit, the digital processing system comprising:
 means for routing a wire to connect a first cell of the integrated circuit and a second cell of the integrated circuit; and   means for placing a third cell of the integrated circuit after the wire is routed to connect the first cell and the second cell.   
     
     
         18 . The digital processing system of  claim 17 , wherein the first, second and third cells are on a first path, the system further comprising:
 means for selecting the first path from a set of paths; and   means for placing the first and second cells before the wire is routed to connect the first cell and the second cell.   
     
     
         19 . The digital processing system of  claim 18 , further comprising:
 means for analyzing timing using a route of the wire connecting the first cell and the second cell to generate first timing information;   means for selecting a second path from the set of paths from a timing analysis using the first timing information; and   means for placing a cell on the second path.   
     
     
         20 . The digital processing system of  claim 19 , wherein the means for placing the third cell comprises one or more of:
 means for determining whether or not the third cell is previously placed, and means for relocating the third cell in response to a determination that: the third cell is previously placed on a third path, the third cell is one of a converging point and a diverging point of the first path and the third path, and the third cell has positive slack; and   means for determining wire delays for placing the third cell at a plurality of locations and means for selecting a first location from the plurality of locations for the third cell according to timing based on the wire delays.   
     
     
         21 . The digital processing system of  claim 20  wherein the first location results in one or more of:
 a lowest routing congestion and a slack larger than a threshold for the third cell among the plurality of locations; and 
 a largest slack for the third cell among the plurality of locations.