Patent Publication Number: US-7913206-B1

Title: Method and mechanism for performing partitioning of DRC operations

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application claims the benefit of U.S. Provisional Application No. 60/611,003, filed on Sep. 16, 2004, which is hereby incorporated by reference in its entirety. 
    
    
     BACKGROUND 
     The invention relates to technology for implementing electronic design automation tools, and in particular, design tools for performing parallel and multithreaded design rule checks (DRC) for an integrated circuit (“IC”) design. 
     An IC is a small electronic device typically formed from semiconductor material. Each IC contains a large number of electronic components, e.g., transistors, that are wired together to create a self-contained circuit device. The components and wiring on the IC are materialized as a set of geometric shapes that are placed and routed on the chip material. During placement, the location and positioning of each geometric shape corresponding to an IC component are identified on the IC layers. During routing, a set of routes are identified to tie together the geometric shapes for the electronic components. 
     A set of design rules are established to ensure that the objects/shapes on the IC design can be properly manufactured. These rules are usually established by the foundry that will produce the IC chip. A DRC tool is used to check for violations of the rules on the IC design. 
     Given the large numbers of components in a typical IC design and the large number of rules that must be checked, it often takes a long period of time and a significant amount of system resources (both for CPU and memory) to perform a DRC check on a given IC design. This provides the motivation for EDA tool vendors to provide a method for parallelizing the DRC operations that must be performed against an IC design. 
     Solutions have been proposed to partition data for DRC operations to allow parallelization of the DRC process. There have been several suggested approaches for data partitioning. A first approach is partitioning based upon the rules and a second approach is based on hierarchy. Conventionally, these are mutually exclusive approaches, and while there is some efficiency in each one of them, these are also problems with each approach. 
     When data partitioning is performed based on rules, one of the most significant problems is that network jamming may occur. This is because the entire design file (e.g., a GDSII file) is sent to each distributed computer that is processing in parallel based upon the rules. This means that there is a lot of traffic being placed on the network. 
     The other approach is to partition the design using a hierarchy where the system sends different blocks affecting the design from one distributed processing unit to another. The problem with data partitioning using this approach is that when the system is trying to verify the top level, problems dealing with the connectivity between the blocks may exist. Conventional systems cannot efficiently or optimally manage this type of problem. 
     There may also exist other proposed approaches, such as windowing. However, these other approaches are also mutually exclusive approaches, and while there is some efficiency in each one of them, there are also problems with each approach. 
     Therefore, it is highly desirable to implement an improved method and mechanism for data partitioning for a DRC tool that will efficiently and effectively allow parallelization and multithreading to occur for DRC analysis of the IC design. Some embodiments of the invention provide an improved method and mechanism for data partitioning for a DRC tool that allows parallelization and multithreading to occur for DRC analysis of the IC design. Data partitioning is performed in some embodiments to allow some of the data to be processed in parallel by distributed processing units, while allowing other of the data to be processed in parallel by multiple threads. This can be accomplished by identifying different types of rules and data, and having different types of processing for the different types of rules and data. Certain types of rules/data will be processed with multi-threaded processing and other types of rules/data will be processed in parallel using distributed processing units. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  illustrates a system for performing DRC operations using data partitioning in accordance with some embodiments of the invention. 
         FIG. 2  shows a flow of a process for performing DRC operations using data partitioning in accordance with some embodiments of the invention. 
         FIG. 3  provides an illustrated example of design portion to be analyzed. 
         FIG. 4  illustrates an example computing architecture with which embodiments of the invention may be practiced. 
     
    
    
     DETAILED DESCRIPTION 
     An embodiment of the present invention provides an approach for data partitioning that provides more efficient parallel physical verification (PV) processing of an IC design in an electronic design automation (EDA) tool. DRC is an example of one type of PV, processing that may be performed upon an IC design. In one embodiment, data partitioning occurs to allow some of the data to be processed in parallel by distributed processing units, while allowing other of the data to be processed in parallel by multiple threads. 
     In one embodiment, this is accomplished by identifying different types of rules and data, and having different types of processing for the different types of rules and data. Certain types of rules/data will be processed with multi-threaded processing and other types of rules/data will be processed in parallel using distributed processing units. 
       FIG. 1  shows a diagram of an architecture for data partitioning according to an embodiment of the invention. In this diagram, there are three different type of shapes. The oval shapes in  FIG. 1  represent data. The rectangular shapes reflect operations. The conical shapes represent a database or data storage element. 
     On the left side of the diagram, shown is an input file for the verification system, which is a rule file  102 . The rule file  102  contains the design rules to be checked during the DRC process. Another input file is shown in the center of the diagram, which is the input design file  104 , e.g., in GDSII format, which needs to be verified. An example of a common database type that can be employed to store and access data, such as the GDSII data, is based upon the Open Access™ standard. Open Access (OA) is a standard for IC designs that allows foundational interoperability for design data between different types of PV tools. More information regarding Open Access can obtained from the Silicon Integration Initiative, Inc. (Si2), an organization that promulgates standards for the EDA industry (www.si2.org). 
     A partition action on the left side of the diagram step is performed by a rule based dispatcher  110 . The rules based dispatcher  110  modifies the rule desk into two sections. One of them is a modified rule file  112  that will be used for the multi-threading operations, and the second one is further modification that is not used to partition the data, but to create instructions  114  of how to further partition the data. So at this point, there has not yet been any distribution of GDSII data. Instead, only instructions on how to partition the data have been generated. Essentially, the system will determine how to partition the data, and sending instructions to the queue manager over the network will not have any significant impact on the run time or network usage at this point. 
     In the next action, the queue manager  116  will manage and obtain a list of jobs to process; here, the queue manager will manage the generation of the instruction set  2   118 . Instructions are sent to each of the dedicated processing units  120 . In addition, the GDSII files are sent to each of the respective processing units. Processing will occur at the different distributed processing units in parallel based upon the rules to check corresponding to the instruction set. 
     Based upon this processing, any detected errors will be collected in an error file. The error files will be transferred to the report storage mechanism on the right-hand side of the diagram. 
     In one embodiment, the report storage mechanism will communicate immediately with the users about the errors  124  that are identified, without waiting for processing of the entire design to be completed. If so, then once the first error (or first grouping of errors) is detected, the user will have access to those reports and does not have to wait until the entire job is completed. Thus, the user will be able to start fixing problems immediately as they were found. This provides a significant advantage over prior approaches that provides errors only after all or a substantial portion of the processing has been completed. For example, consider a DRC processing job that would normally take 20 hours to complete. In the present embodiment, if the first error is detected at 1 hour into the processing, rather than waiting the entire 20 hours before producing an error for the user, the user is immediately granted access to information about the detected error. This provides a much improved response time over prior art solutions. 
     Therefore, the partitioning of the data that is on the left side of these diagram describe the parallel processing activities. It has a reduced load over conventional parallel processing approaches since reduces the load that is placed on the network. In addition, the queue manager can adjust the load that is placed on the network and the dedicated processors to optimally allocate work in the system and to minimize excessive load on the network and other system components. 
     Now an explanation will be provided of the flow that is at the center of the diagram. What happens here is that the rule file was partitioned into instruction sets, and in the middle of the diagram, the modified rule file is sent to the loader  124 . The loader loads relevant part(s) of the GDSII file into an in-memory database  126 . So, one thing being done is a top-down hierarchical step is processed, e.g., the geometries that overlaps one of the cells. 
     Once this has completed, the block-based dispatcher will perform its operations. The dispatcher can operated based upon area, net, and/or rule based controls  128 . At this phase of the operation, the data is partitioned into blocks, and based upon the given instruction set, the further partitioning can be handled by different dedicated threads/processors. The dedicated threads/processors will perform processing on its assigned blocks and will modify the in-memory database. 
     In one embodiment, the flow that appears at the center of the diagram is a multithreaded flow. With multithreaded processing in one embodiment, the multiple threads share the same memory. If the parallel threads share the common data in memory, the performance of the system is significantly improved, since the GDSII data is loaded only once for this operation. 
     Once results on the block are completed, an error file can be generated that is stored in the report storage mechanism. As before, it is noted that this accelerates the access that is granted to users of information about detected errors in the IC design. 
     There is another level of the rules-based dispatcher  108  that is implemented in this architecture. It may occur that jobs originating with the multi-threaded portion of the system actually should be processed in the parallel/distributed portion of the system. The rules-based dispatcher  108  will essentially fork a process in the distributed environment and send an instruction set  130  to the queue manager on the left side of the diagram. These jobs generated in the middle portion of the diagram can therefore be processed in a parallel distributed environment controlled by the queue manager. 
     Thus, the system has different dispatchers that work in the different stages of the verification process. A first advantages provided by this system are that it reduces the loading of the network, since a portion of the parallel processing is performed in a multi-threaded environment in which the memory is shared. In addition, this system significantly accelerates the time to error much faster than existing approaches. Moreover, this system allows integrated processing using both multi-threading and distributed computing, providing the advantages of both approaches. 
     The system integrates control between the queue manager(s) and the dispatcher(s) to allocate work in the system. The dispatchers is configured with intelligence about the data to be processed. The dispatcher determines which part of the processing is performed with multithreading and which portion is performed in a distributed manner. In one embodiment, there are three different criteria. One of them is hierarchy based, the second one is rule-based, and the third one is a windowing base. The dispatcher is configured to identify what kind of rules/data should be executed at each portion of the system. 
     An approach for implementing a system having both windowing and rules-based criteria is disclosed in co-pending U.S. application Ser. No. 11/225,816, entitled “Method and System for Implementing Compilation and Execution of DRC Rules”, filed on Sep. 12, 2005, Atty. Docket No. CA7044922001, which is hereby incorporated by reference in its entirety. Further information about an exemplary approach for implementing rules-based parallelism is described in co-pending U.S. application Ser. No. 11/225,815, entitled “Method and System for Parallelizing Computing Operations”, Atty. Docket No. CA7045492001, filed on Sep. 12, 2005, which is hereby incorporated by reference in its entirety. Further information about an exemplary approach for implementing parallelism using windows is described in co-pending U.S. application Ser. No. 11/225,853, entitled “Method and System for Implementing Parallel Processing of Electronic Design Automation Tools”, Atty. Docket No. CA7045322001, filed on Sep. 12, 2005, which is hereby incorporated by reference in its entirety. 
     The queue manager(s)  116 ,  132  acts as the resource manager for the system. It knows from a machine point of view where to start directing work traffic in the system. The queue manager  116  on the left side of the diagram monitors and allocates work among the different processing units that are distributed in the system. The queue manager  132  in the middle of the diagram monitors and allocates work among the threads in the system. System information may be made available to the queue manager(s) to allow optimal allocation of work among the available resources in the system. 
       FIG. 2  shows a flowchart of a process for data partitioning according to an embodiment of the invention. The process begins by identifying the design data and rules to use for the DRC processing ( 202 ). For example, the design data may be a given GDSII file and the rules may be a rule deck that is supplied by the foundry that will be manufacturing an IC product based upon the design file. 
     A determination is made regarding which portion of the data should be processed using distributed processing ( 204 ). A determination is also made regarding which portion of the data should be processed using multi-threaded processing ( 206 ). It is noted that in this embodiment, it may be determined that a subset of data that has been associated with multi-threaded processing may be redirected to be processed using distributed computing ( 208 ). While not shown in the flowchart, in an alternate embodiment, a subset of data that has been associated with distributed processing may be redirected to be processed using multi-threaded computing. The identified data is processed with multi-threading at  210 . Identified data is processed with parallel processing at  212 . 
     During processing, the process will communicate immediately with the users about the errors that are identified, without waiting for processing of the entire design to be completed  214 . Once errors are detected, the user will have access to those reports and does not have to wait until the entire job is completed. Thus, the user will be able to start fixing problems immediately as they were found. If no errors are found, then processing is continued. 
     To provide an illustrated embodiment, reference will now be directed to  FIG. 3 . Assume that  FIG. 3  shows a portion of an IC design having blocks A, B, and C. Numerous metal lines are shown overlaid on this portion of the IC design. 
     In one embodiment, the rule based dispatcher will be configured to handle metals differently from other design elements and to create instructions that state that all metal is to be checked in the flat mode. Spacing rules, e.g., width-dependent spacing rules, will also be checked in flat mode in this embodiment. Metal to via checks in one embodiment can be checked by a windowing application. The rule-based dispatcher will generate the instruction sets for the different engines and will submit the job into the queue manager. The queue manager will modify the instruction sets and submit jobs to different machines. If it is assumed that the system has many dedicated processors, then at this stage, the above checks will be performed in parallel at the distributed processors. 
     Modified rule files will be generated for multi-threaded processing that exclude the checks that are being performed in a flat mode, and therefore those checks will not be submitted into the main flow and sent to the loader. The loader will get the modified rules set, and based on the modified rules, will load the appropriate portions of the GDSII data into an in-memory database. The top-down hierarchical data for the IC design will be loaded. In this example, this means that the metal overlap on top of blocks A, B &amp;C will be calculated and this includes the polygon elements that overlap blocks A, B, and C. Referring to  FIG. 3 , shown are dotted rectangles that are drawn around blocks A, B, and C. Information about the block area surrounding blocks A, B, and C will be calculated and stored in-memory database. 
     Once this process is completed, then the top-down hierarchical analysis is completed and at that point the block-based dispatcher can work to help distribute work. In the present example, the dispatcher takes block A and its surrounding, takes block B and its surrounding, and takes block C and its surrounding and creates an instruction set that is used by the queue manager to assign jobs to the different threads in the multi-threaded system. So at this point, since there are multiple threads operating upon blocks A, B, and C in parallel, this processing should complete in an efficient manner. 
     It may be determined that a portion of this data should also be processed in a distributed manner. For example, the dispatcher may determine that block C should be processed in a distributed parallel manner, e.g., because it is determined that some of the rules should be processed flat rather than hierarchically. If this is the case, then an instruction set is created and sent to the queue manager for the distributed processing. The queue manager will assign job(s) to the dedicated processors in the distributed system to handle processing of the rules for block C. 
     The system will modify the in-memory database based upon the processing. The identified errors are generated and made available to the user immediately, and therefore this allows results to reach the top level very quickly. 
     System Architecture Overview 
       FIG. 4  is a block diagram of an illustrative computing system  1400  suitable for implementing an embodiment of the present invention. Computer system  1400  includes a bus  1406  or other communication mechanism for communicating information, which interconnects subsystems and devices, such as processor  1407 , system memory  1408  (e.g., RAM), static storage device  1409  (e.g., ROM), disk drive  1410  (e.g., magnetic or optical), communication interface  1414  (e.g., modem or ethernet card), display  1411  (e.g., CRT or LCD), input device  1412  (e.g., keyboard), and cursor control. 
     According to one embodiment of the invention, computer system  1400  performs specific operations by processor  1407  executing one or more sequences of one or more instructions contained in system memory  1408 . Such instructions may be read into system memory  1408  from another computer readable/usable medium, such as static storage device  1409  or disk drive  1410 . In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and/or software. In one embodiment, the term “logic” shall mean any combination of software or hardware that is used to implement all or part of the invention. 
     The term “computer readable medium” or “computer usable medium” as used herein refers to any medium that participates in providing instructions to processor  1407  for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as disk drive  1410 . Volatile media includes dynamic memory, such as system memory  1408 . Transmission media includes coaxial cables, copper wire, and fiber optics, including wires that comprise bus  1406 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. 
     Common forms of computer readable media includes, for example, floppy disk, flexible disk, hard disk, magnetic tape, any other magnetic medium, CD-ROM, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, RAM, PROM, EPROM, FLASH-EPROM, any other memory chip or cartridge, carrier wave, or any other medium from which a computer can read. 
     In an embodiment of the invention, execution of the sequences of instructions to practice the invention is performed by a single computer system  1400 . According to other embodiments of the invention, two or more computer systems  1400  coupled by communication link  1415  (e.g., LAN, PTSN, or wireless network) may perform the sequence of instructions required to practice the invention in coordination with one another. 
     Computer system  1400  may transmit and receive messages, data, and instructions, including program, i.e., application code, through communication link  1415  and communication interface  1414 . Received program code may be executed by processor  1407  as it is received, and/or stored in disk drive  1410 , or other non-volatile storage for later execution. 
     In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be, evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. For example, the above-described process flows are described with reference to a particular ordering of process actions. However, the ordering of many of the described process actions may be changed without affecting the scope or operation of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense.