Method and apparatus for extracting and storing connectivity and geometrical data for a deep sub-micron integrated circuit design

[0002] 1. Field of the Invention

[0003] The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to EDA tools for parasitic extraction in the process of designing sub-micron integrated circuit.

[0004] 2. Background Information

[0005] The technology of large scale integration continues to advance rapidly. Integrated circuits (IC) fabricated employing deep sub-micron processes are increasingly common and increasingly complex. One of the challenges faced by today's deep sub-micron IC designers is the issue of parasitic effects of passive interconnect. Deep sub-micron IC designers have come to recognize that these effects cannot be ignored, else the design can fail. These effects play an important role in timing, power, reliability as well as noise performance. In order to take parasitic effects of passive interconnect into consideration in post layout analysis for timing, power, etc., it is necessary to create electrical models for the physical connections present between the various devices in a deep sub-micron IC design, a process known as parasitic extraction. Multiple parasitic extractions performed repeatedly at different points in time to create multiple electrical models for different views of the design are often required.

[0006] With respect to parasitic extraction for deep sub-micron IC designs, conventional EDA tools typically suffer from at least four disadvantages:

[0007] (a) They do not support enough rich models to describe the increasingly complex processes;

[0008] (b) They do not adequately address electrical interdependence between a physical net model and a design model;

[0009] (c) They are incapable of dealing with the enormous data volumes generated by the increasingly complex sub-micron designs; and

[0010] (d) They do not efficiently support concurrent use by multiple post-layout analysis tools.

[0011] Thus, a more effective and yet efficient approach to extracting and storing connectivity and geometrical data for a deep sub-micron IC design that are comprehensive and organized to meet the needs of parasitic extraction is desired.

[0012] A data extraction tool is provided to extract filtered connectivity and geometrical data for specified layout cell hierarchies of an integrated circuit (IC) design, e.g. a deep sub-micron IC design. The connectivity and geometrical data for each layout cell hierarchy are extracted at least in part in accordance with specified parasitic effect windows. In one embodiment, the data extraction tool includes a filtered extraction function (FEX) that operates to extract connectivity and geometrical data for layout nets of a layout cell hierarchy of the IC design, one or more layout nets at a time. The connectivity and geometrical data for each layout net are extracted at least in part in accordance with specified parasitic effect windows of layout layers of the specified layout cell hierarchy.

[0013] Additionally, one or more filtered databases (FDB) are provided to store the filtered connectivity and geometrical data of the layout cell hierarchies. In one embodiment, one FDB is employed for each layout cell hierarchy, and the filtered connectivity and geometrical data are indexed by layout nets of the layout cell hierarchy.

[0014] The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:

[0015] FIG. 1 illustrates one embodiment of the present invention including a data extraction tool and filtered databases;

[0016] FIGS. 2-4 illustrate one embodiment each of the rule file, the layout cell hierarchies specification, and the data extraction tool command of FIG. 1 respectively;

[0017] FIGS. 5a-5cillustrate one embodiment of the operational flow of the data extraction operation of the present invention;

[0018] FIGS. 6a-6billustrate one embodiment of a filtered database of the present invention;

[0019] FIGS. 7a-7billustrate one embodiment of the operational flow of the data writing operation of FIG. 5 for the filtered databases of FIG. 6; and

[0020] FIG. 8 illustrates an exemplary computer system suitable for programming with the data extraction tool of the present invention.

[0021] Note: FIGS. 5a-5cform FIG. 5, and so forth.

[0022] In the following description, various aspects of the present invention will be described. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention. For purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present invention. However, it will also be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention.

[0023] Parts of the description will be presented in terms of operations performed by a computer system, using terms such as data, flags, bits, values, characters, strings, numbers and the like, consistent with the manner commonly employed by those skilled in the art to convey the substance of their work to others skilled in the art. As well understood by those skilled in the art, these quantities take the form of electrical, magnetic, or optical signals capable of being stored, transferred, combined, and otherwise manipulated through mechanical and electrical components of the computer system; and the term computer system include general purpose as well as special purpose data processing machines, systems, and the like, that are standalone, adjunct or embedded.

