Erik C. Carlson, Rob A. Rutenbar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number5
StatePublished - Sep 1986

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'SCANLINE DATA STRUCTURE PROCESSOR FOR VLSI GEOMETRY CHECKING.'. Together they form a unique fingerprint.

Cite this