111244-2005: DRC & LVSBasic Geometry ProcessingBasic Geometry Processingand LVSand LVSAndreas KuehlmannCourse 244Fall 20052244-2005: DRC & LVSBasics in Geometry ProcessingBasics in Geometry Processing223244-2005: DRC & LVSLiteratureLiterature• Ulrich Lauther: An O(n log n) algorithm for Boolean MaskOperations, 18th Design Automation Conference, 1981• Thomas Szymanski, Christopher Van Wyk: Space EfficientAlgorithms for VLSI Artwork Analysis, 20th Design AutomationConference, 1983• Thomas Szymanski, Christopher Van Wyk: Goalie: A SpaceEfficient System for VLSI Artwork Analysis, IEEE Design andTest of Computers, June 1985• Kuang-Wei Chiang, Surendra Naharm Chi-Yuan Lo: Time-Efficient VLSI Artwork Analysis Algorithms in GOALIE2, IEEETrans. on CAD, June 19894244-2005: DRC & LVSIntroductionIntroduction• Efficient geometry processing key for multiple layout tasks,including– Design rule checking (DRC)– Circuit extraction• Devices• Parasitics– Layout manipulation for yield and other issues• Key operations:– Boolean mask operations (AND, OR, XOR) for• Auxiliary layers (e.g. gates of MOS transistors)• Secondary mask layers that can be derived (implantation)– Measuring areas and edge lengths of regions– Checking distance of point from regions335244-2005: DRC & LVSHistorical ApproachesHistorical Approaches• Bitmaps– Represent each layer as matrix of individual bits• Bit = 1 ⇔ represents layer is present (land)– Highly efficient for Boolean operations• Implemented as Boolean operations on bits– Multiple problems:• Does not scale for large layouts• Difficult for non-Manhattan geometries• Difficult for measuring tasks– Use of special hardware proposed• Representations of Boolean functions (e.g. BDDs, cube lists)– Similar to bitmap, mask is considered as Karnaugh map– Gives erratic behavior as size of Boolean function representationis unpredictable6244-2005: DRC & LVS“Land”“Sea”AssumptionsAssumptions• Geometries of individual layers are given as polygons– Set of directed edges• Not necessarily Manhattan geometry -> angled edges– Counter-clockwise orientation defines “inside” and “outside” ofregion– Overlaps are permitted and are interpreted as “OR”– “Holes” (also referred to as “sea”-areas versus “land”-areas) aredescribed by overlaps/connecting regions• Example:447244-2005: DRC & LVSAssumptionsAssumptions• Huge number of polygons to be processed– Billions per mask layer– Scales roughly with integration density– Thus “next generation” computers don’t help as they barely catchup with increasing integration density• In-memory processing is hopeless with this data amount• Solution:– Algorithms that exploits given computer architecture• Small amount of fast accessible random access memory (RAM)• Large amount of slower sequentially accessible memory (harddisk, tape)8244-2005: DRC & LVSFlow of ComputationFlow of ComputationDiskDiskRAMCPUDiskRAMCPURAMCPU…• Sequential processing from disk to disk– Virtual memory management can mimic same behavior559244-2005: DRC & LVSBasic Basic Scanline Scanline AlgorithmAlgorithm• Given:– Geometry information of set of layers in terms of edges• ((xleft,yleft),(xright,yright))• xleft < xright, omit vertical edges as they can be inferred duringprocessing• Edge attribute indicated region (TOP, BOTTOM)– Stored in “edge file” in canonical order, i.e.,• First criteria: non-decreasing xleft• Second criteria: non-decreasing yleft• Third criteria: non-decreasing slope• Processing– Sweep vertical “scanline” from left to right over layout stopping atpositions xcurr– Read edges from input file and insert into scanline for processing– Drop edges from scanline as soon as xright < xcurr10244-2005: DRC & LVSSimple Example for OR of Two MasksSimple Example for OR of Two MasksPolygons: Edge file:1234Scanline Stops:Read 1&2 Read 3&4 Dump 1&2 Dump 3&46611244-2005: DRC & LVSSimple Example for OR of Two MasksSimple Example for OR of Two MasksOutput Processing:Read 1&2 Read 3&4Dump 1&2Write 1’&2’Dump 3&4Write 3’&4’Chop edges 3 and 4because part fully inside region12244-2005: DRC & LVSComplexity of In-Core MemoryComplexity of In-Core Memory• Assumption that chip density and thus edge density is equallydistributes– Assume processing area of size X x Y requires max N edges to bestored simultaneously on scanline– Doubling area to 2X x Y still required max N edges to be storedsimultaneously on scanline– Doubling area again to 2X x 2Y requires max 2N edges to bestored simultaneously on scanline( )O N• Hence: in-core memory complexity:N 2NN7713244-2005: DRC & LVSOutput Region ClassificationOutput Region Classification• Overlapping areas need to be identified• Simple counting algorithm at each scanline stop using onecounter per layer– Set countlayer1 = countlayer2 = 0– Start from -∞ and enumerate edges of layers along scanline• Crossing bottom edge of layer1 : countlayer1++• Crossing top edge of layer1 : countlayer1--• Crossing bottom edge of layer2 : countlayer2++• Crossing top edge of layer2 : countlayer2--– For operation op area is part of layer1 op layer2 if BLACK = 1• BLACK = (countlayer1 > 0) op (countlayer2 > 0)• op ∈ {AND, OR, XOR, XNOR, NOT)• Whenever BLACK changes value, we cross true output edge14244-2005: DRC & LVSLautherLauther’’s Scanline s Scanline AlgorithmAlgorithmAlgorithm SCANLINE { // QUEUE = sorted stream from edge files xcurr=xleft(MIN(QUEUE)); OLDSCANLINE = ∅ do { NEWSCANLINE = ∅ while (xleft (MIN(QUEUE)) == xcurr) // fill new scanline NEWSCANLINE = NEWSCANLINE ∪ MIN(QUEUE) REMOVE MIN(QUEUE) } OLDSCANLINE = MERGE(OLDSCANLINE, NEWSCANLINE) // see next OUTPUT all true edges with xright=xcurr DELETE from OLDSCANLINE all edges ending at xcurr xcurr = ∞ forall edge ∈ OLDSCANLINE { // find next position xcurr=MIN(xright(edge),xleft(MIN(QUEUE)) } } until (xcurr = ∞)}8815244-2005: DRC & LVSMerge OperatorMerge Operator• Merges edges from OLDSCANLINE and NEWSCANLINE intoOLDSCANLINE– For each adjacent pair of edges, if one of them is fromNEWSCANLINE then check for intersection• If intersection occurs, edges are split– Left parts remains in OLDSCANLINE– Right parts are added back to QUEUE– Same check and split is performed for implicitly given verticaledges• Back to example:34Edges 3 & 4 are splitat given