Statistical analysis is a fundamental method in analysis, design, and optimization of large systems with uncertainties. It is being applied in drug development, analyzing financial markets, search for new oil fields, and many more areas. As the silicon process technology scales to its limits, uncertainty plays an increasing role and has made its way into tools such as yield analysis, statistical time analysis, etc. In this educational panel, we will start with a short tutorial on Monte Carlo methods including their use in EDA. Three experts from distinct application fields will then follow and discuss their experience in using Monte Carlo methods for solving large-scale problems in their domain. It may come as a surprise to some attendees of DAC to learn how much commonality there is between methods used in EDA and other field that seem far-fetched.

This paper describes JIGSAW, the massively parallel mask checking system that has evolved from our earlier feasibility study on large-scale, fine-grain parallelism in simple mask checking tasks [1]. Unlike previous systems, JIGSAW parallelizes all phases of the checking process. We describe new techniques to handle all-angle geometry, the first massively parallel mask flattening and multi-layer netlist extraction algorithms, and measurements made comparing JIGSAW, running on a Connection Machine, against industry-standard tools. End-to-end speedups, (i.e., from CIF to errors) range from 19 to 58 over DRACULA, with larger masks producing larger speedups.

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.