Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!rpi!iear.arts.rpi.edu!kyriazis
From: kyriazis@iear.arts.rpi.edu (George Kyriazis)
Newsgroups: comp.theory.cell-automata
Subject: Re: efficiency and philosophy of CA computer simulation
Message-ID: <&'+#D#|@rpi.edu>
Date: 2 Mar 90 23:38:33 GMT
References: <K{+#+Y+@rpi.edu>
Organization: Rensselaer Polytechnic Institute, Troy NY
Lines: 90

In article <K{+#+Y+@rpi.edu> hiebeler@cs.rpi.edu (Dave Hiebeler) writes:
>
>We just do the following with CA:
> 1. "assume" the universe (hence the system under study) is discrete
> 2. write a CA rule which captures the essentials of the laws of
>    physics, in particular the ones that most strongly affect what
>    we're studying, and implement the CA rule exactly on a computer
>    (no round-off, etc)
>
Hmm..  I don't know if that will work nicely for circuit simulators.
Since the universe is not discrete (well, physicists can argue that it
is, so it's better to say that the universe is not as 'lumpy' as
today's CA machines assume), I think that the results will
probably be better if the CA rules take into account the discretness
of the CA world.  Doing that of course will increase the computation
per step.


>I'm not getting into the virtual reality topic here;
>I'm saying that at some point we'll be able to do things like simulate
>a cubic centimeter of air at the molecular level, in something not far
>from real-time, using CA technology!
>
This is interesting.  What is more interesting is the following:
There is a concept called the time quantum, which is VERY small
(order of 10^-40 secs?).  You are talking about simulating nature in
close to real-time.  Definetely your time step will be mach larger than
that (I am dreaming of 500 picosecs or so), so some kind of interpolation
(spatial and/or temporal) has to be done.  ODE solving does the same
thing:  It's repetitive and interpolates on the time axis.  So, the
question that comes to mind is:  Is there any fundamental difference
between DE solving and CA?  I don't think there is too much.
Finite element Analysis texts start from fixed grid techniques
(hmm..  it reminds me of the CA grid) and go on with localized grid
refinement and a huge list of other stuff I don't want to think about.

But FEM is for Mech. Engineers!  They deal will stresses and they need
refinement.  Circuit simulation uses experimental results 
(capacitance/unit area, resistance/unit length, etc.)  for simulation
(I am talking about SPICE, etc.).  In VLSI design there is a minimum
feature size that can be used, so NOT refining will work.  


>
>  So a *CA simulation* of a serial computer will approach the speed of a
>*physical implementation* of that computer!  At least, it seems that
>way to me.  
>
Assuming that lots of approximations are made during the simulation,
I agree.


>
>  This really starts to sound like a lot of philosophical hocus-pocus,
>but now that I've already gone that far, I might as well ask the real
>philosophical knockout question: do you think it is feasible that we
>will someday be able to simulate computers, using CA techniques, so
>that they will run *faster* than the physical implementation of the
>machines?  That is, maybe CA hardware will develop so well that it
>will get ahead of manufacturing technology in some areas?
>
If you are willing to stretch your question I think it's already done!
There are some new chips just announced that are called
'Field Programmable Logic Arrays'.  They contain an array PLA's
(Programmable Logic Arrays) that are connected with a programmable
interconnect.  That means that you can program it at run-time.
In other words you can have a bunch of them emulatinga SPARC at one
point in time, then change their mind and reprogram themselves so
they emulate a 68020 equally well, and finally change so they
emulate a small Connection Machine.

Now where does the simulation come into play?  I think it makes the
gap between simulation and implementation VERY small.  What you can
do is design the circuit and instead of simulating it, program it
on an array of FPLA's, see if it works, and then (if necessary) go
back to the drawing board.  Scary isn't it?


>
>-- 
>Dave Hiebeler / Computer Science Dept. / Amos Eaton Bldg. /
>Rensselaer Polytechnic Institute / Troy, NY 12180-3590 USA
>Internet (preferred): hiebeler@turing.cs.rpi.edu   Bitnet: userF3JL@rpitsmts
>"Off we go, into the wilds you ponder..."


----------------------------------------------------------------------
  George Kyriazis                 kyriazis@turing.cs.rpi.edu
				  kyriazis@rdrc.rpi.edu
 				  kyriazis@iear.arts.rpi.edu