Connectivity Checker Dealer
August 19, 1987


Connectivity  Checker  
for  VLSI  Layout


Bruce Wagar
Department of Electrical Engineering and Computer Science
University of Michigan

Personal Data

· Third year PhD student in computer science at the University of Michigan
· Thesis area is the design and analysis of communication-intensive algorithms for hypercube multiprocessors.
· Expected date of graduation:  May 1989

ChipNDale

· Graphical editor for VLSI designs
· Handles both schematic (logical) and layout (physical) descriptions
schematics:  gates, blocks, ...
layout:  rectangles (of various layers), contacts, ...
· Designs are built hierarchically (i.e., larger objects are composed of instantiations of smaller objects)
· Layout corresponding to the schematic can be obtained through a package called PWCore

Extractor

· Produces a structural description of a ChipNDale object
interprets all ot the bits and pieces that make up the object as a set of wires which describe the corresponding circuit, using 
clues such as proximity and names to base its decisions on
separates these wires into two groups:
* Public (those which can be connected to from the outside world)  and
* Internal (those contained within the object)
· Works on both schematics and layout
· Works hierarchically, extracting smaller objects before larger ones built up from them

Example

The Problem

· In order to allow for more flexible layout designs, the extractor permits the same wire to be disconnected at one level of 
design, with the assumption that the discrepancy will be corrected at a higher level.
· Unfortunately, nothing in the system ever verifies that this takes place!
· This problem wasn't discovered until some faulty designs were actually fabricated:
* RAM of EU2 chips with disconnected Grounds
* early IFU chips with disconnected Clock lines

Solution

· The problem essentially breaks down to the UNION-FIND Problem.
* Enumerate all the pieces that comprise the wire's layout
* Union them into their connected subsets 
* Make sure you end up with only one such subset

My Approach

· Given my limited knowledge of Cedar and the DATools, I decided to follow the Section's motto "Premature Optimization Kills",  and
* start out simple with something that worked,
* see how it behaved on real-life designs, and
* refine as necessary
· Like most of the other DATools, the final version took specific advantage of the hierarchical structure of layout designs by: 
* checking the connectivity of smaller cells' wires
* report immediately any internal disconnections (i.e., ones that can't be fixed from higher up)
* propagate any public wire disconnectivity information upward for use by larger cells

 
Example
 
Results

· AnalogTest (522 transistors)
> 222 seconds to extract 
> 35 seconds to check connectivity
· RAM of EU2 (3152 transistors)
> 480 seconds to extract 
> 330 seconds to find disconnections
· BIC (10613 transistors)
> 1498 seconds to extract 
> 316 seconds to check connectivity
· IFU (61614 transistors)
> 8958 seconds to extract 
> 10698 seconds to check connectivity
· BPC

Impressions of Cedar Environment

· Nice Features
* Celtics
* MakeDo -rgom
* GetFromRelease
* Breakpoint-Interpreter-Debugger

· Turkeys
* Very difficult for new users 
> rollback
> node-structured editor with looks, format, ...
> local versus server versions of files
* Garbage Collection
* Opaque Types

Thanks

· Lissy Bland
· Willie-Sue Orr
· Lorna Fear
· Jack Kent
· Louis Monier and Bertrand Serlet
· All the other lab members who helped me with their time and made my stay here that much more enjoyable (Christian LeCocq, Peter 
Kessler, Russ Atkinson, Bob Hagmann,...)