Abstract:
A method is disclosed for storing a circuit design in memory of a computer system and analyzing the design using an electronic computer-aided design (E-CAD) tool. The design may include hierarchical cells for repeated elements and groups of elements. A flat data structure is created to represent a specified portion of the circuit between two terminal nodes. For each node and edge in the specified portion, the flat data structure stores a name, an address pointer to the underlying data in the circuit model, and address pointers to adjoining nodes or edges in the flat data structure. Also for each node and edge in the design, the data structure stores an indicator showing whether the node or edge has been analyzed. The E-CAD analysis is performed on the flat representation, the results are recorded, and the flat data structure is deleted from memory.

Description:
FIELD OF INVENTION 
     The present invention relates generally to computer software for the design of semiconductor chips. More particularly, it relates to a method of processing data for analyzing a chip design stored in a computer memory. 
     BACKGROUND 
     In the field of semiconductor chip design and particularly very large scale integration (VLSI) chip design, a design may be stored in a computer memory for analysis. For example, the designer may wish to test the current or signal response through particular metal segments or conductors in the design. The individual nodes, signals, components, conductors, and other information are stored as a computer model in the computer database and used for design calculations and testing. 
     The computer model may include cross-references to save memory. For example, sometimes a particular series of components may be repeated in the design. The design may represent these related components in a single cell and store the cell to memory. Wherever the cell appears in the design, the computer model may merely have a reference to it, rather than storing all of its information every time it appears. This model is referred to as a hierarchical design, as opposed to a flat data representation. The hierarchical model may extend to groups of cells, and groups of groups, etc. as called for by the design. Wherever a series of items is repeated, the computer model may store the data in a hierarchy of cross-references. 
     One difficulty with the hierarchical model is that it is cumbersome and time-consuming to traverse. It requires multiple cross-references, increasing the time required to perform an analysis of the design. The alternative design model is the flat data representation, in which every element of the design is stored in full every time it appears in the design. The same data is stored multiple times because there are no cross-references. The flat data representation requires less time for analysis, but it is impractical to use because it requires too much storage memory to represent the entire design. 
     Another problem with analysis of circuit designs is that a particular design portion under test may have multiple paths between two nodes. For example, an electronic computer-aided design (E-CAD) tool may be run on the circuit design to analyze particular characteristics of a design portion, such as current along a specified path. The E-CAD tool retrieves the information from the design stored in memory, traversing the hierarchy as necessary. In its analysis, the E-CAD tool may need to traverse all of the paths between two nodes to ensure that it has analyzed each path. At the same time, the tool needs to make sure it does not analyze the same path twice, by looping back for example. Existing methods do not provide an efficient means of preventing the tool from analyzing the same portion of the design twice. 
     What is needed is a more efficient method for storing and processing chip design data to decrease required processing time without significantly affecting memory storage. What is also needed is a more efficient means of analyzing hierarchical data using a circuit analysis tool. What is also needed is a more efficient means of avoiding looping in the analysis of the design. 
     SUMMARY OF INVENTION 
     A method is disclosed for storing, for example, a very large scale integration (VLSI) circuit design in memory of a computer system and analyzing the design using an electronic computer-aided design (E-CAD) tool. The design may include hierarchical cells for repeated elements and groups of elements. A data structure is created to represent a specified portion of the circuit, such as a signal between two nodes. For each net in the specified portion, the data structure creates a node that stores a name, an address pointer to the underlying data in the circuit model, and address pointers to adjoining edges in the data structure. For each device between nets, the data structure creates an edge that stores a name, an address pointer to the underlying cell information in the circuit model, and address pointers to adjoining nodes. Also, the data structure stores an indicator showing whether each node or edge in the signal has been analyzed. 
     The circuit design is analyzed on a signal-by-signal basis using the E-CAD tool. The method selects a signal for analysis, creates a flat data representation for the signal, and stores it in memory. The E-CAD tool then performs its analysis on the flat representation and records the results in its ordinary operation. When the signal analysis is complete, the flat representation is deleted from memory, and other signals may be analyzed in turn. 
    
    
     SUMMARY OF DRAWINGS 
     FIG. 1 shows a schematic representation of a cell. 
     FIG. 2 shows a flat representation of a schematic of multiple cells. 
     FIG. 3 shows a hierarchical representation a schematic of multiple cells. 
     FIGS. 4A and 4B show primitive cells. 
     FIG. 5 shows a hierarchical cell model using the cells of FIGS. 4A and 4B. 
     FIG. 6 shows a more complex hierarchical cell model of a circuit portion using the cells of FIGS. 4A,  4 B, and  5 . 
     FIG. 7 shows a graphical representation used by the method. 
     FIGS. 8A and 8B show data structures for node and edge data stored by the method. 
     FIGS. 9A and 9B show example data stored for nodes and edges of the design of FIG.  6 . 
     FIG. 10 shows a block diagram of a computer system that performs the method. 
     FIG. 11 shows a flow chart of the method. 
     FIG. 12 shows a more detailed flow chart of the method shown in FIG.  11 . 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 illustrates the use of design hierarchical cells in the computer modeling of a design for a circuit, such as an integrated circuit (IC). FIG. 1 shows a schematic of a cell  50  having an inverter  40  connected to a plurality of resistors  41 ,  42 ,  43 ,  44 ,  45 . The cell  50  may represent the components of a segment that is stored as a computer model of a circuit design stored in a computer memory. In use, a design may repeat the same components in cell  50  several times. A cell  50  allows the designer to create the specific components, such as the inverter  40  and resistors  41 ,  42 ,  43 ,  44 ,  45 , just once, and then repeat the contents of the cell wherever the connection and components repeat themselves. 
     For example, a single design may have three inverters connected in series using segments of the same character; that is, having the same physical dimensions and properties. FIG. 2 shows an example of the contents of three cells  50  connected in series without reference to the general cell concept. The connection results in the series connection of the first inverter  40 , the first set of resistors  41 ,  42 ,  43 ,  44 ,  45 , the second inverter  40 ′, the second first set of resistors  41 ′,  42 ′,  43 ′,  44 ′,  45 ′, the third inverter  40 ″, and the third set of resistors  41 ″,  42 ″,  43 ″,  44 ″,  45 ″. The schematic shown in FIG. 2 is a flat data representation of the circuit, as every element is shown. Storage of the flat data representation of the entire model in the computer system requires substantial memory, so other methods are sometimes employed. 
     FIG. 3 shows a hierarchical schematic of the example of the flat data representation of FIG.  2 . Rather than specifying each of the components of a segment  10 , the cell  50  shown in FIG. 1 is utilized, and three cells  50 ,  50 ′,  50 ″ are connected in series. This hierarchical representation requires less memory because it stores the cell information only once and references it thereafter. For example, each resistor may require 32 bytes of memory to store its information. A flat representation of the entire design would require substantial memory and would repeat the same 32 bytes of information for every resistor and other component each time they appear in the design. A hierarchical design stores the cell  50  information in memory once and references that cell using an address pointer, which requires less memory. An address pointer includes any type of database link or association. 
     FIGS. 4A and 4B show examples of primitive cells used in a circuit design. FIG. 4A shows a primitive cell  52  for an n-type field effect transistor (NFET), labeled Cell A. The cell  52  is primitive in that it has no hierarchy. It contains the basic circuit element—in this case, the NFET having gate, source, and drain connections. The cell  52  has a plurality of ports  60  for connection to other cells in the design. In this example, there is a port  60  for each terminal of the NFET. FIG. 4B shows a primitive cell  54  for a p-type FET (PFET), labeled Cell B. In use, a design may store the attributes of the cells  52 ,  54  just once, and future uses of these same FETs is done using an address pointer to the memory location of the cells  52 ,  54 . This conserves memory by storing the circuit details only once. 
     FIG. 5 shows a hierarchical cell  56 , labeled INV. This cell  56  is an inverter comprised of input and output ports  60 , labeled “In” and “Out,” an NFET connected between the output and a low voltage, and a PFET connected between the output and a higher voltage. The INV cell  56  has a plurality of ports  60  for connecting the device to the circuit, and it also has the internal ports  60  of the constituent cells  52 ,  54 . The INV cell  56  is hierarchical because it comprises other cells, namely Cells A and B  52 ,  54  shown in FIGS. 5A and 5B. In memory, the INV cell  56  stores port and connection information, and references Cells A and B  52 ,  54  using an address pointer. This cell within a cell concept creates the hierarchy and conserves memory. 
     FIG. 6 shows a more complex cell design labeled Complex 1 . The cell  58  has a plurality of ports  60  and contains various resistors, inverters, FETs, and other devices. As used herein, “devices” refer broadly to any circuit element. Each box in FIG. 6 is an instance of a particular cell  50 , which itself may contain instances of other cells  50 . The inverters  56  are cells  50 , such as the inverter cell  56  shown in FIG. 5, having their own hierarchy. Similarly, the NTYPE FET cell  52  may be of the type shown in FIG.  4 A. In memory, the complex cell  58  contains references to the memory location of the inverter cell  56 , which in turn has the memory references to the FET cells  52 ,  54 . This hierarchy saves memory because each cell is stored once, and instances merely refer back to the cell that describes them, using address pointers. 
     In use, the circuit model, such as the Complex 1 cell  58  portion shown in FIG. 6, is analyzed using an E-CAD tool. The tool analyzes the performance of the circuit design by accessing the information stored in memory. The tool might examine, for example, the current through a particular portion of the design. In another example, the tool may simply check the connectivity of the design portion. In its analysis, the tool may traverse the circuit design from one node to another. For example, in the design portion shown in FIG. 6, an E-CAD tool might traverse the design from node A to node B to analyze the performance of that path. The selected portion may be defined as a signal from a starting terminal (Node A) to an end terminal (Node B). Two nodes may have multiple paths connecting them, caused by loops in the circuit design. To traverse the design, it is helpful for the E-CAD tool to know all of the paths between the nodes and to know which paths have already been analyzed. As devices are analyzed, they are marked to indicate that they have already been processed to avoid looping and analyzing the same device more than once. 
     In its analysis, the tool considers the properties of the devices along the traverse—for example, all of the resistors and other devices between nodes A and B. This involves reading the device information stored in the memory. When the design contains hierarchical devices, such as the inverters, the E-CAD tool reads the data stored in memory and uses the address pointers to access the primitive cells. 
     FIG. 7 shows an graphical representation of the signal paths between nodes A and B. This graph  61  is a representation of the flat representation data structure stored in a memory for analysis by an E-CAD tool. The graph  61  is created to overlay the hierarchical circuit design model. The flat representation refers to the connections by nodes and edges. Nodes  62  are the connectors between devices, such as nodes A and B. The individual nodes  62  shown in FIG. 7, N 1  through N 7 , correspond to the nodes (also referred to as “nets) shown in FIG.  6 . Edges  64  refer to the devices between the nodes, such as the resistors and cells in the example shown. Information is stored for each node  62  and edge  64  under test. 
     FIGS. 8A and 8B show the data format of the nodal and edge information that is stored. FIG. 8A shows the information stored for a node  62 . Each node  62  contains the name of the logical net that it represents, a marker to indicate whether the node  62  has been analyzed, or visited, by the E-CAD tool, and a data address pointer to the actual net data in the circuit design. As used herein, the terms “node” and “net” are used interchangeably, with node sometimes referring to a data representation of a net. Also, the terms “device” and “edge” are used interchangeably, with edge sometimes referring to a data representation of a device. FIG. 8B shows the information stored for an edge  64 . Each edge  64  contains the name of the instance it represents, a marker to indicate whether the edge  64  has been visited, and a data address pointer to the actual instance of the edge in the design. Also, to connect the graph  61 , the nodes  62  contain a list of the edges  64  connected to them, and the edges  64  contain a list of the nodes  62  they connect. These connectivity lists may be address pointers, referred to herein as connection address pointers. 
     FIGS. 9A and 9B show examples of information stored for nodes  62  and edges  64  of the design shown in FIG.  6 . Node N 5  is shown in FIG.  9 A. FIG. 6 shows the node N 5  connected between resistor R 6  and FET NTYPE  52 . In FIG. 9A, the name of the node  62  is stored as N 5 , and it is indicated to not yet have been processed. A reference to the actual net data is also included, along with the edge connections. In this example, the edge connections include NTYPE and R 6 . In FIG. 9B, edge data for the edge  64  named NTYPE is stored, along with an indication that this edge  64  has not yet been visited by the E-CAD tool. The data references the instance of the underlying NTYPE data, using a pointer to cell A shown in FIG.  4 A. The data also stores the names of the connected nodes N 5  and N 6 . 
     FIG. 10 shows a block diagram of a computer system  400  having a processor  410  connected to an input device  420  and a display device  430 . The processor  410  accesses memory  440  in the computer system  400  that stores a VLSI circuit design  450 . The design  450  may be stored in a data file, sometimes referred to as a “resistance-capacitance netlist” or an “RC netlist.” An E-CAD tool  460  is also stored in the memory  440  for analyzing the circuit model  450 . The circuit model  450  may be a hierarchical model that uses cells  50 , as described herein. In use, the input device  420  receives commands instructing the processor  410  to call the E-CAD tool software  460  to perform a circuit analysis on the model  450 . The results of the analysis may be displayed on the display device  430 . During the application of the E-CAD tool  460  on the hierarchical circuit design  450  using the method, a flat data representation  470  is created and stored in memory  440 . The data representation  470  uses a data structure that uses address pointers to store information about the nodal and edge connections of the design  450 . The data structure  470  may be similar to the data structures described in FIGS. 8A and 8B. 
     FIG. 11 shows a flow chart of the method for analyzing the design  450  stored in memory  440  of the computer system  400 . The method may be implemented in, for example, software modules such as the E-CAD tool  460  stored in memory  440  for execution by processor  410 . A hierarchical design database  450  is read into the E-CAD tool  460  for analysis. A portion of the circuit design  450  is selected  100  for analysis. The selection may be a signal defined by two terminal nodes in the circuit design  450 , such as nodes A and B in FIG. 6. A flat data structure  470  is then created  110  in memory  440  to represent the paths in the selected signal. The paths of the signal are traced  120  and marked as they are visited by the E-CAD tool  460 . The E-CAD tool  460  analyzes  130  the signal and deletes  140  the flat representation  470  from memory  440 . 
     FIG. 12 shows a more detailed analysis of the method for building  110  the flat representation  470 . After a signal is selected  100  for analysis, the E-CAD tool  460  reads  111  a net. A “net” refers to an idealized connection between devices or cells in a design  450 . A node  62  is built  112  to represent the net in the flat representation  470 . The flat representation data structure  470  stores a name of the node  62  and connection information. The data structure  470  contains information shown in FIG.  8 A. The representation  470  also stores a data address pointer to the location in the hierarchical database  450  that stores the underlying data for the node  62 , and an indication of whether the node  62  has been analyzed by the tool  460 . Using the connection information, the method then traces  113  the signal to the next connected device or cell  50 . An edge  64  is created  114  to represent the device in the flat data representation  470 . An “edge” refers to any data structure that stores information about a device or cell  50  in the flat representation  470 . By definition, nets (mapped as nodes) lie between devices (mapped as edges). The data structure  470  stores a name of the device as the edge name and stores connection information  120 . The data structure  470  contains information shown in FIG.  8 B. The representation  470  also stores a data address pointer to the location in the hierarchical database  450  that stores the underlying data for the edge  64 , and an indication of whether the edge  64  has been analyzed by the tool  460 . 
     The method then determines  115  whether it has reached the end terminal device for the signal analyzed. The terminal refers to any specified end point of the signal or design analysis. If it has not reached the terminal, then it traces  116  the connectivity to the next net and builds  112  a node for the net. Once the method reaches the terminal device, it determines  117  whether any other edges require mapping. For example, the map may involve multiple loops in the circuit  450  that must be followed. The tool  460  “backs up” from the terminal looking for additional nets and devices to be mapped. Using a recursion process, the method returns  118  to the last net having devices to traverse. and continues the trace  113  to the next device. The process continues until all paths are mapped. 
     Conventional E-CAD software programs are known in the art and the method shown in FIGS. 11 and 12 may be implemented, for example, by modifying such conventional software programs, or by including appropriate instructions in any E-CAD software tool. The modifications may include, for example, instructions to create and store the flat representation of the signal of interest and subsequently delete it from memory after analysis of it. 
     Although the present invention has been described with respect to particular embodiments thereof, variations are possible. The present invention may be embodied in specific forms without departing from the essential spirit or attributes thereof. In addition, although aspects of an implementation consistent with the present invention are described as being stored in memory, one skilled in the art will appreciate that these aspects can also be stored on or read from other types of computer program products or computer-readable media, such as secondary storage devices, including hard disks, floppy disks, or CD-ROM; a carrier wave from the Internet or other network; or other forms of RAM or read-only memory (ROM). It is desired that the embodiments described herein be considered in all respects illustrative and not restrictive and that reference be made to the appended claims and their equivalents for determining the scope of the invention.