SCANLINE DATA STRUCTURE PROCESSOR FOR VLSI GEOMETRY CHECKING.

An architecture to support VLSI geometry checking tasks based on scanline algorithms is proposed. Rather than recast the entire verification task in hardware, primitives around which geometry checking tools can be built are identified, and the feasibility of accelerating two of these critical primitives is examined. Emphasis is placed on the operations of Boolean combinations of mask layers, and region numbering within a mask layer. This architecture operates on a realistic representation of masks as a sorted stream of possibly oblique edges. The architecture can be viewed as directly interpreting the operators that manipulate the relevant scanline data structures. It is shown how the edge computations in these two algorithms can be restructured into the form of a single, shared hardware pipeline. Data from a simulation of this processor suggests that, relative to the specific software functions it is intended to replace, the scanline processor can reduce computation time significantly. In particular, simulations of one possible implementation for this processor yield speedups of three orders of magnitude for Manhattan mask data, degrading gracefully to speedups of two orders of magnitude for highly oblique mask data.