A Scanline Data Structure Processor for VLSI Geometry Checking

Erik C. Carlson, Rob A. Rutenbar

Research output: Contribution to journalArticlepeer-review


This paper proposes an architecture to support VLSI geometry checking tasks based on scanline algorithms. Rather than recast the entire verification task in hardware, we identify primitives around which geometry checking tools can be built, and examine the feasibility of accelerating two of these critical primitives. We focus on the operations of Boolean combinations of mask layers, and region numbering within a mask layer. Unlike previous proposals for special hardware (e.g., bit map processors), this architecture operates on a more realistic representation of masks: A sorted stream of possibly oblique edges. The architecture can be viewed as directly interpreting the operators that manipulate the relevant scanline data structures. We show 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)
Pages (from-to)780-794
Number of pages15
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number5
StatePublished - Sep 1987
Externally publishedYes

ASJC Scopus subject areas

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


Dive into the research topics of 'A Scanline Data Structure Processor for VLSI Geometry Checking'. Together they form a unique fingerprint.

Cite this