Layout rule checking is traditionally done through sequences of region-operations, and a few experimental systems use pixel-based processing. This dissertation examines these approaches in detail, and then proposes corner-based checking as an efficient and flexible alternative. In corner-based checking contextual rules, specifying conditions at corners matching patterns, are applied to the design. A rule compiler is used to convert the user-readable rule description to an efficient, indexed, internal form prior to checking. Hierarchical and incremental check algorithms that eliminate redundant checking are also developed. These algorithms greatly enhance the effectiveness of layout rule checking. Measurements from several systems implementing corner-based checking and the hierarchical and incremental algorithms demonstrate their viability and effectiveness.
Corner-based checking has several advantages. First, it checks all rules in a single pass over the data. This avoids the I/O bottleneck that is common in the multi-pass region-operation systems. The rule-based nature of corner-based checking provides inherent flexibility: variants of design rules that would require the coding of new operations in region-operation systems can often be accommodated by modifying the rule specification. Corner-based rules also permit directional context, which is notoriously difficult to establish in region-operation systems. Finally corner-based systems associate violations with points in a design rather than edges or regions. The consequent simplicity of piecewise processing facilitates hierarchical and incremental checking.