[0024] Various operations will be described as multiple discrete steps in turn, in a manner that is most helpful in understanding the present invention, however, the order of description should not be construed as to imply that these operations are necessarily order dependent. In particular, these operations need not be performed in the order of presentation.

[0025] Referring now to FIG. 1, wherein a block diagram illustrating one embodiment of the present invention is shown. As illustrated, the present invention includes data extraction tool 100 and filtered databases (FDB) 104. For the illustrated embodiment, data extraction tool 100 includes filtered extraction function (FEX) 102. Together, the elements cooperate to advantageously extract and store connectivity and geometrical data for layout cell hierarchies of deep sub-micron IC designs, to facilitate subsequent parasitic extraction, without most of the earlier described limitations of the prior art.

[0026] In accordance with the present invention, responsive to commands 101, data extraction tool 100 extracts filtered connectivity and geometrical data for specified layout cell hierarchies at least in part in accordance with specified parasitic effect windows. For the illustrated embodiment, data extraction tool 100 extracts the filtered connectivity and geometrical data for the specified layout cell hierarchies of a deep sub-micron IC design from its hierarchical specification, i.e., specification 106, using control information in rule file 110 and layout cell hierarchy specification 112, and optionally using references in cross references (XREF) 108. More specifically, for the illustrated embodiment, FEX 102 extracts the filtered connectivity and geometrical data for layout layers of the layout nets of a specified layout cell hierarchy of the deep sub-micron IC design, one or more layout nets at a time, from specification 106, using references and control information contained in files 108112. For the illustrated embodiment, rule file 110 contains the control information for the layout layers of a layout cell hierarchy, including their parasitic effect windows, and the control information for FDB 104, whereas layout cell hierarchy specification 112 specifies the layout cell hierarchies of interest.

[0027] Additionally, in accordance with the present invention, the extracted connectivity and geometrical data of the layout cell hierarchies are stored in filtered databases (FBD) 104. For the illustrated embodiment, one FDB 104 is employed for each layout cell hierarchy, and the stored data are indexed by the layout nets of the layout cell hierarchy. In other words, FEX 102 stores the extracted connectivity and geometrical data of each layout cell hierarchy, along with the layout net indices to the extracted data in a FDB 104.

[0028] Hierarchical specification 106 and XREF 108 are intended to represent a broad category of these elements known in art. For example, they may be generated based on a VHDL description of the deep sub-micron IC design using the Calibre™ product, of Mentor Graphics Corporation, Wilsonville, Oreg., assignee of the present invention. Accordingly, hierarchical specification 106 and XREF 108 will not be further described. Beside FEX 102, data extraction tool 100 includes conventional logic for performing various standard file control operations, such as validating file directories/paths, opening and accessing files, computing signatures for the open files, and so forth, that are implementation (e.g. file system) dependent and known in the art. Accordingly, except for FEX 102, data extraction tool 100 will not be further described either. Beside filtered extraction function 102, commands 101, rule file 110, specification 112 and FDB 104 will be described in further detail in turn below.

[0029] Before doing so, it should be noted that while the present invention is being described as being advantageous for extracting connectivity as well as geometrical data for layout cell hierarchies of deep sub-micron designs, the present invention may be practiced to merely extract either connectivity or geometrical data. Furthermore, while the present invention is motivated by the needs of deep sub-micron IC designs, the present invention may nevertheless be practiced for non-deep sub-micron IC designs.

