Re: EGG 1.0

Fellow Avians:

  I've just returned to the net after some serious router down time.
Here's a little something to prompt discussions on the issue of how to
represent mutuals. You'll recall that there are two proposals before
the forum: the EGG uses a "sparse" representation; the other proposal
from Cadence is to use a "banded matrix" approach. One issue that has
been raised is how compact the two notations are.

  Both approaches assume some numbering of the pins from 1 to N.
Recall that the "banded" approach assumes that if you have two pins,
numbered I and J, then there is no coupling if the difference of the
two indices is greater than the bandwidth B. So, for each pin from
1 to N (let's take the I'th) you just have B + 1 entries: I's self
term, the mutual from I to I+1, I to I+2, ..., I to I+B. There's no
need to list the indices of the pins in the table of mutual values.

  In the sparse approach, you explicitly indicate the indices of
the two coupled pins, and then give the value of the mutual. If
there's a coupling from pin 10 to pin 78, you write

        10 78 1.98237e-7

or something similar. Clearly, the need to write the indices is
the source of overhead of this method. It's also a source of clarity
for the human reader.

  In what follows, I've provided a little analysis of the storage
requirements in the two approaches for a specific case: that of a big
PGA. The results of the comparison may prove surprising.

--Eric Bracken <bracken@performance.com>

Chris Reid of Cadence wrote in response to EGG 1.0:

>> As for representing mutuals, we are using banded-symmetric RLC
>> matricies. That is the form most 3-D field solvers deliver the result,
>> and it is an easy format to deal with in software. Eric's suggested
>> format is up to the task, but it is somewhat more verbose than
>> required, and requires more processing by the software.

I guess that the "verbosity" you're referring to is the need to include
the indices of the coupled pins before I give the values of the mutuals?
I would say this is the price of the increased generality; the couplings
don't need to be "banded" for this description to work.

As to how verbose it really is, I'm not so sure. There are some
inefficiencies in the banded matrix approach. Take the Intel
Overdrive processor for the Pentium. It's a 273-pin PGA, with pins
laid out in 21 rows with up to 21 pins each. Here's a simplified view
of how the pins are distributed:

          * * * * * * * * * * * * *

          * * * * * * * * * * * * *

          * * * * * * * * * * * * *

          * * * * * * * *

          * * * * * * * *

          * * * * * * * *

          * * * * * * * * * * * * *

          * * * * * * * * * * * * *

          * * * * * * * * * * * * *

Now think about it--if I number the pins in the first row 1, 2, 3,
..., 21, those in the second row with 22, 23, ..., 42 and so forth (of
course the numbering gets screwed up when you get to the "hole" in the
middle, but you get the drift), then the bandwidth of the matrix is
22. That is to say, if you take (for example) pin 23 (the 2nd pin in
row 2), then it's coupled to the pins above (pins 1, 2, 3) the pins
beside (22, 24), and the pins below (pins 43, 44, 45).

Although there are only 8 nearest neighbors, the bandwidth is 22.
Therefore, the banded symmetric matrix representation will have 273
rows X 23 entries (22 mutuals + 1 self term), or

                6279

entries total. Remember that in the banded representation,
zero-valued entries that lie within the "band" still have to be
listed explicitly.

Each of these entries is a triple (R,L,C) of floating point numbers.
If we can assume 10 characters per floating point number, that's 30
characters per banded matrix entry, or

                188,370 <- Banded

characters total, not counting spaces and returns.

On the other hand, if I employ the "sparse" representation described
in the EGG, then the 273 pins have 8 neighbors + 1 self term, or 9
entries per pin, for a total of 273 x 9 = 2457 entries. (Actually,
some pins obviously have fewer than 8 neighbors, which would be
exploited to further reduce the number of entries.) Each entry
consists of 3 floating point numbers (10 chars each) and 2 integer
indices (3 characters apiece), or 36 characters per entry. The total
file size is therefore 2457 x 36, or

                88,452 <- Sparse

characters total. This is just under half the size of the banded
representation.

Please note that I'm assuming BOTH approaches make use of symmetry,
which is only commonsense.

To be fair to the banded approach, it is possible to look at more
clever numbering schemes to reduce the bandwidth. But this tends to
add more work for the people who are trying to build the models (which
they may be unwilling to expend) because those schemes are far from
intuitive.
Received on Thu Jan 27 13:22:17 1994