Subject: BIRD29 Banded_matrix Correction

From: [email-masked] ( Bob Ross)
Date: Sat, 27 May 95 12:23 PDT

IBIS Members:

In IBIS Version 2.1 under the Package Model description, the text contains
a format restriction on the Banded_matrix description which is technically
incorrect.  BIRD29 suggests text changes to correct the problem.

This issue relates to a correction to Version 2.1 and is also necessary
to be resolved for proper IBISCHK2 functionality since IBISCHK2 checks
for the incorrect restriction.

Bob Ross,
Interconnectix, Inc.

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

*****************************************************************************
                 Buffer Issue Resolution Document  (BIRD)

BIRD ID#:                29
ISSUE TITLE:             Banded_matrix Correction 
REQUESTOR:               Bob Ross, Interconnectix, Inc.
DATE SUBMITTED:          26 May 1995 
DATE REVISED:
DATE ACCEPTED BY IBIS OPEN FORUM:    Pending

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

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

STATEMENT OF THE ISSUE:

In the Package Model description in IBIS Version 2.1, the Banded_matrix 
format needs to be corrected to remove a technically incorrect restriction.

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

STATEMENT OF THE RESOLVED SPECIFICATIONS:

The relevant portion of the original Specification is given along with 
edited remarks or deletion comments are designate by "|*" lines.

| Banded_matrix
|
| A Banded_matrix is one whose entries are guaranteed to be zero if they
| are farther away from the main diagonal than a certain distance, known
| as the "bandwidth."  Let the matrix size be N, and let the bandwidth
| be B.  An entry [I,J] of the matrix is zero if:
|
|        | I - J | > B
|
| where |.| denotes the absolute value.
|
| The bandwidth for a Banded_matrix must be specified using the [Bandwidth]
| keyword:
|
|==============================================================================
|     Keyword:  [Bandwidth]
|    Required:  Yes (for Banded_matrix matrices only)
| Description:  Indicates the bandwidth of the matrix.  The bandwidth field
|               must be a nonnegative integer.  This keyword must occur after
|               the [Resistance Matrix], etc. keywords, and before the matrix
|               data is given.
| Usage Rules:
|------------------------------------------------------------------------------
[Bandwidth]     10
|
|==============================================================================
| Specify the banded matrix one row at a time, starting with row 1 and
| working up to higher rows.  Mark each row with the [Row] keyword, as
| above.  As before, symmetry is exploited: do not provide entries below the
| main diagonal.
|
| The first row only needs to specify the entries [1,1] through [1,1+B] since
| any other entries are guaranteed to be zero.  The second row will need to
| specify the entries [2,2] through [2, 2+B], and so on.  In general, for row M
| the entries [M,M] through [M,M+B] are given.
|
| Unlike the Full_matrix, each successive row will typically have the same
| number of entries, except for the last few rows.  When M + B finally exceeds
| the size of the matrix N, then the number of entries in each row starts to
| decrease; the last row (row N) has only 1 entry.
|
| As in the Full_matrix, if all the entries for a particular row do not fit
| into a single 80-character line, the entries can be broken across several
| lines.
|
| It is possible to use a bandwidth of 0 to specify a diagonal matrix (a matrix
| with no coupling terms.)  This is sometimes useful for resistance matrices.
|

|**** Reword the Above 5 Paragraphs with Changes Shown: *********************