[0030] Referring now to FIG. 2, wherein a block diagram illustrating one embodiment of rule file 110. For the illustrated embodiment, rule file 110 includes one or more layer statements 114 and at least one FDB statement 116. Each layer statement 114 specifies a layout layer of a specified layout cell hierarchy, where extraction is to be performed, and a parasitic effect window for the specified layout layer. An exemplary syntax is LAYER <layer_name> WINDOW <non_negative_number>, where <layer_name> is the name or number of an original or derived layout layer, and <non_negative_number> is the distance from geometric shapes on the named layer beyond which parasitic effects can be ignored. In one embodiment, all capacitance layers, resistance layers, connect layers, and device pin layers are automatically included with predetermined WINDOW distances. In other words, a user of data extraction tool 100 needs not specify these layers and their parasitic effect windows. User specifications will either override or augment the default settings. In one embodiment, the defaulted WINDOW distances for capacitance layers, resistance layers, connect layers, and device pin layers are determined by the maximum distance and width parameters in the capacitance statements in rule file 110. In yet another embodiment, additional control mechanism, e.g. through user environment variables, is provided to request FEX 102 to perform extraction for only user specified layers, and using only user specified parasitic effect windows.

[0031] The at least one FDB statement 116 specifies control information for FDB's 104, including control information for forming the file identifiers for the FDBs 104. In one embodiment, one FDB 104 is employed for each layout cell hierarchy. But notwithstanding that organization, one FDB statement 116 is employed. For this embodiment, FDB statement 116 merely specifies the common portion of the file identification information of the FDB's. The specified control information are concatenated with the identity of each of the layout cell hierarchies to form the unique file names for the FDBs 104. Additionally, in one embodiment, the maximum number of layout nets to have their data stored in the specified FDB may also be specified, as well as the layout nets to be excluded. An exemplary syntax is FDB <file_path> GLOBAL <num>[Exclude Layout|Source <name>], where <file_path> identifies the common pathname to be concatenated with the identities of the layout cell hierarchies to form the file identifiers for the FDB's, <num> denotes the maximum number of layout nets to have their data stored in a single FDB, and Exclude specifies the layout or source nets to be excluded. Examples of such nets are VDD and VSS, i.e. the power and ground nets. Multiple FDB files may be produced such that any one FDB will not contain more than <num>nets.

[0032] Before proceeding with the remaining descriptions of the present invention, it should be noted that while for ease of explanation, the present invention is being described with rule file 110 as having both layer statements 114 and FDB statement 116, those skilled in the art will appreciated that the present invention may be practiced with both types of these statements being specified in either a combined or separate rule files.

[0033] Turning now to FIG. 3, wherein a block diagram illustrating one embodiment of a layout cell hierarchies specification 112 is shown. For the illustrated embodiment, layout cell hierarchies specification 112 is a cell correspondence file used for conventional hierarchical layout verification (LVS) comparison. It includes a number of layout cell name to source cell name correspondence statements 118. Each correspondence statement 118 specifies a layout to source cell correspondence. A layout cell name may appear in multiple correspondence statements 118 denoting correspondence to different source cell names, i.e. a 1:n correspondence. Similarly, a source cell name may also appear in multiple correspondence statements 118 denoting correspondence to different layout cell names, i.e. an n:1 correspondence. In other embodiments, layout and source cell names may also be m to n corresponded. An exemplary syntax for correspondence statements 118 is <layout name><source_name>, where <layout name> is the layout cell name, and <source_name> is the corresponding source cell name.

[0034] Together, the layout cell names of correspondence statements 118 specify the layout cell hierarchies of interest. In other words, for the illustrated embodiment, for the purpose of the subject connectivity and geometrical data extraction, the source cell names are optional. They are included for the conventional hierarchical layout verification (LVS) comparison only. Furthermore, the specified layout cells are LVS correspondence points (also referred to as hcells). An instance of an hcell is referred to as an hinstance.

