Browse Prior Art Database

Improved Multiply and Add Vector Function

IP.com Disclosure Number: IPCOM000105567D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 94K

Publishing Venue

IBM

Related People

Moore, BB: AUTHOR

Abstract

Using the multiply and add function to be described, the rate at which inner loop vector processing takes place is improved.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Improved Multiply and Add Vector Function

      Using the multiply and add function to be described, the rate
at which inner loop vector processing takes place is improved.

      Engineering and scientific programs sometimes process sparse
matrices that are too large to fit into main storage.  Thus, parts of
the matrices are read from DASD and processed, and the results are
written to DASD so that the cycle may be repeated.  Columns of a
matrix which are in main storage are said to be active.  Columns
which must be read from DASD before they can be processed are
inactive.  Column substrings are blocked together when stored on
DASD.  When a column not already in main storage is needed, column
blocks are read from DASD; the result is that new columns become
active.  Similarly, when a newly-created or modified block of columns
is no longer needed, the block is written to DASD; the result is that
several columns become inactive.

      The following is a technique for multiplying a sparse matrix by
a full matrix:  E*B=D.  Here, E is a sparse matrix, B is a full
matrix, and D is the resulting full matrix.  First, main storage
buffers are used to hold as many active columns of B and D as is
possible.  Then, successive column strings of E are used to compute a
contribution to the final values on the active columns of D.  When
the entire E matrix has been processed, the active columns of D are
written to DASD and a new set of columns of B are read from DASD.
The cycle is repeated until all columns of D have been written to
DASD.

      An example of a general step in matrix multiplication is given
in Fig. 1 which shows a string of the E matrix and S active columns
of the B and D matrices.  The E string contains the elements of
column C starting at row R and ending at row R+L-1, where L is the
length of the E string.  F is the row dimension of B and M is the row
dimension of D.  Formulas for calculating the contributions of the E
string to rows R through R+L-1 of the active columns K = G, G+1,...,
G+S-1 of D are:

D(R,K)        =     D(R,K)         +    E(R,C)*B(C,K)
D(R+1,K)      =     D(R+1,K)       +  E(R+1,C)*B(C,K)
  ....            ....
D(R+L-1,K)    =     D(R+S-1,K)     +  E(R+S-1,C)*B(C,K)

      The formulas show that a code for calculating the values for
column K of D can be designed to use stride 1 accesses to main
storage.  When B(C,K) is used as a scalar constant to be multiplied
by each element of column C of E, then stride 1 loads of the E string
are used.  The accesses required to add the products to the elements
of column K of D and to store the results back into that...