Abstract:
A method of simulating a design of an electronic system having multiple layers includes, for each layer, storing a plurality of shape occurrences for the layer. A hierarchy of shape instances having a plurality of levels is generated. Each shape instance corresponds to one of the shape occurrences. A hierarchy of shadow instances having a plurality of levels is generated.

Description:
FIELD OF THE INVENTION 
   The present invention relates generally to electronic circuit design and manufacturing. 
   BACKGROUND OF THE INVENTION 
   A semiconductor integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, wires, etc., that are fabricated by forming layers of different materials and of different geometric shapes on various regions of a silicon wafer. The design of an integrated circuit transforms a circuit description into a geometric description called a layout. The process of converting specifications of an integrated circuit into a layout is called the physical design. 
   After the layout is complete, it is then checked to ensure that it meets the design requirements. The result is a set of design files, which are then converted into pattern generator files. The pattern generator files are used to produce patterns called masks by an optical or electron beam pattern generator. Subsequently, during fabrication of the IC, these masks are used to pattern chips on the silicon wafer using a sequence of photolithographic steps. Electronic components of the IC are therefore formed on the wafer in accordance with the patterns. 
   Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives such as transistors and diodes, their sizes and interconnections, for example. 
   Geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist. 
   IC layouts are often constructed in a hierarchical fashion, in which a master version or occurrence of a particular geometric element is created once, but where one or more instances of the geometric element may be inserted into various locations and levels within the IC design. 
   In this type of approach, the IC layout is hierarchically set out by re-using elements over and over again. Rather than copying duplicates of the same geometric element everywhere that it is used, instances of the elements are inserted in the appropriate locations that logically reference the appropriate master occurrence or version. 
     FIG. 1A  shows an example design hierarchy, in which an occurrence  112  of element A comprises three shapes  114 ,  116 , and  118 . As used herein, occurrence is a master or reference copy of an element and an instance is an instantiation of an occurrence. At a different level in the IC design, an occurrence  122  of element B may be created that includes its own shapes  124  and  125 , as well as two instances  126  and  128  of element A. At yet another level of the IC design, an occurrence  132  for element C may be created that includes a shape  134  as well as two instances  136  and  138  of element B. Instances  136  and  138  each contain instances of element A as shown in occurrence  122  (which are “nested instances”). In the hierarchy of  FIG. 1A , each instance provides a logical reference to its master occurrence rather than a physical manifestation of the occurrence at the instance locations. Assume that shapes  114 ,  116 , and  134  are on layer  1  of the design and shapes  118 ,  124 , and  125  are on layer  2  of the design.  FIG. 1B  shows the shapes that would be present on layer  1  for these portions of the design and  FIG. 1C  shows the shapes that would be present on layer  2 . 
   An advantage of this approach is improved efficiency with respect to memory usage when storing design data for an IC design. Memory efficiencies are gained since instances of an element are used and placed in the design, rather than requiring a full copy of that element to be duplicated numerous times in the design data. 
   However, the hierarchical nature of this approach can also cause inefficiencies when attempting to access the design data. As just one example, consider the process to search a portion of the IC design for the shapes within a particular search area. The search area may encompass parts of one or more instances in the design. However, only a subset of the shapes within the instances may actually fall within the search area. Because the shapes are not actually stored at each level, the search process may need to traverse the entire hierarchy of the corresponding instances on every layer and their nested instances to confirm which shapes in the instances relate to the search area, even through portions of the hierarchy that do not contain any shapes at the correct layer or design area. Depending upon the complexity of the design, this could be a very lengthy and expensive process. 
   In an alternate approach, the design hierarchy can be flattened so that the design data is not hierarchical in nature. In this approach, rather than inserting instances of elements into the design, actual copies of the elements are placed in the appropriate locations within the design data. 
     FIG. 2  shows a flattened version of the design data shown in  FIG. 1 . Here, occurrence  122   a  for a flattened element B includes copies  126   a  and  128   a  of element A  112 , rather than the instances  126  and  128  of element A shown in  FIG. 1  that refers back to the master copy  112 . Similarly, occurrence  132   a  for a flattened element C includes copies  136   a  and  138   a  of element B  122   a , rather than instances that refer back to the master copy. 
   The advantage of this approach is that it is very efficient to search the flattened design data, since chains of instances do not need to be followed to identify shapes within a search area. However, if the design includes a large number of geometric elements, then this approach may also consume an excessive amount of memory and storage resources. 
   SUMMARY OF THE INVENTION 
   A method of representing a design of an electronic system having multiple layers includes, for each layer, storing a plurality of shape occurrences for the layer. A hierarchy of shape instances has a plurality of levels. Each shape instance corresponds to one of the shape occurrences. A hierarchy of shadow instances has a plurality of levels. 
   Other and additional objects, features, and advantages of the invention are described in the detailed description, figures, and claims. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The drawings illustrate the design and utility of embodiments of the present invention, in which similar elements are referred to by common reference numerals. In order to better appreciate the advantages and objects of a preferred embodiment, reference should be made to the accompanying drawings that illustrate this preferred embodiment. However, the drawings depict only one embodiment of the invention, and should not be taken as limiting its scope. 
       FIGS. 1A–C  shows an example design hierarchy. 
       FIG. 2  shows an example of a flattened design hierarchy. 
       FIGS. 3A–B  illustrate examples of information stored in a shape tree according to one embodiment of the invention. 
       FIGS. 4 ,  5 A–C, and  6 A–C illustrate an embodiment of a process for determining shadow boundaries and shadow trees. 
       FIG. 7  is a flowchart of a process for searching an area of a layer of a design according to an embodiment of the invention. 
     FIGS.  8 A–G and  9 A–C illustrate an example process for searching an area of a layer of a design according to an embodiment of the invention. 
   

   DETAILED DESCRIPTION 
   The present invention is directed to an improved method and mechanism for managing and tracking geometric objects in an integrated circuit design. In one embodiment, the invention comprises a set of structures (referred to herein as “shape abstraction data structures”) in which a hierarchical design structure is maintained but which provides many advantages of a flattened design. In this embodiment, the shape abstraction data structures store geometric information for shapes in each layer of the design and track the boundaries of shape instances (“shadows”) at each layer. 
   In one embodiment, the shapes are tracked for each occurrence for each layer of the design. Any suitable data structure may be employed to track the shapes, e.g., using a tree structure, list structure, etc. As used herein, the term “shape tree” refers to a data structure for tracking the shapes on a layer for an occurrence. 
   To illustrate and explain the invention, reference will be made to the design hierarchy of  FIG. 1A . Recall that  FIG. 1A  shows an example design hierarchy, in which an occurrence  112  of element A comprises three shapes  114 ,  116 , and  118 . At a different level in the IC design, an occurrence  122  of element B may be created that includes its own shapes  124  and  125 , as well as two instances  126  and  128  of element A. At yet another level of the IC design, an occurrence  132  for element C may be created that includes a shape  134  as well as two instances  136  and  138  of element B. It is assumed that shapes  114 ,  116 , and  134  are on layer  1  of the design and shapes  118 ,  124 , and  125  are on layer  2  of the design.  FIG. 1B  shows the shapes that would be present on layer  1  for these portions of the design and  FIG. 1C  shows the shapes that would be present on layer  2 . Each instance in the instance hierarchy points to a master data structure of the corresponding occurrence for the shape. The master data structure contains data, such as the bounds for the shape. 
   A first set of structures in the shape abstraction data structures is referred to herein as the shape trees, which track the native shapes on each layer for each geometric element. In the present embodiment, a separate shape tree is maintained for each occurrence for each layer. However, as is evident to those skilled in the art, other organizations of the data can also be used to implement the shape trees. 
     FIG. 3A  illustrates the contents of the shape trees for layer  1  of the design hierarchy of  FIG. 1A . Shape tree  312   a  tracks the shapes on layer  1  for element A, illustrating that element A includes shapes  114  and  116  on layer  1  at the indicated locations. Shape tree  322   a  tracks the shapes on layer  1  for element B, illustrating that element B does not have any native shapes on layer  1 . Shape tree  332   a  tracks the shapes on layer  1  for element C, illustrating that element C includes a shape  134  on layer  1  at the indicated location. 
     FIG. 3B  illustrates the contents of the shape trees for layer  2  of the design hierarchy of  FIG. 1A . Shape tree  312   b  tracks the shapes on layer  2  for element A, illustrating that element A includes shape  118  on layer  2  at the indicated location. Shape tree  322   b  tracks the shapes on layer  2  for element B, illustrating that element B includes shapes  124  and  125  on layer  2  at the indicated locations. Shape tree  332   b  tracks the shapes on layer  2  for element C, illustrating that element C does not have any native shapes on layer  2 . 
   Another set of structures (referred to herein as “shadow trees”) is maintained to track the boundaries of the shape for instances (“shadows”) at each layer. Each instance refers to a master structure that may include one or more shapes on one or more layers of the design. The shadow trees provide a structure that tracks the identity and location for the boundaries of the shapes referred to by instances in the design. Any suitable data structure may be used to track the information in the shadow trees, such as tree structures and list structures. In the present embodiment, a separate shadow tree is maintained for each occurrence for each layer. However, as is evident to those skilled in the art, other organizations of the data can also be used to implement the shadow trees. 
   The shadow tree for an occurrence on a layer is determined by identifying a “shadow” for shapes in the appropriate layer for the top-level instances in the element. Each top-level instance having shapes at the appropriate layer is associated with its own shadow. Each top-level instance may have its own nested instances. The boundary of the shadow for the instance is determined by performing a union of the coverage area for all shapes at the appropriate layer for that top-level instance with the coverage area of shapes at the layer in its nested instances. 
   Referring to  FIG. 4 , shown are the contents of shadow trees that may be created for element A. The shapes in instances for element A at layer  1  would be represented in a layer  1  shadow tree  401  and the shapes in instances A at layer  2  would be represented in a layer  2  shadow tree  403 . Here, since element A does not contain any instances, there are no instance shadows, at either layer  1  or layer  2 , to populate the shadow trees for element A. Therefore, no shadows exist in shadow trees  401  and  403  for element A. 
     FIG. 5A  illustrates the presently embodied process for forming shadow trees for occurrence  122  of element B. Occurrence  122  for element B includes two instances A 1   126  and A 2   128  of element A. The shadow trees for element B contain a shadow for each instance that contains shapes at the appropriate layer of the design. Each shadow tracks the boundaries of the shapes in the instance, and shapes in its nested instances, that exist on the appropriate layer of the design. 
   Shadow tree  430  tracks the boundaries of shapes on layer  1  for instances of element B. Here, shadow tree  430  contains a first shadow  412   a  corresponding to instance A 1  and a second shadow  412   b  corresponding to instance A 2 . 
     FIG. 5B  illustrates an embodiment of a process for determining the boundaries and locations of the shadows  412   a  and  412   b  for the shapes of instances of element A at layer  2 . The first action is to identify the native shapes for element A that exist on layer  1  of each instance. For this example, shapes  114  and  116  have been identified as being on layer  1  of element A (see  FIG. 1B ). A boundary is drawn around the identified shapes on the layer. In one embodiment, the boundary is a rectangle that is sized to fit around the boundary of all the identified shapes on the layer. Here, boundary  410  is a rectangular shape that matches and encompasses the outer boundaries of all the identified shapes  114  and  116  for element A on layer  1 . Since shapes  114  and  116  are separated by a certain distance, the boundary  410  may encompass additional area within the geometric element. Next, identification is made of a boundary for all shapes for layer  1  within nested instances of element A. To identify the boundaries of the final shadow  412  for instances of element A, a union is performed between the boundary  410  of the native shapes in element A and the boundary of the shapes for nested instances within element A. Here, element A does not have any nested instances. Therefore, the coverage area and relative location of boundary  410  for the native shapes  114  and  116  in element A form the shadow  412  for element A on layer  1 . 
   Shadow  412  is duplicated as shadow  412   a  in shadow tree  430  of  FIG. 5A  at a location relative to its positioning within instance A 1 . In like manner, shadow  412  is also duplicated as shadow  412   b  in shadow tree  430  at a location relative to its positioning within instance A 2 . 
   Shadow tree  432  in  FIG. 5A  tracks the boundaries of shapes on layer  2  for instances of element B. Here, shadow tree  432  contains a first shadow  416   a  corresponding to instance A 1  and a second shadow  416   b  corresponding to instance A 2 . 
     FIG. 5C  illustrates an embodiment of a process for determining the boundaries and locations of the shadows  416   a  and  416   b  for the shapes of instances of element A at layer  2 . The first action is to identify the native shapes for element A that exist on layer  2  of each instance A 1  and A 2 . Here, only shape  118  of element A has been identified as being on layer  2  (See  FIG. 1C ). Therefore, the boundary  414  that is drawn around native shapes at the top-level instance (i.e., shape  118 ) exactly matches the dimensions and relative location for shape  118  within element A. Next, identification is made of the boundary for all shapes on layer  2  within nested instances in element A, which will be combined with boundary  414  to form shadow  416 . Here, element A does not have any nested instances. Therefore, the coverage area and relative location of boundary  414  for shape  118  forms the shadow  416  for element A on layer  2 . 
   Shadow  416  is duplicated as shadow  416   a  in shadow tree  432  of  FIG. 5A  at a location relative to its positioning within instance A 1 . In like manner, shadow  416  is also duplicated as shadow  416   b  in shadow tree  432  at a location relative to its positioning within instance A 2 . 
     FIG. 6A  illustrates the presently embodied process for forming shadow trees for occurrence  132  of element C. Occurrence  132  for element C includes two instances B 1   136  and B 2   138  of element B. The shadow trees for element C contain a shadow for each instance that contains shapes at the appropriate layer of the design. Each shadow tracks the boundaries of the shapes in the instance, and shapes in its nested instances, that exist on the appropriate layer of the design. 
   Shadow tree  436  tracks the boundaries of shapes on layer  1  for instances of element C. Here, shadow tree  436  contains a first shadow  473   a  corresponding to instance B 1  and a second shadow  473   b  corresponding to instance B 2 . 
     FIG. 6B  illustrates an embodiment of a process for determining the boundaries and locations of the shadows  473   a  and  473   b  for the shapes of instances of element B at layer  1 . The first action is to identify the native shapes for element B that exist on layer  1  of each instance. In this example, there are no native shapes for instances of element B on layer  1  (See  FIG. 1B ). Therefore, a shadow does not exist for native shapes for instances of element B on layer  1 . Next, identification is made of the boundary for shapes on layer  1  for nested instances within instances of element B. Here, element B includes two instances of element A (element A 1  and A 2 ). Each instance A 1  and A 2  includes a shape  114  and a shape  116  on layer  1 . Therefore, a boundary  471  exists for all the shapes  114   A1 ,  116   A1 ,  114   A2 , and  116   A2  for nested instances A 1  and A 2 . As before, the boundary can be drawn as a rectangle that is sized to fit around the outer boundaries of all the identified shapes, even if the boundary includes open area between the shapes. The shadow  473  for layer  1  of element B is formed from a union of the boundary for the native shapes and the boundary  471  for the shapes at layer  1  of nested instances. Here, since element B does not have any shapes on layer  1 , the coverage area and relative location of boundary  471  for the nested instances form the shadow  473  for element B on layer  1 . 
   Shadow  473  is duplicated as shadow  473   a  in shadow tree  436  of  FIG. 6A  at a location relative to its positioning within instance B  1 . In like manner, shadow  473  is also duplicated as shadow  473   b  in shadow tree  436  at a location relative to its positioning within instance B 2 . 
   Shadow tree  434  tracks the boundaries of shapes on layer  2  for instances of element C. Here, shadow tree  434  contains a first shadow  422   a  corresponding to instance B 1  and a second shadow  422   b  corresponding to instance B 2 . 
     FIG. 6C  illustrates an embodiment of a process for determining the boundaries and locations of the shadows  422   a  and  422   b  for the shapes of instances of element B at layer  2 . The first action is to identify the native shapes for element B that exist on layer  2  of each instance B  1  and B 2 . Shapes  124  and  125  have been identified as natively being on layer  2  of instances of element B. A boundary  420  is drawn around the identified shapes  124  and  125  on the layer. Here, boundary  420  is a rectangular shape that matches and encompasses the outer boundaries of all the identified shapes  124  and  125  for element B on layer  2 . Since a distance separates shapes  124  and  125 , the boundary  420  encompasses additional area within the geometric elements of the two shapes. 
   Next, identification is made of the boundary for shapes on layer  2  for nested instances within element B. Here, element B includes two instances of element A (element A 1  and A 2 ). Each instance A 1  and A 2  includes a shape  118  on layer  2 . Therefore, a shadow boundary  475  exists surrounding the outer boundaries of shapes  118   A1 , and 118 A2  for nested instances A 1  and A 2 . 
   The shadow  422  for layer  2  shapes of element B is defined from a union of the boundary  420  for the native shapes and the boundary  475  for the shapes of nested instances within layer  2 . As before, the boundary can be drawn as a rectangle that is sized to fit around the outer boundaries of all the identified shapes, even if the boundary includes open area between or around the shapes. Shadow  422  is duplicated as shadow  422   a  in shadow tree  434  of  FIG. 6A  at a location relative to its positioning within instance B 1 . In like manner, shadow  422  is also duplicated as shadow  422   b  in shadow tree  434  at a location relative to its positioning within instance B 2 . 
     FIG. 7  shows a flowchart of an embodiment of a method to identify or search for objects within a layer of a design when using the disclosed shape abstraction data structures. A desired region or area of a given layer to be searched is defined ( 602 ). Shapes within or intersecting with the search area on the desired level are identified. In one approach, this is performed by searching the appropriate shape tree for the object or area being searched ( 604 ). A determination is made whether any shapes exist within or intersect with the search area ( 606 ). If so, then the identified shapes are reported as being within the search area ( 608 ). One exemplary approach for identifying geometric objects within a given search area is described in co-pending application U.S. Ser. No. 10/342,823 entitled, “Zone Tree Method and Mechanism”, filed on Jan. 14, 2003, which is hereby incorporated by reference in its entirety. 
   Next, the shapes for instances within the search area are identified. In one approach, this is performed by searching the appropriate shadow tree for the object or area being searched ( 610 ). A determination is made whether any shadows exist within or intersect with the search area ( 612 ). If so, then identification is made of the master structure(s) for the identified shadow(s) ( 614 ). The search area is re-defined to cover the corresponding portions of each identified master structure ( 616 ). For each identified master, the process recursively returns back to  604  to identify shapes associated within the re-defined search area of the master ( 618 ). 
     FIGS. 8A–G  illustrate an example of this process for identifying objects within a search area.  FIG. 8A  shows a search area  702  that has been defined for layer  1  to search for shapes within element C. A search of the shape tree is performed. To depict a search of the shape tree,  FIG. 8B  shows the search area  702  overlaid on the shape tree  332   a  ( FIG. 3A ) for layer  1  of element C. Here, it can be seen that shape  134  intersects with the boundaries of search area  702 . Therefore, the process reports shape  134  as being within/intersecting with the search area. 
   Next, the shadow tree is searched with respect to the search area  702 . Referring to  FIG. 8C , shown is the search area  702  overlaid onto the visualization of shadow tree  436  ( FIG. 6A ) for layer  1  of element C. Here, it can be seen that shadow  473   a  intersects with the boundaries of the search area  702 . 
   The shadow  473   a  is identified as being associated with instance B 1 . Therefore, the next action is to transform the search area  702  relative to its corresponding portion of the master for instance B 1 , and then recursively perform a search for shapes within that re-defined search area  702   a  for the master structures for instance B 1  at the appropriate layer. 
   A search of the shape tree  322   a  ( FIG. 3A ) for the master of instance B 1  is performed. To depict a, search of the shape tree,  FIG. 8D  shows the re-defined search area  702   a  overlaid on the shape tree  322   a  for layer  1  of element B. Here, it can be seen that no shapes exist in the shape tree  322   a  for element B within the re-defined search area  702   a.    
   Next, the shadow tree for layer  1  of element B is searched with respect to the search area  702   a . Referring to  FIG. 8E , shown is the search area  702   a  overlaid onto the visualization of shadow tree  430  ( FIG. 5A ) for layer  1  of element B. Here, it can be seen that shadow  412   b  intersects with the boundaries of the search area  702   a.    
   The shadow  412   b  is identified as being associated with instance A 2  of element B. Therefore, the next action is to transform the search area  702   a  relative to its corresponding portion of the master for instance A 2 , and then recursively perform a search for shapes within that re-defined search area  702   b  for the master structures for instance A 2  at the appropriate layer. 
   A search of the shape tree  312   a  ( FIG. 3A ) for the master of instance A 2  is performed. To depict a search of the shape tree,  FIG. 8F  shows the re-defined search area  702   b  overlaid on the shape tree  312   a  for layer  1  of element A. Here, it can be seen that shape  114  falls within the boundaries of search area  702   b . Therefore, the process reports shape  114  as being within/intersecting with the search area. 
   Next, the shadow tree for layer  1  of element A is searched with respect to the search area  702   b . Referring to  FIG. 8G , shown is the search area  702   b  overlaid onto the visualization of the shadow tree  401  ( FIG. 4 ) for layer  1  of element B. Here, it can be seen that no shadows within shadow tree  401  intersect with the boundaries of the search area  702   b . Therefore, the process ends unless additional recursive searches still need to be performed for shadows that have been previously identified. 
   Next, assume that the search is for objects on layer  2  of geometric element C.  FIG. 9A  shows a search area  802  that has been defined for layer  2  to search for shapes within element C. A search of the appropriate shape tree is performed. To depict a search of the shape tree,  FIG. 9B  shows the search area  802  overlaid on the shape tree  332   b  ( FIG. 3A ) for layer  2  of element C. Here, it can be seen that the boundaries of search area  802  do not intersect any shapes within shape tree  332   b . Therefore, the process does not report any shapes at this time. 
   The shadow tree for layer  2  is then searched with respect to the search area  802 . Referring to  FIG. 9C , shown is the search area  802  overlaid onto a visualization of the shadow tree  434  ( FIG. 6A ) for layer  2  of element. Here, it can be seen that no shadows within shadow tree  434  fall within or intersect the boundaries of the search area  802 . Therefore, no shapes are reported as being within the search area on layer  2 . 
   Note that this search area over layer  2  of element C does not return any found objects, despite the fact that the search area actually encompasses a portion of instance B 1   136  (as can be seen on  FIG. 9A ). Because the shadow tree is configured to track only the actual boundaries of shapes for instances on the specified layer, and no shapes exist within the search area on layer  2  of element C, the search does not return any found objects. This highlights a significant advantage of the present embodiment of the invention, which can greatly reduce unnecessary searching of hierarchical elements that do not have shapes in the search area within the layer being searched. 
   Therefore, what has been described is a method and mechanism for managing and tracking objects in an integrated circuit design. The present invention may be embodied as any combination of software, hardware, computer usable medium, or manual operations. In one specific embodiment, the invention is embodied as an EDA software tool for placing and/or routing integrated circuit designs. 
   These and other embodiments of the present invention may be realized in accordance with the above teachings and it should be evident that various modifications and changes may be made to the above-described embodiments without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense and the invention measured only in terms of the claims.