Browse Prior Art Database

Minimizing the Computations Required to Fill a Matrix Describing Relationships Between Members of a Rectangular Array

IP.com Disclosure Number: IPCOM000045638D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 57K

Publishing Venue

IBM

Related People

Weeks, WT: AUTHOR [+2]

Abstract

Faster computation is permitted of LSI package electrical parameters by utilizing inherent symmetry characteristics to eliminate redundant calculations.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Minimizing the Computations Required to Fill a Matrix Describing Relationships Between Members of a Rectangular Array

Faster computation is permitted of LSI package electrical parameters by utilizing inherent symmetry characteristics to eliminate redundant calculations.

Often, in the design of LSI packages it is necessary to calculate the effect of rectangular ground or power planes on wiring capacitance or inductance. To do so, it is necessary to calculate the surface charge or current density on the plane. The usual procedure is to divide the plane into rectangular cells and assume the charge or current density is constant over each cell but varying in value from one cell to the next. The rectangular plane is divided into M divisions in the vertical dimension and N divisions in the horizontal dimension.

Existing computer programs compute MN(MN+1)/2 integrals, P.(ij,) representing all possible interactions between the MN cells. However, because of the symmetry of a rectangular plane, many of the integrals have the same value. The following systematic procedure determines, before evaluation, which integrals will have the same value, thus reducing substantially the number of integrals that need be evaluated.

Of concern here are two symmetry operations, V and H, which map a rectangle onto itself. V - Reflection through a vertical axis of symmetry (same as rotation by 180 degrees about that axis). H - Reflection Through a horizontal axis of symmetry (same as rotation by 180 degrees about that axis). One implements the two symmetry operations by means of an array called the KEY matrix. The KEY matrix is an M by N matrix of integers stored columnwise. It is initialized as follows.

The V symmetry operation is implemented by replacing each column of KEY by its mirror image through a vetical axis through the center of the matrix. The H symmetry operation is implemented by replacing each row by its mirror image through a horizontal axis through the center of the matrix. For example, consider the 3 by 3 cell subdivisions shown in Figs. 1a through 2b. One has

Thus, KEY contains a permutation of the cell numbers which describes the transformation.

The P matrix, which is always symmetric, is stored in the usual format for symmetric matrices, that is, upper triangle stored columnwise. Thus, P(i+j (j- 1)/2) contains P(ij). Since P has MN rows and MN columns, the P matrix contains MN(MN+1)/2 entries.

A LOC matrix also is used which contains the indices in the P array of the distinct elements in the P matrix. The elements of the LOC matrix are in a one to one correspondence with the elements of the P m...