Patent Publication Number: US-9418190-B2

Title: Virtual sub-net based routing

Description:
This application is a continuation of U.S. Pat. No. 9,245,084 filed May 13, 2014, the disclosure of which is incorporated by reference herein in its entirety. 
    
    
     BACKGROUND 
     The present invention relates to the design of an integrated circuit, and more specifically, to virtual sub-net based routing in integrated circuit design. 
     As part of the design of an integrated circuit, interconnections among the various sub-networks or sub-nets (groupings of transistors and other components) must be routed. Two considerations in determining the routes are timing and crosstalk. For example, if the routes are too long, timing constraints of the design may not be met. As another example, when routes are temporally aligned, crosstalk may occur such that a signal on one route affects or interferes with a signal on another route. Temporal correlation of interconnects refers to transitions (0 to 1 or 1 to 0) occurring around the same time in close by interconnects. 
     SUMMARY 
     According to an embodiment, a system to route connections of sub-networks in a design block of an integrated circuit includes a memory device configured to store instructions to route the connections of the sub-networks; and a processor configured to execute the instructions to determine a baseline route for each of the connections of each of the sub-networks, identify noise critical sub-networks in the integrated circuit design based on congestion, set a mean threshold length (MTL), segment the connections of the noise critical sub-networks based on the MTL, and re-route the baseline route based on segmenting, wherein the MTL indicates a maximum length of each segment of each connection, each segment includes a different wirecode than an adjacent segment, and the wirecode defines a width, metal layer, and spacing for the segment. 
     According to another embodiment, a computer program product stores instructions therein which, when executed by a processor, cause the processor to implement a method of routing connections of sub-networks in a design block of an integrated circuit. The method includes determining a baseline route for each of the connections of each of the sub-networks; identifying, using a processor, noise critical sub-networks in the integrated circuit design based on congestion; setting, using the processor, a mean threshold length (MTL), the (MTL) indicating a maximum length of each segment of each connection, each segment including a different wirecode than an adjacent segment, the wirecode defining a width, metal layer, and spacing for the segment; segmenting the connections of the noise critical sub-networks based on the MTL; and re-routing the baseline route based on the segmenting. 
     Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. For a better understanding of the invention with the advantages and the features, refer to the description and to the drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The forgoing and other features, and advantages of the invention are apparent from the following detailed description taken in conjunction with the accompanying drawings in which: 
         FIG. 1  is an illustration of routing among tiles of a design block of an integrated circuit representation in the design phase; 
         FIG. 2  illustrates symmetric segmentation and asymmetric segmentation according to embodiments of the invention; 
         FIG. 3  illustrates different segmenting techniques according to embodiments of the invention; 
         FIG. 4  is a process flow of a method of routing connections in a sub-network to address crosstalk according to embodiments of the invention; and 
         FIG. 5  is a block diagram of a system to generate the design block according to an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     As noted above, timing (interconnect delay) and crosstalk are both important considerations in routing the various signals among sub-blocks of an integrated circuit. The likelihood of crosstalk increases as the distance that a signal travels increases and as a number of connections increases. This is because longer interconnects increase the length over which temporal correlation might occur, and higher congestion increases the likelihood that interconnects have to be more closely spaced, thereby increasing the chances of temporal correlations. Embodiments of the systems and methods discussed herein relate to crosstalk aware routing that uses dynamic criteria to virtually segment a long interconnect. 
       FIG. 1  is an illustration of routing among tiles  110  of a design block  100  of an integrated circuit representation in the design phase. The computer-aided design (CAD) tool organizes the design block  100  into groupings of components or tiles  110 .  FIG. 1  illustrates a high routing demand between two exemplary tiles  110  (A and B). The distance and density of communication links between the tiles A and B may result in crosstalk among the connections shown in  FIG. 1 . Some of the routes shown in  FIG. 1  may exceed a threshold Steiner length or maximum coupling length. These routes are susceptible to crosstalk. As detailed below, embodiments of the methods and systems described herein specifically relate to virtually segmenting these routes in the design phase. Long interconnects are routed as smaller segments with different wirecodes (different metal layer, width, spacing, or a combination thereof). Spacing refers to a minimum separation between an interconnect and an adjacent interconnect in the same metal layer. 
       FIG. 2  illustrates symmetric segmentation and asymmetric segmentation according to embodiments of the invention. The interconnects  200  include three sub-network connections  210 - 1 ,  210 - 2 ,  210 - 3  (referred to generally as connections  210 ) for explanatory purposes. Each of the connections  210  is shown divided into four segments  220  (connection  210 - 1  is divided into segments  220  A_ 1 , A_ 2 , A_ 3 , A_ 4 ; connection  210 - 2  is divided into segments  220  B_ 1 , B_ 2 , B_ 3 , B_ 4 ; and connection  210 - 3  is divided into segments  220  C_ 1 , C_ 2 , C_ 3 , C_ 4 ), with each segment  220  having an equal length  207 . The interconnects  200  may be symmetrically segmented into interconnects  203  or asymmetrically segmented into interconnects  205  according to embodiments of the invention detailed herein. That is, wirecodes are transitioned differently based on the embodiment. According to one embodiment, symmetric segmentation of the interconnects  200  (of the connections  210 ) results in the interconnects  203 . According to this embodiment, each of the connections  210  transitions to a different wirecode (e.g., width as shown in  FIG. 2 ) at the same point or at the end of a segment length  207  as shown in  FIG. 2 . For example, each of the connections  210  exhibits four different wirecodes over the four segments  220  (a different wirecode within each segment  220  A_ 1 , A_ 2 , A_ 3 , A_ 4  of connection  210 - 1 , for example). According to another embodiment, asymmetric segmentation of the interconnects  200  results in the interconnects  205 . According to this embodiment, each connection  210  transitions to a different wirecode (e.g., width and spacing as shown in  FIG. 2 ) at a different point, as shown in  FIG. 2 . As shown in  FIG. 2 , the original segment  220  demarcations of segment length  207  (from interconnects  200 ) are indicated, but the wirecode transitions of only connection  210 - 1  in interconnects  205  match up with those demarcations. That is, connection  210 - 1  exhibits four different wirecodes over the four segments  220 . However, connection  210 - 2  exhibits only three different wirecodes over those four segments  220  such that segment  220  B_ 4  is not shown for connection  210 - 2  of interconnects  205 . Further, connection  210 - 3  exhibits two different wirecodes over those four segments  220  such that segments  220  C_ 3  and C_ 4  are not shown for connection  210 - 3  of interconnects  205 . None of the connections  210  (of interconnects  205 ) transition from one wirecode to another at the same point as another connection  210 . 
     Segmenting must be balanced with the timing constraints on the integrated circuit design. That is, while increased segmenting decreases the potential for crosstalk, increased segmenting may also negatively impact timing. The threshold length at which a connection  210  is segmented is inversely dependent on congestion. The higher the congestion (and, thus, the higher the potential for crosstalk), the lower the threshold length for segmentation of the connection  210 . Within a tile  110 , segment length  207  for multiple connections  210  may be partially randomized around a computed congestion based mean (such that every connection  210  within the interconnects  203 , for example, do not have the same segment length  207 ) to further reduce the potential for crosstalk. 
       FIG. 3  illustrates different segmenting techniques according to embodiments of the invention. A source  310  and sink  320  for a connection  210  are shown on a coordinate map of an exemplary sub-network of the integrated circuit. The border or transition point between segments  220  may be marked on the initial connection  210  according to one embodiment, as shown by A. According to another embodiment, the segment  220  transitions may be determined on a Steiner route between the source  310  and sink  320 . According to yet another embodiment, a stepped path based on (originating at) the initial connection  210  path and chosen segment length  207  may be used to determine the coordinates (shown by B) at which to jump or transition from one segment to another. In order to prevent timing degradation based on the segmentation, some considerations during the segmenting process include using equivalent or better wirecode within the segments  220  than in the unsegmented connection  210 , limiting jogs (keeping the segments as straight as possible), and increasing the overall length of the connection  210 . The increase in overall length of the connection  210  is based on maintaining a ratio of the original length to the current length below a specified threshold. The threshold is selected based on timing requirements. That is, the threshold helps maintain the balance of crosstalk reduction efforts through segmentation and meeting timing constraints. 
       FIG. 4  is a process flow of a method of routing connections  210  in a sub-network to address crosstalk according to embodiments of the invention. At block  410 , performing baseline routing provides the initial connections  210  (e.g., interconnects  200  in  FIG. 2 ). Horizontal and vertical congestion may be mapped on a per tile  110  basis. The horizontal and vertical refers to a relative perpendicular orientation of connections  210  rather than to a direction. Identifying noise critical sub-networks in the design at block  420  may include assigning a congestion score to each tile  110 . The score may be separate for horizontal and vertical congestion. The score indicates the need for segmenting. As noted above, increased segmentation can negatively affect timing. Thus, segmentation is performed (prioritized) on the basis of need. Crosstalk-aware timing analysis may be performed in addition to identifying noise critical sub-networks. At block  430 , setting the mean threshold length (MTL) is done either uniformly or for each sub-network individually. The MTL is the maximum length at which a new segment (a change in wirecode) is warranted based on an increase in susceptibility to crosstalk. The wirecode may be changed after a length that is less than the MTL but must be changed once the length reaches the MTL. The MTL may be based on factors like congestion or utilization and may be determined individually for each sub-network or may be uniform over the integrated circuit design, at least initially. When the MTL is determined per sub-network, a sub-network with more congested interconnections would have a lower MTL (more segmenting), for example. A uniform MTL may be based on an average set of factors (e.g., congestion, utilization) or a worst-case scenario, for example. The MTL may be assigned for virtual sub-networks such that horizontal and vertical orientations are assigned different MTL values for each congestion critical tile  110 . The MTL may additionally be determined per wirecode, because each wirecode varies in its susceptibility to crosstalk. Thus, one wirecode may mitigate crosstalk over a longer segment length than another wirecode such that the MTL may be longer for that wirecode. The MTL may also be affected by the technology being supported. That is, for a given process technology, there is a known upper bound of interconnect length at which crosstalk may be maintained within a specified level for a given metal and wirecode. This upper bound may be used as a limiting factor on MTL, while congestion, timing, and other factors further limit MTL. When the MTL is not uniform for every sub-network but is, instead, determined based on the factors discussed above, the routing is said to be design aware. 
     At block  440 , segmenting selected interconnects (e.g.,  200 ) based on MTL includes segmenting long connections  210  that exceed the MTL into segments  220 . According to one embodiment discussed above as symmetric segmentation (see e.g., interconnects  203  in  FIG. 2 ), each segment  220  would have a length of MTL. According to another embodiment discussed above as asymmetric segmentation (see e.g., interconnects  205  in  FIG. 2 ), each segment  220  would have a length of MTL±Δ, where Δ is computed based on a random seed or on fine-tuning according to design adaptive randomization. At block  450 , the process includes re-routing the virtual sub-networks according to the MTL-based segmentation performed at block  440 . At block  460 , performing noise and timing analysis for the re-routed virtual sub-networks is followed by determining if noise levels and timing are as specified, at block  470 . Specifically, noise voltage level overshoot or undershoot or glitches may cause functional failure, and timing degradation (from the determination at block  420 ) based on slew fluctuation must not result in failure to adhere to timing constraints. If the noise for the re-routed sub-networks is not below specified levels or timing degradation is not acceptable based on system timing constraints, segmenting selected interconnects at block  440  is repeated. Specifically, the processes at blocks  440 - 470  are performed iteratively. 
       FIG. 5  is a block diagram of a system  500  to generate the design block  100  according to an embodiment of the invention. The system  500  executes a CAD tool, for example, to output the design block  100  that is ultimately used to fabricate the integrated circuit. The system  500  includes an input interface  510 , one or more processors  520 , one or more memory devices  530 , and an output interface  540 . The CAD tool may be implemented based on instructions stored in the memory device  530  and executed by the processor  520 , for example. More than one system  500  may be involved in the generation of the design block  100 . The segmented routing for the virtual design that results from the process discussed with reference to  FIG. 4  is output as a netlist that is used to fabricate the integrated circuit. 
     The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one more other features, integers, steps, operations, element components, and/or groups thereof. 
     The corresponding structures, materials, acts, and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements as specifically claimed. The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the invention. The embodiment was chosen and described in order to best explain the principles of the invention and the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated 
     The flow diagrams depicted herein are just one example. There may be many variations to this diagram or the steps (or operations) described therein without departing from the spirit of the invention. For instance, the steps may be performed in a differing order or steps may be added, deleted or modified. All of these variations are considered a part of the claimed invention. 
     While the preferred embodiment to the invention had been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first described.