[0035] FIG. 4 illustrates one embodiment of commands 101 employed to place data extraction tool 100 into operation. For the illustrated embodiment, two commands may be issued: DEX [-full]<rule_file_name><hcell_file_name> where <rule_file_name> specifies rule file 110, and <hcell_file_name> specifies layout cell hierarchies specification 112. The absence of the optional switch “-full” causes data extraction tool 100 to extract connectivity and geometrical data for the primary layout cell only, whereas the presence of the optional switch “-full” causes data extraction tool 100 to extract connectivity and geometrical data for each hcell. More specifically, when the “-full” switch is not specified, data extraction tool 100 extracts connectivity and geometrical data for all global interconnect nets for the top layout cell only, subject to the specified parasitic effect windows for the layers and with each global interconnect net flatten to the top layout cell. When the “-full” switch is specified, data extraction tool 100 extracts connectivity and geometrical data for all global interconnect nets for each and every hcell, subject to the specified parasitic effect windows for the layers and with each global interconnect net flatten to the particular hcell having its data extracted. Note that for the purpose of this application, as conventionally understood by those skilled in the art, the terms “primary layout cell” and “top layout cell” are interchangeable.

[0036] In alternate embodiments, additional degrees of selection, i.e. more granularity between “primary” and “all hcells” are provided. Additionally (or alternatively), data extraction tool 100 is incorporated as an integral part of a multi-EDA function tool. For these embodiments, commands issued to the multi-EDA function tool are provided with a “-fdb” switch to denote the above described DEX function. Furthermore, it should be noted that while the present invention is being described with a command interface, other non-command interfaces, such as a programming interface, or a graphical end-user interface may be employed to facilitate interfacing with data extraction tool 100.

[0037] FIGS. 5a-5cillustrate one embodiment of the operational flow of the data extraction operation of the present invention. As shown in FIG. 5a, for the illustrated embodiment, data extraction tool (DEX) 100 first verifies the specified FDB statement, step 122. The specific verification actions taken are implementation dependent, i.e. the actions are file system dependent, as well as dependent on the nature of integrity checking being performed. Any one of a number of integrity checking techniques known in the art, or none may be employed. Next, DEX 100 determines if the “-full” switch is specified, i.e. whether it is to perform data extraction for the primary layout cell only or for all hcells. In the first case, DEX 100 proceeds to step 126 and selects the top layout cell, whereas in the later case, DEX 100 proceeds to step 128 and selects the next hcell, using e.g. a breadth first approach in traversing the design hierarchy. Recall that the hcell information is provided by layout cell hierarchies specification 112. In either case, DEX 100 then proceeds to step 130 and invokes FEX 102 to extract connectivity and geometrical data for all global interconnect nets for the selected cell, to be described more fully below with references to FIGS. 5b-5c. Upon completion, DEX 100 proceeds to step 132 to determine if additional data extraction operations are to be performed. In the case where the “-full” switch is not specified, the process terminates when extraction for the top layout cell is completed. In the case where the “-full” switch is specified, DEX 100 repeats steps 128-132 until data extractions have been performed for each hcell.

[0038] FIG. 5billustrates one embodiment of step 130 of FIG. 5a. As shown, to extract connectivity and geometrical data for a selected layout cell hierarchy, FEX 102 first opens a FDB for the selected layout cell hierarchy, step 132. Then FEX 102 extracts connectivity and geometrical data for each layout net of the selected layout cell hierarchy, one or more layout nets at a time, until the desired data are extracted for all layout nets of the selected layout cell hierarchy, steps 134-136.

