BIRD29.2

IBIS Members:

BIRD29.1 was approved at the June 30, 1995 forum. BIRD29.2 is issued to
add some bandwidth limits to comply with a practical IBISCHK2 implementation.

In one case the limit is already implied by construction and has already
been implemented in IBISCHK2. In the other case, the limit is set to
avoid the ambiguity associated with allowing the same entry to be specified
twice (and possibly differently).

The BIRD29.2 changes are designated by four "|**" lines.

Bob Ross,
Interconnectix, Inc.

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

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

BIRD ID#: 29.2
ISSUE TITLE: Banded_matrix Extension
REQUESTOR: Bob Ross, Interconnectix, Inc.
DATE SUBMITTED: 26 May 1995
DATE REVISED: 5 June 1995
DATE ACCEPTED BY IBIS OPEN FORUM: BIRD29.1: 30 June 1995

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

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

STATEMENT OF THE ISSUE:

In the Package Model description in IBIS Version 2.1, the Banded_matrix
format needs to be extended to remove a technical limitation.

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

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. BIRD29.2
changes are designate by "|**" lines to add upper bound bandwidth limits.

| 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 Text with Changes Shown: *********************

| 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 x M, 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 is used to specify the coupling effects up to B pins
|* on either side. Two variations are supported. One allows for the coupling
|* to circle back on itself. This is technically a simple form of a bordered
|* block diagonal matrix. However, its data can be completely specified in
|* in terms of a Banded_matrix for an N x M matrix consisting of N rows
|* and M = N + B columns. The second variation is just in terms of an N x N
|* matrix where no circle back coupling needs to be specified.
|*
| 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.
|
|* For case where coupling can circle back on itself, consider a matrix of
|* N pins organized into N rows 1 ... N and M columms 1 ... N, 1 ... B.
| 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 K
|* the entries [K,K] through [K,K+B] are given when K + B is less than or
|* equal to the size of the matrix N. When K + B exceeds N, the entries in the
|* last columns 1 ... B specify the coupling to the first rows. For row K, the
|* entries [K,K] ... [K,N] [K,1] ... [K,R] are given where R =
|** mod(K + B - 1, N) + 1. All rows will contain B + 1 entries. To avoid
|** redundant entries, the bandwidth is limited to B <= int((N - 1) / 2).
|*
|* For the case where coupling does not circle back on itself, the process is
|* modified. Only N columns need to be considered. When K + B finally exceeds
|* the size of the matrix N, the number of entries in each row starts to
|** decrease; the last row (row N) has only 1 entry. This construction
|** constrains the bandwidth to B < N.
|
| 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, please note 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 columns 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"

BIRD29.1 provides another way looking at the formating. The "41" entry can
now be viewed as an upper-triangle entry of the original matrix augmented
by repeating columns 1 ... B. Using symmetry, this format gives all of
the information needed to describe all coupling by the B adjacent pins.

Commentors on BIRD29 discussed nomenclature (banded, bandwidth, bordered block
diagonal matrix) and proposed other terms. One concern was whether to retain
the existing definition and add another term (such as Augmented_matrix) to
handle the wrap around situation. The revised data entry format can still be
referred to as banded when the first N columns are augmented by repeating
existing columns 1 ... B.

For compatibility reasons, support of the existing Banded_matrix format was
desireable. The proposed new format was only a slight variation on the
existing format, so it did not seem appropriate to introduce new nomenclature
for the change. The solution proposed in BIRD29.1 is to accept simutaneously
both format options. The intent is allow the technically robust functionality
within the existing nomenclature, and to allow the technically limited
descriptions be supported where wrap around coupling is of no concern. This
works because the terms missing in the existing format are zero in the more
robust format. The old format should be phased out rather than endorsed by
separate notation which must be supported indefinitely because it would allow
technically incomplete package model libraries.

This is a compromise position between those who would like the original
format definition deleted and those who would like to see both formats
supported using different terminology. The parser definition will be
overloaded, but for this situation, this is not a significant complication.

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

BIRD29.2 is issued to explicitly put in bandwidth limits. This is
in response to an IBISCHK2 question raised by Ron Neville regarding how
to treat redundant Banded_matrix entries when the entries are different.

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

ANY OTHER BACKGROUND INFORMATION
Received on Wed Jul 5 13:32:17 1995