From: Matt Gingell (mjg223@is7.nyu.edu)
Date: Wed May 03 2000 - 20:30:21 MDT
>Ok, I have a question that is leaving me confused. What exactly is the
>role of compression within simulation situations? If I can represent
>(i.e., model) a set of information perfectly with a compressed form of
>that information, then haven't I modeled something larger with something
>smaller?
>
>For example: I can model 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 with 2 *
>5. I've compressed a ten digit, multiple addition operation with a
>single multiplication of two digits operation.
>
>This would then seem to scale up for many things, indeed, even to the
>size of the universe. Is there something I'm missing here?
>
>-Dana
This is a really interesting question.
On the one hand, you'd think there might be situations where a system
emulating its own substrate could actually yield a speed increase. For
instance, take a chip running a instruction-level simulation of
itself. To elaborate on your example, let's say multiplication on this
chip is very inefficient: it takes longer to multiple 5 by 6 than it
does to do 5 adds. If I simulate multiplication by doing additions,
then I'd get a speed increase.
But this is a one time optimization: If the emulator runs another
layer of simulation, I won't get the same increase. And I only get a
speed up on programs using the multiplication instruction - so I don't
have a faster chip, that is a chip that runs every program faster than
the substrate, I only have a chip than runs a subset of programs
faster. You always have to bottom out somewhere.
There's an analogy here to data compression: There exists no algorithm
which can be guaranteed to shave a bit off any arbitrary bit string. If
there were, applying the algorithm enough times would compress
anything down to zero. All you can do is map frequently occurring
patterns down to short encodings at the expense of making less
frequent patterns more expensive to express.
-matt
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:28:24 MST