EFFICIENT DESIGN RULE CHECKING USING A SCANLINE ALGORITHM

作     者：THOMAS, PR BROWN, AD 

作者机构：Department of Electronics and Computer Science University of Southampton Southampton UK 

出 版 物：《IEE PROCEEDINGS-I COMMUNICATIONS SPEECH AND VISION》 (IEE Proc Part I)

年 卷 期：1987年第134卷第2期

页      面：63-69页

核心收录：

主　　题：Electronic engineering computing Lithography (semiconductor technology) integrated circuits VLSI data structures verification tools IC layout design scanline algorithm circuit layout CAD data structure design rule checking Computer-aided circuit analysis and design mask data CAD error detection integrated circuit technology computer aided design Semiconductor integrated circuits 

摘      要：Design rule checking of integrated circuits requires many operations which manipulate and test geometric figures. Closer examination often reveals that some effort is duplicated by different operations on the same mask data. The paper describes a scanline based design rule checker which structures the mask data to allow common administrative operations to be separated from the main checking process. This structuring is made possible by a novel data structure, the ‘scanline history’, and it is demonstrated experimentally that, after an initial preprocessing phase, the workspace and execution times required to perform design rule checking are 0(N0.5) and 0(N). The results indicate that rationalised scanline administration yields significant savings in overall execution time.