Browse Prior Art Database

Instructions for Computing Dynamic Matrix Addresses

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

Publishing Venue

IBM

Related People

Berstis, V: AUTHOR [+2]

Abstract

In computer systems, matrixes of data are stored linearly in main storage. To address a particular element of a matrix, a computation involving a multiplication and addition operation for each subscript is required. Some computer systems have a CAI (Compute Array Index) instruction which can be used for such computations. Several limitations of the CAI instruction prevent its use in languages, such as BASIC, APL, and PL/I, where the matrixes are variable in size and dimension, where each subscript value must be checked to be within a range of values, and where the lower value of a subscript is variable. The new instruction described here overcomes these limitations and provides more optimal code for computing matrix addresses based on subscript values.

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 52% of the total text.

Page 1 of 4

Instructions for Computing Dynamic Matrix Addresses

In computer systems, matrixes of data are stored linearly in main storage. To address a particular element of a matrix, a computation involving a multiplication and addition operation for each subscript is required. Some computer systems have a CAI (Compute Array Index) instruction which can be used for such computations. Several limitations of the CAI instruction prevent its use in languages, such as BASIC, APL, and PL/I, where the matrixes are variable in size and dimension, where each subscript value must be checked to be within a range of values, and where the lower value of a subscript is variable. The new instruction described here overcomes these limitations and provides more optimal code for computing matrix addresses based on subscript values.

The existing CAI instruction provides the following computation on four operands: I=J+(S-1)*D

where:

Operand Number Description

1 I = Resulting index

2 J = Previous index

3 S = Subscript value

4 D = Displacement between values of

above subscript

Using this CAI instruction, one can compute the index into a matrix as follows. Let the matrix have N dimensions, and for each script, the lower bound is 1 and the upper bound is U. Thus, the number of elements in the entire matrix is: the product: U(1)* U(2)* U(3)* ...*U(N). Let the subscripts be S(i).

To compute the index into the linear storage array for a given matrix element S, one would perform the following instructions: CAI X,S(1),S(2),U(1)

CAI X,X,S(3),U(1)*U(2)

CAI X,X,S(4),U(1)*U(2) *U(3) ...

CAI X,X,S(N),U(1)*U(2)*U(3)*...*U(N-1)

This results in X having an index value into the storage array To obtain the byte address, one would multiply the result by the number of bytes of storage occupied by each element, and subtract one to get the offset.

The above computation is adequate if the matrix is of fixed size and dimensionality. However, the following problems arise when the matrix does not meet these restrictions, as is the case in languages such as BASIC, APL, and PL/I. If the upper bounds U are variable at run time, the series of products for the fourth operands of the CAI instructions must be recomputed each time the array size changes in any dimension Since these are products of several upper bounds, a larger amount of temporary storage is required when accumulating the products and the slower form of multiply is required because of the possibility of

1

Page 2 of 4

larger products The lower bound is a constant 1. The above languages lower subscript bounds differ from one, and thus the CAI is not usable here The CAI instruction does not check the bounds of the individual subscripts as required in the above languages. Both upper and lower bounds must be variable at run time and checked for each subscript The new instruction eliminates all of the above restrictions

To overcome these limitations, the following excerpt of a typical expansion is required to compute a subscript for a...