Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!brutus.cs.uiuc.edu!apple!apple.com!karakots
From: karakots@apple.com (Ken Karakotsios)
Newsgroups: comp.theory.cell-automata
Subject: Re: VLSI CAs (was Re: hiebeler's rap)
Message-ID: <7012@internal.Apple.COM>
Date: 2 Mar 90 19:27:25 GMT
Sender: usenet@Apple.COM
Distribution: inet
Organization: Apple Computer Inc.
Lines: 38
References:<9003020522.AA25938@megalon.acad.com> <37683@iuvax.cs.indiana.edu>

There are several aspects of VLSI design that one uses computers for:  
Logic simulation, timing accurate simulation, layout generation, design 
rule checking, static timing analysis, schematic extraction from a layout 
(for checking to make sure your layout generator did its job), and 
modelling the solid state physics of a single transistor are a few 
examples that come to mind.

Wire world running on a serial computer is many orders of magnitude slower 
than current logic simulators.  Also, the fact that synchronization of 
electorns at gates requires all paths between gates to be the same length 
makes things quite complicated.  However, one company I know of 
(Qucikturn) is using a large cluster of electrically programmable gate 
arrays to actually implement the logic, on the fly, that you want to 
simulate.  This approach sounds about as reasonable as making a special 
electrically programmable wireworld hardware element to do logic 
simulation.  Put a reconfigurable cluster of enough of them together (is 
this a CAM-8?) and you could get one clock cycle of the design you are 
simulating in some small number of clock cycles of the  wireworld 
simulator hardware.  Typical logic simulation of a complex design on a 
serial computer is about a factor of 10^6 slower than the speed of the 
real design.  If you can do better than this with a cheap hardware add-on, 
it could be interesting. 

Perhaps CAs could be applied the problem of generating VLSI layout or 
extracting a schematic from existing layout.  For example, you could use a 
CA which shrinks rectangles down to lines to simplify the topology of a 
VLSI  layout into some "stick" types of patterns.  Perhaps these patterns 
could then be looked up in some "list of possible patterns".

Static timing analysis requires software which can find all possible paths 
which a signal can take through a design.  Maybe "virtual ants" could 
crawl through the netlist and report back to some data structure on what 
all the paths are... 

Ken Karakotsios                 karakots@apple.com
(408) 974-1942                AppleLink: karakots

generic disclaimer... I speak for myself, not Apple...