Real-time DRC in Expert Layout Editor

1. Introduction

In this paper we introduce one of the latest and most advanced features of Silvaco's Expert Layout processor for Windows NT ­ DRC Guard. DRC Guard is fully functional real-time design rule checker that works in background mode and makes extensive use of multithreading/ multiprocessor capabilities of operating system. Based on a specially optimized and tuned DRC engine, DRC Guard works extremely fast and reports results of local DRC directly into the layout area in convenient user-friendly way. DRC Guard automatically checks modified part of the layout immediately after the modification is made. It also can perform instant DRC in any part of layout at the user's request.

 

2. DRC Guard

2.1 Real-time background DRC

2.1.1 Minimizing response time
One of the most interesting problems, which arise in real-time DRC system implementation process, is the trade-off of response time and number of DRC checks. On the one hand, to be of use this system should be able to handle DRC scripts that contain substantial number of commands. Often some very useful DRC checks can't be expressed by means of a single check command. Implementation of such checks may include generation of intermediate layers by, boolean or resize operations. Several such not very sophisticated multi-command checks together may create DRC script consisting of hundreds or even thousands of commands which should be executed in real-time.

On the other hand, a real-time DRC system should not get in the way and make the user wait until execution of the script is completed blocking all layout functions. No matter how fast is the internal DRC engine, any non-trivial DRC script being applied in straightforward way to each modification made to layout will noticeably and unacceptably increase the editor response time.

To resolve this conflict, special techniques have been developed that made it possible to implement the real-time background DRC. Given a multithreaded operating system (such as Windows NT), the main idea is that real-time DRC is separated into a special low-priority background thread while layout editing is performed by a high-priority foreground thread. Instead of calling DRC directly after each modification, the layout editor places a special record called check request into the real-time DRC queue. A check request contains full information about what kind of modification was made, which object was modified, where it is located, etc. Background DRC reads check requests from the queue one by one and performs all necessary checks in the corresponding area of layout. The real-time DRC queue is a communication link between the layout editor and the background DRC (see Figure 1).

Figure 1. Layout editor and background DRC communication

 

 

It is obvious that DRC system built on these principles will not necessary report all DRC violations immediately after they are introduced. But the time gap between an erroneous edit and the error report can be negligibly small provided the DRC engine is accurately implemented and tuned within the whole system. The key is that care should be taken to minimize the amount of information processed by the background DRC without affecting check accuracy (see "Minimizing system resource usage" section).

Separation of real-time DRC into an independent thread also makes it possible to control its execution priority with respect to the priority of the layout editor. The higher is the priority of DRC the shorter is its response time. The lower is the priority of DRC the less noticeable is its slowing influence on layout editor functions. Another great advantage of a multithreaded architecture is that on multiprocessor system the real-time DRC thread will work on a separate processor. It will result in a substantial increase of the performance of the background DRC as well as the performance of the layout editor.

2.1.2 Database Synchronization

Although our real-time DRC works as a background thread parallel to the layout editor thread, the former is not completely independent from the latter. The most obvious point of competition between these threads is the moment when they try to access the common layout database simultaneously. The execution of DRC on some part of layout takes some period of time while user is free to modify any part of layout at any moment. Under this assumption it appears to be a reasonable technique to make a separate copy of local part of layout to be checked ­ the layout snapshot. After that the background DRC is executed on that copy rather than on original layout. In this case the problem of database access synchronization will take place only at the moment of snapshot preparation and can be easily solved by means of standard thread synchronization methods provided by the operating system.

Although such technique of snapshot processing of layout works well with batch mode fire-and-forget background DRC, it is not free of drawbacks when used in real-time background DRC. Suppose that user is making some modifications in the part of layout which is being processed by DRC at same time. It means that at any moment the snapshot taken for DRC may become out of date. If it does, chances are that the results of this script execution will be obsolete as well. To prevent real-time DRC from generating obsolete results such, situations should be detected. DRC execution stopped and modified area scheduled for recheck. The same applies to check requests waiting in the real-time DRC queue. Some of them may become obsolete before they are processed and should be excluded from the queue. This technique of exclusion of obsolete check requests leads to substantial increase in performance of real-time DRC.

 

2.1.3 Minimizing System Resource Usage

The amount of data handled by conventional DRC can be very large and usually does not fit into the internal memory requiring additional external storage space. However, it makes sense to use only RAM for real-time DRC in order to increase its performance thus reducing its response time. Of course, when real-time DRC is implemented as background thread care should be taken to prevent it from occupying too much system memory because it always leads to the drop of overall system performance. The simplest way is to set a limit for the amount of memory allocated for real-time DRC needs and cancel DRC script execution whenever the limit is exceeded. The corresponding check request from the real-time DRC queue is removed without processing.

Under assumption that the amount of memory background DRC thread can occupy is limited, the problem of most effective utilization of that memory arises. An effective method of optimization of real-time DRC resource usage is developed. It will be referred to as selective DRC script execution. When a designer is editing a layout most of modifications he makes are localized in a particular area and particular layer of the layout. Most frequently used operations such as creation or deletion of object or changing shape of object locally affect contents of only one layer. Hence, to check whether the result of such operation is violating any of DRC requirements it is sufficient to execute only those operations of DRC script, which are related to the modified layer. The problem of extraction of the sequence of the operations to be executed is non-trivial because any check operation can reference layers of the layout directly as its operands as well as indirectly through a chain of layer generation operations (boolean, resize etc.). The informational dependency graph of script commands can be used to solve this problem efficiently [2]. When the sequence of DRC commands is determined, the set of input layers for this sequence can be easily obtained. Only layers from this set and their objects from area of modification should be included in the layout snapshot before executing the DRC script. In most cases such preliminary analysis of the script allows faster checking of the modified portion of layout because it reduces the amount of layout data to be prepared for DRC processing and decreases the number of commands to be executed.

 

2.2 Using DRC Guard

2.2.1 Operations Recognized by DRC Guard

The background real-time DRC based on the principles described above and called DRC Guard was recently introduced into Silvaco's Expert Layout Processor. Once set up, DRC Guard watches all modifications which are made to the layout and generates immediate visual report of all detected errors. Internal DRC engine used in DRC Guard is based on very efficient scan-line approach [1]. It allows DRC Guard to deliver check results in true real-time. It is worth to mention that DRC Guard supports all types of error report conventional DRC does including polygon-shaped errors reported by check operations with GT/GE comparison types (see "User interface" section and Figure 5).

Setup of DRC Guard is very simple and includes ordinary DRC script written in Savage DRC language (see Figure 2). Not only check operations but also any command of the language can be used in DRC Guard script.

Figure 2. DRC Guard Setup is through a user defined options menu.

 

Check requests are placed into DRC Guard queue after each application of any editing operation such as Create Object, Delete Object, Modify Object, Stretch, Move, Copy, Cut, Paste etc. Being built into hierarchical layout editor, DRC Guard is able to handle editing operations not only when they are applied to polygons but also when they are applied to instances of other cells in current one. DRC Guard can also perform quick DRC check of any rectangular area of layout by user's request (see Figure 6). DRC Guard also supports Undo command. Moreover, DRC Guard produces correct and useful results in Expert's Edit-in-Place mode of hierarchical editing.

2.2.2 Error Report on Hierarchical Layout

Since it is implemented in a hierarchical layout editor, DRC Guard takes into account hierarchical structure of layout when performing DRC checks and displaying errors. The purpose of DRC Guard is real-time detection of DRC violations caused by user's modifications currently made. It aims for finding and reporting of errors of this kind only. If DRC Guard finds some errors that are unlikely to be caused by user modifications, it does not report them to avoid overloading of workspace with irrelevant DRC error marks. To carry out DRC check of entire layout or its particular part with full error report designer can use batch-mode DRC or DRC in Area.

The problem of filtering out irrelevant errors becomes more complicated when DRC is executed on hierarchical layout, because in this case designer can work not only with polygonal shapes but also with instances of other cells. Incorrect placement of the instance may induce DRC violations, which also have to be detected. DRC Guard considers a DRC error as relevant and reports it if the error meets certain conditions. More concretely, when designer is working with cell C DRC Guard reports all errors that would be dispatched to that cell C in accordance with nearest common parent rule used in hierarchical DRC [3]. To get all information necessary for application of this rule DRC Guard makes use of hierarchical information inheritance technique [3].

In simple words, in its search for DRC violations in current cell C DRC Guard checks the following relations:

a) between polygons of cell C;

b) between direct and indirect instances of other cells in cell C and polygons of cell C;

c) between different direct and indirect instances of other cells in cell C.

It is very likely that the actual reason of DRC violation detected by DRC Guard in cell C resides nowhere else but in cell C [3].

2.2.3 DRC Guard in Edit-In-Place

