Performance analysis of an IC-mask design rule check and net extraction software suite

The authors provide a detailed analysis of the runtime and workspace requirements of a software suite for the design rule check and netlist extraction of IC mask sets. The system allows the user to describe the components of a circuit (transistors, contacts, diodes etc.) in terms of an acyclic graph (the formula graph), where the nodes represent the geometric features and the edges represent the topological relationships between these features. The graph can easily be converted into textual format, using a mask verification language (MVL). MVL is partly procedural and partly asynchronous, with the instruction set of the procedural part having been chosen with great care to allow extensive optimisation of the necessary mask operations by the MVL compiler. The analysis shows that the preprocessor, geometry processor and topology processor execution times and workspace requirements are all approximately O(N) and O(N^0.5), respectively. Throughout the paper, an array of I²L adder circuits is used as an example. One of the necessary MVL code listings is given as an Appendix.