[0039] Skipping now to FIG. 5c, wherein one embodiment of step 134 of FIG. 5bis illustrated. As shown, to extract connectivity and geometrical data for a layout net, FEX 102 first locates the layout net in the placement hierarchy and follow it to its highest location in the placement hierarchy, step 156. Next, FEX 102 selects a next placement the layout net enters, traversing down the placement hierarchy, e.g. depth first, step 158. Then, FEX 102 flattens all geometries belonging to the layout net for each layer specified by the layer statements into the selected top layout cell or hcell, step 160. FEX 102 appends the flattened geometries to a global edge collection (EL) that accumulates all flattened geometries of the layout net on the layer over all placements. In one embodiment, FEX 102 also transforms the layout net's local net number to the layout net's global net number. Upon completion of step 160 for all layers, FEX 102 locates all device pins belonging to the layout net, step 162. Additionally, if the selected layout cell is the top layout cell, FEX 102 also locates all ports belonging to the layout net, step 164. At step 166, FEX 102 determines if more placements are to be processed. If so, FEX 102 repeats steps 158-164 until eventually it is determined in step 166 that all placements have been processed. At such time, step 134 of FIG. 5bis performed for a layout net.

[0040] Returning now to FIG. 5b, eventually FEX 102 determines at step 136 that data have been extracted for all layout nets of the selected layout cell hierarchy. FEX 102 then proceeds to step 138, wherein it oversizes the EL of each layer into a corresponding oversized edge collection OL, in accordance with the specified parasitic effect window of each layer. At step 140, FEX 102 merges all OL's into a single edge collection M (also known as net mask), and place it on a new temporary layer T as the intrinsic geometries of the selected top layout cell/hcell. At step 142, FEX 102 determines Ts interaction with each layout cell. At step 144, FEX 102 optionally creates a pruning array. At step 146, for each layout cell in the selected layout cell hierarchy, FEX 102 obtains the interaction geometries of T as an edge collection IT. Except if the selected layout cell is the top layout cell, then FEX 102 obtains the intrinsic geometries of T instead. Additionally, FEX 102 also obtains the intrinsic geometries for each layer as an edge collection IL, and then compute ML=IL AND IT.

[0041] At step 148, FEX 102 follows the layout net down through the placement hierarchy again. If the pruning array was created at step 144, FEX 102 avoids entering any sub-hierarchy having no interaction with M. For each placement visited, and each layer specified in the layer statements, FEX 102 flattens the geometries of ML to the selected top layout cell or hcell, and appending them to the corresponding EL. If any layer carries node numbers, these local node numbers are also transformed into global node numbers during the flattening process. Note that at this point, the EL of each layer contains all of the flattened net shapes on the layer and all of the flattened geometries on the layer which were sufficiently close to any shape of the net on any layer plus additional geometries flattened because interactions are kept on a cell basis rather than a placement basis. At step 150, FEX 102 sorts and merges each EL created for the selected layout cell. At step 152, FEX 102 replaces each EL with EL AND M. The operation effectively cuts away the additional geometries outside the mask m. Finally, at step 154, FEX 102 writes the extracted connectivity and geometrical data to the open FDB, and upon writing, closes the FDB, to be described more fully below after an embodiment of FDB 104 is described.

[0042] Referring now FIGS. 6a-6b, wherein two block diagrams illustrating one embodiment of a FDB 104 are shown. As illustrated in FIG. 6a, FDB 104 comprises a number of segments 172-186. In particular, FDB 104 includes segment 180 for storing extracted connectivity and geometrical data for multiple nets. As shown in FIG. 6b, for each net, segment 180 includes segment 188 for storing the extracted geometrical data for the various layers of the net, segment 192 for storing the pin collection information for the net, and segment 190 for storing the pin location information for the pins stored in segment 192.

[0043] Referring back to FIG. 6a, for the illustrated embodiment, in addition to segment 180, FDB 104 also includes segment 184 for storing indices to the nets having extracted connectivity and geometrical data stored in segment 180. FDB 104 also includes segments 178, 182 and 186 for storing a table each cross-referencing the layer names/numbers, pin signatures and net names to the nets with data stored in segment 180. Lastly, for the illustrated embodiment, FDB 104 includes segments 172-176 for storing various header information, offsets to the various segments, and various miscellaneous data, respectively. Examples of header information are file identifiers and various integrity checking values. Examples of miscellaneous data are control data about the rule file and so forth.

[0044] FIGS. 7a-7billustrate one embodiment of step 154 of FIG. 5bfor the embodiment of FDB 104 of FIGS. 6a-6b. As illustrated in FIG. 7a, at step 202, FEX 102 writes the header information, miscellaneous data and layer count to the appropriate segments of FDB 104. At step 204, FEX 102 writes the layer information for each layer of the selected layout cell hierarchy to the layer table segment. At step 206, FEX 102 writes the pin signature information to the pin signature table. Finally at step 208, FEX 102 writes the extracted connectivity and geometrical data for each net to the appropriate net segments of the net group segment. FIG. 7billustrates one embodiment of step 208. As shown, at step 210, FEX 102 selects the next net. At step 212, for each device pin extracted, FEX 102 writes the device pin information into the corresponding pin collection segment. At step 214, for each hcell pin extracted, FEX 102 writes the hcell pin location information into the corresponding pin location segment. At step 216, for each port extracted, FEX 102 also writes the port information into the corresponding pin location segment. At step 218, for each layer, FEX 102 writes the geometrical data into the corresponding data segment.

[0045] Finally, at step 220, FEX 102 determines if there are more nets with data to be written. If there are still more nets with data to be written, FEX 102 repeats steps 210-220, until eventually FEX 102 determines at step 220 that all net with data to be written into FDB 104 has been written. At such time, step 154 of FIG. 5bis completed.

[0046] As those skilled in the art will appreciate, with the stored data of FDB 104 being extracted at least in part in accordance with specified parasitic effect windows of the various layers of the selected layout cell hierarchies, and organised with the described indices and cross-reference tables, the stored data of FDB 104 are particularly suitable for subsequent parasitic extraction for various post layout analysis. In one application, the stored data of FDB 104 are retrieved by a parasitic extraction tool, analysed, annotated with electrical modelling information, and then stored into a separate parasitic database (PDB). This application is the subject of co-pending U.S. patent application Ser. No. 09/052,915, filed contemporaneously, having common inventorship and assignee of the present invention. The co-pending application is hereby fully incorporated by reference.

[0047] FIG. 8 illustrates one embodiment of a computer system suitable for programming with the data extraction tool of the present invention. As shown, for the illustrated embodiment, computer system 300 includes processor 302, system bus 304 and standard I/O bus 314. System bus 304 and I/O bus 210 are bridged by bus bridge 308. Coupled to system bus 304 are system memory 306 and video memory 310, against which video display 312 is coupled. Coupled to I/O bus 316 are fixed storage 316, removable storage 318, communication interface 320 and keyboard and pointing device 322. Examples of fixed storage 316 include magnetic and optical disk drives. Examples of removable storage 318 includes magnetic tape drive, diskette drive, CD-ROM drive and DVD drive. Examples of communication interface 320 include modem, ISDN adapter and network adapter.

[0048] These elements perform their conventional functions known in the art. In particular, fixed storage 316 and system memory 306 are used to store a permanent and a working copy of the programming instructions for effectuating the teachings of the present invention, when executed by processor 302. Fixed storage 316 and system memory 306 may also be used to store similar copies of other EDA tools and operating system. The permanent copy of the programming instructions that effectuate the present invention (when executed by processor 302) may be pre-installed in the factory by the manufacturer of computer system 300. Alternatively, it may be loaded from a distribution medium 319, such as a tape, a CD-ROM, or a DVD, through removable storage 318, or from a remote server 321 through communication interface 320. Furthermore, data extraction tool 100 and FDB 104 may be implemented on different ones of computer system 300 or equivalent, communicatively coupled to each other. The constitutions of these elements are known. Any one of a number of implementations of these known elements may be used to form computer system 300.

[0049] While for ease of understanding, the present invention has been described in terms of the above illustrated embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The present invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of restrictive on the present invention.

[0050] Thus, a method and apparatus for extracting and storing connectivity and geometrical data for a deep sub-micron IC design has been described.