When user is editing cell contents in the Edit-in-Place (EiP) mode the situation is rather different from ordinary editing mode. The nature of difference is that the cell is edited in its particular placement ­ the instance ­ and therefore it is surrounded by instance's environment, i.e. objects of its parent cell. At any moment user can change edited cell by diving one level down via instance of another cell as well as by climbing on level up. Chain of instances used by the user to move between levels of hierarchy is called the Edit-in-Place chain (EiP chain). EiP chain begins in the topmost cell and ends in the current edited cell. Any modification made on certain level of hierarchy may induce DRC violation not only on that level but also on any higher level up to the topmost one. Moreover, before leaving modified cell user has to choose the way of its integration into project structure. The options are the following:

1. Explode instance ­ the instance of edited cell is replaced with its polygons in parent cell. DRC Guard checks
the area of the former instance in parent cell and environments of all instances from EiP chain.

2. Save Instance as Separate Cell ­ DRC Guard checks environments of all instances from EiP chain including
environment of edited instance in parent cell.

3. Change Edited Cell ­ DRC Guard checks environments of all instances of this cell in all their parent cells up
to the topmost one (including instances from EiP chain).

Such behavior of DRC Guard in EiP mode may seem rather complicated but it leads to effective detection of all DRC violations caused by modifications made in EiP mode. The large numbers of check requests that may be generated after EiP modifications do not represent any problem because DRC Guard is implemented as background thread.

 

2.2.4 User interface

All DRC errors detected by DRC Guard are immediately displayed on the screen in form of blinking markers. The markers can have different shape depending on type of particular violation. For instance, distance violations are displayed in form of two-headed arrows and intersections are marked by circles. When mouse cursor hovers above particular error mark the label containing information about this error is displayed. The information includes type of violation and DRC rule that is violated (see Figures 3, 4, 5).

Figure 3. Intersection marker (Intersection check)


Figure 4. Minimum distance violation markers (InDistance LT check).

Figure 5. Maximum distance violation markers (OutDistance GE check).

 

 

Another component which makes DRC Guard's user interface more convenient is the Error Locator. Although the main purpose of DRC Guard is to check correctness of local layout modifications, it can easily handle any non-local editing operation. Note that such operations as, for instance, Move can change location of all currently selected objects. Depending on distribution of selected objects over the layout area, application of this operation may result in local modification as well as in global one affecting the entire layout. In case selected objects are relatively far one from another, operation Move can produce DRC errors outside view area. It means that DRC Guard will actually detect all errors but user probably will not be able to see all error markers on the screen. In such situations Error Locator could be very useful. Error Locator consists of small display containing eight arrows and central dot (see Figure 7). Each of eight arrows represents particular direction (North, Northeast, East etc.) and begins to blink if DRC Guard has detected violation in corresponding area outside the screen. When mouse cursor hovers over blinking arrow in Error Locator, the amount of errors found in that invisible area is displayed. The central dot provides the same information for visible screen area. Clicking on any of the arrows causes the layout to pan so that the nearest error in corresponding direction moves to the center of view area. This provides simple and convenient way of navigating DRC Guard errors.

Figure 6. Check Area function of DRC Guard.


Figure 7. Error Locator.

 

A number of important additional steps were taken in order to achieve further improvement of DRC Guard performance, reliability and convenience. We only mention some of them here. First, the DRC Guard setup dialog box offers three ways to specify the script: manual typing, semi-automatic command generation by means of dialog boxes, loading from file. Second, the DRC Guard script is analyzed, compiled and optimized in special way at setup stage to reduce the initialization time of processing of each check request. Third, DRC Guard tracks the location of user's working area on the layout and processes in first turn check requests that are closer to that area than others. Fourth, the DRC Guard thread is carefully isolated from the layout editor thread so that accidental crash of DRC Guard doesn't result in crash of the entire layout editor and data loss.

 

3. Conclusion

The real-time DRC the Expert Layout Processor is evolving very rapidly in direction of introducing new user interface features, new types of DRC commands and speeding up overall DRC performance. In its current state DRC Guard is convenient and powerful component of the layout editor, which improves speed and quality of custom design of integrated circuits.

 

References

  1. V. Feinberg. Geometrical problems of VLSI computer graphics,
    Radio i Sviaz, Moscow, 1987.
  2. Application of Scan Line Methodology to Perform Metric Operations in DRC. Simulation Standard.
    Volume 8, Number 12, December 1997, pp. 7--9.
  3. Savage Enhanced with Recognition and Reporting of Hierarchical Structure of Errors. Simulation Standard.
    Volume 9, Number 3, March 1998, pp. 1-4.