Dragon DRC: Performance Improvement Techniques

Introduction

Dragon DRC is a new advanced hierarchical DRC system. The design principles this system is based on are carefully selected to ensure that Dragon DRC will deliver maximum performance in different execution environments. Designed as a highly adaptive and truly hierarchical DRC system, Dragon is able to execute DRC scripts much faster than any flat DRC system in most real-life cases. An important feature of Dragon is its multithreaded parallel processing capabilities implemented at several system levels including parallel processing of layout, parallel execution of DRC commands and a number of internal parallel algorithms. Even though a well-thought-out implementation of the parallel hierarchical approach to layout DRC alone results in substantial performance boost over flat DRC system, Dragon is also able to carry out various preliminary and run-time optimizations of DRC script. The main purpose of the above optimizations is to generate the optimal schedule of execution of DRC commands, so that all components of the system will be used with maximum efficiency throughout the whole execution process, both in single processor environments and in multiprocessor ones.

 

Operation Coupling

To improve DRC performance on single processor systems, Dragon implements a separate scheduling algorithm called operation coupling. This technique is based on the fact that an atomic operation of the internal DRC engine of Dragon can be much more complex than an average single operation of a typical DRC script. Several operations from the script can be combined into one internal DRC operation and executed simultaneously, which is considerably faster than executing them one by one.

A straightforward example of such optimization can be easily built from several Boolean operations (see Figure 1).




Figure 1. Simple example of operation coupling.


However Dragon's script optimization capabilities are not limited to merging simple Boolean operations into Boolean formulae [1]. Implementation of almost all supported DRC operations in Dragon is based on various modifications of the widely known scanline technique [2]. The fact that internal algorithmic engines for operations from different groups, such as Boolean, Select and Spacing Check operations, are based on the same foundation opens great opportunities for effective operation coupling. The separate component of Dragon DRC called DRC script execution scheduler is responsible for detecting and realizing all reasonable operation coupling opportunities in a given DRC script. On multiprocessor systems the same component of Dragon DRC also takes care of generating parallel execution schedule for the script (see below).

 

Parallel Processing at Script Level

Even though the operation coupling technique described above possesses a substantial potential for optimization of DRC script execution process, Dragon takes additional steps in order to achieve even higher DRC performance on multiprocessor systems. As was mentioned above, there is a number of relatively independent parallel DRC algorithms implemented in Dragon.

The DRC script execution scheduler introduced above is also responsible for parallel DRC script execution. Both parallel execution schedule and operation coupling schedule for DRC script are created by analyzing the informational dependencies of operations within the script. The primary target of the scheduler is to split the graph of informational dependencies of the given DRC script info separate operation clusters, each consisting of a bunch of easily coupled and highly dependent operations. After that it can generate one or more coupled DRC operations for each cluster and, finally, produce a schedule of parallel execution such that independent operations from different clusters are carried out simultaneously.

It is easy to see that in many cases the same set of DRC operations can be optimized in accordance with either operation coupling or parallel execution approach (see Figure 2).




Figure 2. Operation coupling and parallel execution - two
alternative ways of DRC performance improvement.




Because of that it is often possible to generate several execution schedules for the same DRC script. Either one might be optimal depending on different external parameters, i.e. parameters of DRC execution environment (including the number of available processors, amount of available virtual and physical memory and other system parameters). For this reason Dragon is equipped with a number of well-balanced heuristic criteria which are used to analyze the execution environment so as to properly adjust the DRC script scheduler priorities and fine-tune its internal algorithms. As a result, it is expected to generate the execution schedule optimal for a given DRC script in a given execution environment.

 

Parallel Processing at Command Level

Still another important parallel processing technique is employed by Dragon during the execution of one DRC command. The technique is layout-related, not DRC script-related as the one above. Working with a hierarchical layout, Dragon executes each DRC operation in cell-by-cell manner. In multiprocessor environment groups of cells can be processed simultaneously, i.e., in parallel mode. Of course, in most practical cases a hierarchical layout cannot be treated as just a collection of independent cells. On the contrary, internal geometry of one cell may have many interactions - overlaps - with geometry of other cells in many places in the layout. This can substantially complicate its hierarchical processing during DRC. In order to obtain correct and exhaustive DRC results and at the same time increase system's performance, Dragon uses a number of algorithms to preprocess the existing layout hierarchy. It dose this by rebuilding it in order to decrease the amount of cell interaction in the layout (resolving overlaps). That includes selective flattening of overlapping cell instances, overlapping instance merging, array decomposition and other techniques of cell interaction resolving. It is important to mention here, that whatever changes were made to the initial layout hierarchy by internal Dragon algorithms, the DRC results can always be reported in terms of the original hierarchy [3].

By preliminary resolution of cell interactions in the layout, Dragon can significantly increase the efficiency of parallel cell processing during DRC. The special component of the program called cell processing scheduler keeps track of all known or potential cell interactions and makes sure that all cells that can be processed by parallel threads are processed that way. The growth of the number of parallel threads created by Dragon at all supported levels of parallel processing is limited by available system resources.

 

Conclusion

The powerful performance improvement approaches described above are built into other proven by time, carefully tuned and fit together components of Dragon DRC system to guarantee its top performance.

References

  1. Application of Scan Line Methodology to Perform Metric Operations in DRC. Simulation Standard. Volume 8, Number 12, December 1997, pp. 7-9.


  2. V. Feinberg. Geometrical problems of VLSI computer graphics, Radio i Sviaz, Moscow, 1987.


  3. Savage Enhanced with Recognition and Reporting of Hierarchical Structure of Errors. Simulation Standard. Volume 9, Number 3, March 1999, pp. 1-4.