Methods for Tiling Integrated Circuit Designs

Abstract

Methods for routing in the design of integrated circuits (ICs) to simplify the routing task. The method includes dividing a given IC design into a limited number of non-overlapping tiles, and then routing all tiles in parallel, each tile being independently routed by a standard router. Thereafter, routed tiles are assembled to form a routing solution for the entire IC. Details of exemplary methods are disclosed.

1 . A method for tiling an integrated circuit (IC) design, said method comprising:
 computing a routing capacity of each metal lithographic layer of said IC design;   constructing a set of horizontal and vertical wire segments;   bi-sectioning said IC design for identifying a set of tiles; and   partitioning the connectivity of said IC design based on the identified tiles.   
   
   
       2 . The method of  claim 1 , further comprising:
 distributing said tiles to a plurality of distributed routers;   simultaneously routing said tiles on the plurality of distributed routers; and   assembling the routed tiles to form a routed IC design.   
   
   
       3 . The method of  claim 1 , wherein said IC design is provided by at least one of: a placement tool, a global router; and a fine router. 
   
   
       4 . The method of  claim 1 , wherein constructing said set of horizontal and vertical wire segments comprises:
 receiving said IC design data from a placement tool;   for each net in said IC design, constructing an enclosing rectangle, wherein said enclosing rectangle includes all ports of said net; and   setting two opposite sides of said enclosing rectangle as a wire segment.   
   
   
       5 . The method of  claim 1 , wherein bi-sectioning said IC design comprises:
 receiving a rectangular portion of said IC design, said rectangular portion includes at least one horizontal wire segment and at least one vertical wire segment;   positioning a cut line perpendicularly to a longer side of said rectangular portion;   searching for a location that said cut line cuts a minimum number of wire segments; and   dividing said rectangular portion in the location with minimum cuts of wire segments, and thereby forming two smaller rectangular portions.   
   
   
       6 - 13 . (canceled) 
   
   
       14 . A machine-readable medium that provides instructions to implement a method for accelerating the generation of a physical layout of an integrated circuit (IC) design, which instructions, when executed by a set of processors, cause said set of processors to perform operations comprising:
 computing a routing capacity of each metal lithographic layer of said IC design;   constructing a set of horizontal and vertical wire segments;   bi-sectioning said IC design for identifying a set of tiles; and   partitioning the connectivity of said IC design based on the identified tiles.   
   
   
       15 . The machine-readable medium of  claim 14 , further comprising:
 distributing said tiles to a plurality of distributed routers;   simultaneously routing said tiles on a set of distributed routers; and   assembling the routed tiles to form a routed IC design.   
   
   
       16 . The machine-readable medium of  claim 15 , wherein said IC design is provided by at least one of: a placement tool, a global router, and a fine router. 
   
   
       17 . The machine-readable medium of  claim 15 , wherein constructing said set of horizontal and vertical wire segments comprises:
 receiving said IC design data from a placement tool;   for each net in said IC design, constructing an enclosing rectangle, wherein said enclosing rectangle includes all ports of said net; and   setting two opposite sides of said enclosing rectangle as a wire segment.   
   
   
       18 . The machine-readable medium of  claim 14 , wherein bi-sectioning said IC design comprising:
 receiving a rectangular portion of said IC design, said rectangular portion includes at least one horizontal wire segment and at least one vertical wire segment;   positioning a cut line perpendicularly to a longer side of said rectangular portion;   searching for a location that said cut line cuts a minimum number of wire segments; and   dividing said rectangular portion in the location with minimum cuts of wire segments, and thereby forming two smaller rectangular portions.   
   
   
       19 - 26 . (canceled) 
   
   
       27 . A distributed system for accelerating the routing of an integrated circuit (IC) design, said system comprising:
 a main computing node having at least a multi-processing agent for tiling said IC design;   a plurality of remote processing nodes coupled to said main computing node and programmed for simultaneously executing the routing of the tiles on a set of distributed routers; and   a communication network for communication between said main computing node and said plurality of remote processing nodes.   
   
   
       28 . The distributed system of  claim 27 , wherein each of said distributed routers is at least one of: a global router, a fine router. 
   
   
       29 . The distributed system of  claim 27 , where said multi-processing agent is further capable of:
 distributing said tiles to said plurality of remote processing nodes; and   assembling the routed tiles by said main computing nodes.   
   
   
       30 . The distributed system of  claim 29 , wherein tiling said IC design comprises:
 computing a routing capacity of each metal lithographic layer of said IC design;   constructing a set of horizontal and vertical wire segments;   bi-sectioning said IC design for identifying a set of tiles; and   partitioning the connectivity of said IC design based on the identified tiles.   
   
   
       31 . The distributed system of  claim 30 , wherein constructing said set of horizontal and vertical wire segments comprises:
 receiving said IC design data from a placement tool;   for each net in said IC design, constructing an enclosing rectangle, wherein said enclosing rectangle includes all ports of said net; and   setting two opposite sides of said enclosing rectangle as a wire segment.   
   
   
       32 . The distributed system of  claim 31 , wherein bi-sectioning said IC design comprising:
 receiving a rectangular portion of said IC design, said rectangular portion includes at least one horizontal wire segment and at least one vertical wire segment;   positioning a cut line perpendicularly to a longer side of said rectangular portion;   searching for a location that said cut line cuts a minimum number of wire segments; and   dividing said rectangular portion in the location with minimum cuts of wire segments, and thereby forming two smaller rectangular portions.