|
|
Magic Mailing List |
|
From: Jeff Solomon (jsolomon AT vlsi DOT stanford.edu) Date: Tue Apr 09 2002 - 18:59:00 EDT
Andrew P. Lentvorski writes:
> If you really meant your statement about viewing designs of
> arbitrary size (up to max disk space), there is *NO* current vlsi
> editor which will meet your needs.
>
> What you really want is some form of viewer which converts stream
> formats into a fully-packed RTree which is then packed onto a hard
> drive or similar mass-storage device. This is the realm of database
> design rather than VLSI tools design. Antonin Guttman's "R-Trees: A
> Dynamic Index Structure for Spatial Searching" (ACM 1984) is a good
> starting point.
>
> If what you want is a more compact representation to fit bigger
> designs into DRAM, that's a different story entirely. However,
> corner stitching is so fundamental to Magic that changing it to
> something like a quad-tree, a k-d tree, or an R-Tree requires
> *major* surgery.
>
> Let me assure you, however, that "dumb, simple and straightforward"
> structures do not have sufficient performance. The difference
> between O(n^2) (most dumb algorithms) and O(n log n) (the provably
> optimal, but complicated algorithms) for n=10,000 is significant
> even on a 1GHz computer with 1GB of RAM.
>
> You will have to take a dive into some heavy-duty computational
> geometry if you hope to have anything approaching reasonable redraw
> performance for 100,000+ shapes (a relatively small design by
> today's standards)
Andrew,
Let me explain to you a little bit better where I'm coming from. The
problem with layout redraw (and EDA visualization) is something that's
been bothering me for a while. I started some work on it a few years
ago and have managed to make some progress:
http://www-vlsi.stanford.edu/~jsolomon/chipmap/
To implement my viewer, I used magic because it was the only existing
viewer with source code available. I claim that my viewer can
interactively navigate through designs of arbitrary size. This is
mostly true. But the startup time is non-zero. And you'll have to wait
an arbitrarily long time for a top level view to become fully computed
for arbitrarily large designs. But for all the designs I have, and all
the designs I know about, the initial computation times aren't
terrible.
I guess I believe that my algorithm is the fastest way to draw (and
redraw) every element in a VLSI database on the screen.
I brought up the points in my previous posts to share with other magic
users my experiences with reading in massive databases. I'm betting
I'm one of the only people trying to do this with magic. If people who
want to use magic, want to use it with very large databases, they
might want to know how poorly it performs in overall memory footprint
compared to commercial editors/viewers. I suspect that these
commercial editors/viewers are using just the type of database
representation that you talk about above.
Jeff
|
|
|
|