| Specify the banded matrix one row at a time, starting with row 1 and
| working up to higher rows.  Mark each row with the [Row] keyword, as
| above.  As before, symmetry is exploited: do not provide entries below the
|* main diagonal except when entering data in the last rows to define the
|* coupling to the first rows.
|
| The first row only needs to specify the entries [1,1] through [1,1+B] since
|* all other entries are guaranteed to be zero.  The second row will need to
|* specify the entries [2,2] through [2,2+B], and so on.  For row M
|* the entries [M,M] through [M,M+B] are given when M+B is less than or
|* equal to the size of the matrix N.
|
|* When M+B exceeds N, the last entries specify the coupling to the first
|* rows, wrapping around and continuing in ascending order.  For row M, the
|* entries [M,M] ... [M,N] [M,1] ...[M,K] are given where K = mod(M+B-1,N)+1. 
|
|* For the Banded_matrix, all rows will contain B+1 entries.
| As in the Full_matrix, if all the entries for a particular row do not fit
| into a single 80-character line, the entries can be broken across several
| lines.
|
| It is possible to use a bandwidth of 0 to specify a diagonal matrix (a matrix
| with no coupling terms.)  This is sometimes useful for resistance matrices.
|
|****************************************************************************
|
| Sparse_matrix
|
| A Sparse_matrix is expected to consist mostly of zero-valued entries, except
| for a few nonzeros.  Unlike the Banded_matrix, there is no restriction on
| where the nonzero entries can occur.  This feature is useful in certain
| situations, such as for Pin Grid Arrays (PGAs.)
|
| As usual, symmetry can be exploited to reduce the amount of data by
| eliminating from the matrix any entries below the main diagonal.
|
| An N x N Sparse_matrix is specified one row at a time, starting with
| row 1 and continuing down to row N.  Each new row is marked with [Row]
| keyword, as in the other matrix formats.
|
| Data for the entries of a row is given in a slightly different format,
| however.  For the entry [I, J] of a row, it is necessary to explicitly
| list the name of pin J before the value of the entry is given.  This
| specification serves to indicate to the parser where the entry is put into
| the matrix.
|
| The proper location is not otherwise obvious because of the lack of
| restrictions on where nonzeros can occur.  Each (Index, Value) pair is
| listed upon a separate line.  An example follows.  Suppose that row 10
| has nonzero entries [10,10], [10,11], [10,15], and [10,25].  The
| following row data would be provided:
|
[Row]   10
| Index         Value
10              5.7e-9
11              1.1e-9
15              1.1e-9
25              1.1e-9
|
| Note that each of the column indices listed for any row must be
| greater than or equal to the row index, because they always come from
| the upper half of the matrix.  When alphanumeric pin names are used,
| special care must be taken to ensure that the ordering defined in the
| [Pin Numbers] section is observed.
|
| Also, note that it is again necessarily the case that the N'th
| row of an N x N matrix has just a single entry (the diagonal entry.)
|
|**** Reword the Above Sentence: *******************************
|
|* With this convention note that it is necessarily the case, for example, 
| that the N'th
|* row of an N x N matrix has just a single entry (the diagonal entry).
|
|****************************************************************
|==============================================================================

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

ANALYSIS PATH/DATA THAT LED TO SPECIFICATION

In order to reduce the size of the symmetrical matricies, there are several
statements describing data entries only ON or ABOVE the main diagonal.
That was the intention of the banded-matrix description.  However the
format prevented entering the coupling between the last pins and the
first pins.

A simple 4-pin example with a bandwidth of 1 illustrates the problem.  The
"data" entries are the two digit subscripts of the matrix entries and are
shown using quote marks "".

Version 2.1 does not allow defining the coupling between pin 4 and 1:

[Inductance Matrix]   Banded_matrix
[Bandwidth]           1
[Row]   1
   "11"  "12"
[Row]   2
   "22"  "23"
[Row]   3
   "33"  "34"
[Row]   4
   "44"     

One possible solution is to augment the Banded_matrix format for the
first rows by the entries that could not be entered in the last rows.
This would preserve the ABOVE the diagonal convention.

[Inductance Matrix]   Banded_matrix
[Bandwidth]           1
[Row]   1
   "11"  "12"  "14"
[Row]   2
   "22"  "23"
[Row]   3
   "33"  "34"
[Row]   4
   "44"     

However, the solution proposed here is to keep the number of colums the same
and to wrap around the entries for the last rows as needed.  Technically
the entries are BELOW the main diagonal.  The "41" entry would really be
entered as "14" in the reduced upper-triangle matrix data structure.

[Inductance Matrix]   Banded_matrix
[Bandwidth]           1
[Row]   1
   "11"  "12"
[Row]   2
   "22"  "23"
[Row]   3
   "33"  "34"
[Row]   4
   "44"  "41"  

This problem does not occur in the Sparse_matrix format.  So the restriction
text has a minor change in that portion of the Specification.

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

ANY OTHER BACKGROUND INFORMATION

---

From: [email-masked] ( Bob Ross)
Date: Mon, 29 May 95 11:06 PDT

