Abstract:
Channels are routed in an integrated circuit layout by reserving grid positions for buffers. Cell pins are identified at different y-coordinates to be connected by the channel. A determination is made as to the necessity of a jog between vertical segments, and if so, a y-coordinate is assigned to each such jog. An x-coordinate is assigned to each channel segment extending across the y-coordinates. Y-coordinates are assigned to buffers to be connected to the channel.

Description:
FIELD OF THE INVENTION 
     This invention relates to integrated circuits, and particularly to routing channels in integrated circuit chips. The invention is particularly useful in connection with fabrication of integrated circuit chips whose netlist is transmitted electronically by a customer to the IC foundry. 
     BACKGROUND OF THE INVENTION 
     Integrated circuits are typically composed of cells that are defined by netlists. The netlist defines the function of the cell, timing requirements and other factors associated with the fabrication of the integrated circuit chip. In most cases, channel size and pin function are defined by the netlist, taking into account technology restrictions of the fabrication process. Consequently, when developing the netlist, the IC designer selects the size of the channel, and any specialized timing considerations (including buffers) that may be required. 
     In some cases, the IC designer may not have full knowledge of the technology restrictions in connection with the fabrication of the integrated circuit chip. It is common, for example, for equipment manufacturers to design integrated circuit chips for use in their equipment and develop netlists of those chips. The netlists are then transmitted to the IC fabricator where modifications may be necessary to accommodate proprietary technology restrictions. This often means the chip designer and fabricator must coordinate efforts to modify the designer&#39;s netlists to accommodate the technology of the fabrication. 
     One area of chip fabrication requiring close coordination between the designer and the fabrication requirements lies in the area of channel definition and timing. Considerable time and effort are directed to channel definition. Moreover, even where the designer is fully knowledgeable of fabrication restrictions, complexities of channel design often render development of netlists that include channel design to be tedious. There is, accordingly, a need for a technique that automates the channel definition and timing to alter the original netlist for meeting fabrication requirements. 
     SUMMARY OF THE INVENTION 
     The present invention provides a technique to create channel routing of a channel and to insert buffers as may be necessary to accommodate timing requirements. 
     The present invention provides a process for routing channels in an integrated circuit layout. Input are definitions of (1) a grid having first and second orthogonal coordinate types, (2) netlists, (3) a channel dimension defined by coordinated of a first type, (4) timing requirements, and (5) technology restrictions for a plurality of cells of the integrated circuit. Grid positions are reserved for buffers. Pins of a cell are identified at different coordinates of the first type, such as at different y-coordinates, to be connected by the channel. A determination is made as to the necessity of a jog between vertical segments, and if so, a coordinate of the first type, such as a y-coordinate, is assigned to each such jog. A coordinate of the second type, such as an x-coordinate, is assigned to each channel segment extending across the y-coordinates. Coordinates of the first type, such as y-coordinates, are assigned to buffers to be connected to the channel. 
     In preferred embodiments, the necessity for jogs is determined by identifying whether pins of other netlists have the same coordinates, such as y-coordinates, as two pins on opposite sides of the channel of the cell under consideration. Coordinates are assigned to channel segments in accordance with technology restrictions, such as spacing, for the channel segments and jog. 
     In other preferred embodiments, coordinates are assigned to buffers for the channel by identifying if a segment extending along the y-direction crosses a coordinate of a reserved grid. If so, a buffer is coupled to the segment. If the segment does not cross the coordinate of the reserved buffer, the segment is extended to the coordinate of the reserved buffer, and a penalty is assigned to each extended segment. The buffers and segments are ordered to minimize the total penalty. 
     According to another aspect of the invention, a computer usable medium contains a computer readable program comprising code that causes a computer to define channel routing with buffer connections. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flow chart of the process in accordance with the presently preferred embodiment of the present invention. 
     FIGS. 2-6 illustrate certain examples in connection with the process of FIG.  1 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 1, the process commences at step  10  by inputting data into a computer that will calculate the position of channels and buffers. The input data consists of the input netlist of the cells of the IC chip being fabricated, including channel height, pin allocation and timing requirements. Also input are the rules associated with technology restrictions, including grid size and spacing rules. For each pin in the netlist, a pointer identifies the net to which it belongs and the metal layer in which it is located. Pins may be on the left, right, top and bottom of the cell, and are flagged as such. For purposes of the present invention, pins to the left and right have a y-coordinate but no x-coordinate, and pins on the top and bottom edges have no coordinates. Further, no cell may have more than one pin at the top edge and one pin at the bottom edge. In most cases, the top and bottom pin(s) are in single metal layer, different from the metal layer containing the left and right pin(s), which are also usually in a single metal layer. 
     The present invention will be described with the assumption that the channel is vertical, as opposed to horizontal, that is, it extends along the y-direction, crossing the x-coordinates. Analogous input and procedures may be performed should the channel be horizontal (along the x-direction). 
     At step  12 , a test is conducted to confirm that the left and right pins are associated with one layer and that all top and bottom pins are associated with a different layer. If this is not the case, it will be necessary to create small channels around the routing channel to provide metal vias to the proper layer. For the purposes of the present invention, horizontal wires (x-direction) will be placed on the same layer as the left and the right pins, and vertical wires (y-direction) will be placed on the same layer as top and bottom pins. These assignments may be reversed, if desired. 
     At step  14 , grids are reserved for connection to buffers that will be inserted to break long vertical wires. Since the horizontal wires are on the same layer as the left and right pins, the reservation of grids for the horizontal wires is accomplished on that layer in locations where there are no pins. At step  16 , jogs and vertical segments are established for the channel. This is accomplished on a net-by-net basis by placing the pins of the nets in order, such as from bottom to top. Where two pins have different y-coordinates, at least one vertical segment will be created between them. If two or more vertical segments are necessary, one or more horizontal jogs between the vertical segments will be necessary. 
     FIGS. 2-6 illustrate five examples of locating the vertical segments. In each of FIGS. 2-6, a circle identifies the position-of a pin of the current net, a square represents the location of a free spot where a pin may be positioned, and an “X” identifies the position of a pin of another net. 
     In FIG. 2, pins  52  and  54  to be connected are both on the same side of the channel and at different y-coordinates (y 1  and y 2 , respectively), meaning that a single vertical segment  50  is adequate to interconnect the pins. In FIGS. 3,  4  and  5 , a single segment  56  (FIG.  3 ),  58  (FIG. 4) and  60  (FIG. 5) couples pin  62  (at yl coordinate) on the left side of the channel to pin  54  (at y 2  coordinate) on the right side of the channel. In FIG. 4, a segment  64  of a different net is coupled to pin  66  to the left of pin  54 . Consequently, vertical segment  58  must be to the right of segment  64  by an amount based on technology spacing rules. Similarly, in FIG. 5, segment  68  of a different net is coupled to pin  70  to the right of pin  62 , so vertical segment  60  must be to the left of segment  66  by the design amount. 
     FIG. 6 illustrates the situation of a combination of FIGS. 4 and 5 where segments  64  and  68  of other nets are to the left and right of pins  62  and  54 , respectively, of the current net. In this case, two vertical segments  72  and  74  are coupled together by jog  76  for connection between pins  62  and  54 , so that vertical segment  72  is a design distance from segment  68  and vertical segment  74  is a design distance from segment  64 . 
     An inspection of FIGS. 2-6 reveals the constraints on the placement of vertical segments in the channel. In FIGS. 2 and 3, there are no other nets that will interfere with the placement of the vertical segment, so segment  50  or  56  may be placed anywhere in the channel. However, in the case of FIG. 2, since both pins are on the same side, it is desirable to maintain the position of segment  50  as close as practical to pins  52  and  54  to minimize channel length. In the example of FIG. 6, jog  76  is necessary because pin  70  of the other net is at the same y-coordinate as pin  62  of the net under consideration, and pin  66  of another net is at the same y-coordinate as pin  52  as the net under consideration. Consequently, a jog is necessary only if the right and left pins are on opposite sides of the channel and if each has a pin of a different net on the other side of the horizontal grid line. 
     At step  18  in FIG. 1, y-coordinates are assigned to the horizontal jogs. Where a jog is necessary, as in the case of jog  76  in FIG. 6, it may be placed at the y-coordinate on any free grid that is not occupied by another pin or reserved for a buffer in step  14 . It is preferred, however, that jog  76  is placed between the y-coordinates of pins  62  and  54 : y 1 &lt;y 3 &lt;y 2 . The placement of the jog becomes an assignment problem of minimizing a penalty function based on placement of objects in boxes. 
     Treating the jogs as objects and the horizontal grid lines as boxes, the capacity of a grid line is “1” if it is a free line, that is, that has no pins and is not reserved for buffers. If the line is not free, it is assigned a “0”. The penalty is 0 if the grid line (y-coordinate) for the jog is between those of the pins (i.e., y 1 &lt;y 3 &lt;y 2 ). A penalty function is applied if the position of the y-coordinate of the jog is outside the y 1 , y 2  interval, increasing the penalty the further the jog is from the y 1 , y 2  interval. A linear function is preferred for this penalty. 
     The penalty functions are summed, and the y coordinates of all jogs may be altered to minimize the overall penalty. 
     At step  20 , x coordinates are assigned to the vertical segments. The vertical segments are defined as “left”, “right” or “either”. A “left” segment is one that is to the left of some other segment. Segments  50  and  60  in FIGS. 2 and 5 are “left” segments. A “right” segment is one that is to the right of some other segment. Segment  58  in FIG. 4 is a “right” segment. An “either” segment is one that creates no potential conflict with another segment. In FIG. 6, segment  72  is a “left” segment and segment  74  is a “right” segment. 
     The x-coordinates of the vertical segments are identified by sorting the segments to deal with one or the other of “left” and “right” segments, followed by “either” segments and then followed by the other of “right” and “left”. Treating “left” segments as the first, each vertical “left” segment is placed on the left-most available grid. If no such grid line is available, the width of the channel is extended by one grid and attempt is made to place the segment on a new grid. The grid line is available if there are no conflicts with another net along the length of the vertical segment, taking into account separation rules. After the “left” segments are identified, the x-coordinates of the “either” vertical segments are identified, followed by the “right” segments. If the process is accomplished starting with the “right” segments, then each vertical “right” segment is placed on the right-most available grid and the process continues toward the left, as previously described. 
     At step  22 , the required buffers are identified, together with their ideal position and range. This takes into account the timing requirements to identify the approximate places where buffers would be required. Such a position is characterized by the ideal y-coordinate, the allowed distance from the ideal y-coordinate (range) and the vertical segment that is to be broken by the buffer. For example, if segment  50  in FIG. 2 is to be broken by a buffer, the resulting y coordinate of the buffer must be on a grid reserved for the buffer, with only that one buffer on that one grid reserved for it. 
     At step  24 , the actual positioning of the buffers is accomplished, based on the ideal positions. This is treated as an assignment problem of placing the buffers (as objects) at horizontal grid lines (as boxes) to minimize the penalty function. If the capacity of a line is “1”, it is reserved for buffers. Otherwise, grid lines not reserved for buffers are “0”. The penalty increases as the position of the grid line to the buffer is placed further from the ideal y-coordinate, and is infinity if the grid line is outside the allowed distance from the ideal coordinate or outside the vertical segment. The penalty increases as a quadratic function, and the solution is the placement of the buffers and grid lines to minimize the overall penalty function. As a result the buffers are positioned in optimal locations. After the buffers are placed, the vertical channels are extended to the y-coordinate of the buffer, with jogs as necessary. 
     In some cases, it may be necessary to sort the buffers according to the x-coordinate of the corresponding vertical segment and solve the assignment problem, as heretofore described, for subchannels consisting of buffers whose x-coordinate is less than some X 0 . Using the largest X 0 , a column of buffers is constructed. The process is then repeated for that part of the channel from X 0  to the end, resulting in several potential columns of buffers. Buffers are then placed at their positions, the vertical lines are broken and horizontal lines to make connection are accomplished. 
     The invention is preferably carried out though use of a computer programmed to carry out the process. A computer readable program code is embedded in a computer readable storage medium, such as a disk drive, and contains instructions that cause the computer to carry out the steps of the process. More particularly, code causes the computer to reserve grid positions for buffers, create jogs and vertical segments, assign y-coordinates to jogs and x-coordinates to vertical segments, and assign connections to buffers with minimized penalty. The result is a netlist that differs from the original by the inclusion of buffers and their position to accommodate technology restrictions. 
     Although the present invention has been described for the situation where the channel is vertical, an analogous process is performed if the channel is horizontal. The process of the invention provides for channel routing without repetitive trial layouts that prior processes required and without detailed knowledge of technology restrictions associated with the fabrication process. The process is simple to use and allows for channel routing of IC netlists transmitted electronically from the designer to the fabricator. 
     Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.