Eric:

Thank you very much for your comments that are attached below.  Since you
were the originator of the coupling matrix extension to IBIS, your assessment
of any change is critical.

I interpret your response that you would favor such an "expansion" to IBIS.
I will provide a revision to BIRD29 per your comments.  It would be helpful
to me if you could review some wording changes (and/or provide alternative
text) to correctly deal with the Banded_matrix designation in IBIS.

PROPOSED ADDITIONAL TEXTS DESIGNATED BY "|*" :

| Banded_matrix
|
| A Banded_matrix is one whose entries are guaranteed to be zero if they
| are farther away from the main diagonal than a certain distance, known
| as the "bandwidth."  Let the matrix size be N, and let the bandwidth
| be B.  An entry [I,J] of the matrix is zero if:
|
|        | I - J | > B
|
| where |.| denotes the absolute value.
|*
|* The Banded_matrix format conforms to this definition, except that it also
|* allows for the off-diagonal entries to describe coupling between the first
|* and last pins.  The Banded_matrix format supports a constant-sized band
|* of entries for each row and is not limited to be in strict compliance with
|* the traditional mathematical definition.
|
| The bandwidth for a Banded_matrix must be specified using the [Bandwidth]
| keyword:
|
|==============================================================================

The BIRD29 issue is not one of mathematical purity, but of practical reality.
One of the main applications is for a simple user interface format for 
flat pack package configurations, especially those with high pin counts and
small spacing.  Often pin 1 is centered along one side and next to the
highest numbered pin.  Even flat pack configurations for the standard
logic families have pin 1 centered along one edge.  I think that the 
"Banded_matrix" format is the natural and appropriate format, and it should
be defined to support the actual coupling between adjacent pins.  There
is no value and there is actually harm to wait for Version 3.0 to make
the technical inclusion proposed in BIRD29 because the IBISCHK2 parser would
test and enforce a non-practical restriction while IBISCHK3 would operate
in a different manner.

Bob Ross,
Interconnectix, Inc.

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

> Date: Sun, 28 May 1995 09:20:58 -0400
> From: J Eric Bracken <[email-masked]>
> Status: RO

> I have two comments on the BIRD:

> Comment 1:
> ---------

> This BIRD is more of an expansion in functionality than a "correction."
> I think it's highly useful--especially for PGA's, where the pins are laid
> out in a "circle" that closes back on itself.  Please note, however, that
> the resulting matrix is no longer "banded" in the traditional sense of
> the word, because the pattern of entries will be something like this:

> 	XX      X  <--  this is not present in a "banded" matrix
> 	XXX		
> 	 XXX
> 	  XXX
> 	   XXX
> 	    XXX
> 	     XXX
> 	      XXX
> 	X      XX

>         ^
>        nor is this

> That's why the original spec is the way it is--I thought people would
> use a Sparse Matrix for this type of structure.  Incidentally, this is
> a simple form of a "bordered block diagonal" matrix. 

> Could we add a phrase or two to the spec which clarifies that the New
> and Improved "banded matrix" is a generalization of the concept that's 
> used in most of the world's literature?  This might help to avoid some
> confusion with terminology.

> Comment 2:
> ---------

>   I don't like the rewording of the comment on the last paragraph of
> the Sparse Matrix description.  Particularly, the "for example" seems
> clumsy.  How about:

> ** With this convention, please note that the N'th row of an 
> ** N x N matrix has just a single entry (the diagonal entry.)

> __________________________________________________________________
>      ________   ________   __   ________
>     /\_______\ /\_______\ /\_\ /\_______\ J. Eric Bracken, Ph.D.
>    / / ______// / ____  // / // / ______/ Visiting Lecturer, Dept. of ECE
>   / / /__\   / / /__\/ // / // / /        Carnegie Mellon University
>  / / ____/  / / ___  _// / // / /___      Pittsburgh, PA 15213
> / / /____\ / / / \/ / / / // / /____\     (412) 268-8944 FAX (412) 268-3204
> \/_______/ \/_/  \/_/ \/_/ \/_______/     [email-masked]

>  http://www.ece.cmu.edu/afs/ece/usr/bracken/.home-page.html
> __________________________________________________________________