Electrical computers and digital processing systems: memory – Address formation – Generating a particular pattern/sequence of addresses
Reexamination Certificate
1998-10-28
2002-04-16
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Generating a particular pattern/sequence of addresses
C711S200000, C711S209000
Reexamination Certificate
active
06374343
ABSTRACT:
The present invention relates to array indexing in a computer and in particular to a method of and apparatus for sequentially generating a set of addresses, defined over a plurality of indices, for a multi-dimensional array scored in a memory, wherein at least one of the address indices is fixed.
In accessing data stored in a digital memory, it is often desirable or necessary to step through the entries of a multi-dimensional array, holding one or more indices of the address constant whilst doing so. To illustrate this, reference is made to
FIG. 1
which shows a typical example of how a multi-dimensional array A[i,j,k] where i=0 to 1, j=0 to 1, k=0 to 3 may be stored in a computer's memory. The array is logically a sequence of elements each of which is identified with a unique combination of subscripts or indices (i,j,k) but is physically stored in a one dimensional array of locations in the memory. In order to enable hardware to access the one dimensional memory array it is necessary to translate logical addresses composed of the appropriate indices (i,j,k) to location addresses which can directly access the one dimensional array.
It is therefore the case that associated with each set of indices in the multidimensional array there will be a number which, when used as an index to the underlying one dimensional array, will define the corresponding position in the one dimensional array. Thus, in the example shown in
FIG. 1
, element A[1,0,3] will be in decimal location 11 (i.e. 1011 in binary) in the underlying one dimensional array.
In the above example, location
11
is typically obtained from che array indices [1,0,3] as shown in FIG.
2
. The indices [1,0,3] i.e. i,j, are held in respective distinct registers (i,j,k) and are then multiplied by appropriate constants (8, 4 and 1). The results are then added together to form the location number (1011) in binary.
Consider now that one wishes to step through the array A[i,j,k], holding the value of j constant at 1 but going through all legitimate combinations of i and k. This involves accessing the set of array elements:
A[0,1,0], A[0,1,1], A[0,1,2], A[0,1,3],
A[1,1,0], A[1,1,1], A[1,1,2], A[1,1,3]
and the corresponding locations: 4,5,6,7,12,13,14,15
The normal process by which this would be done would be to:
1. reserve three computer registers for i, j, k;
2. initialise them to the values i=0, j=1, k=0;
3. set up a pair of nested loops in a computer program so that
(a) the outer loop increments i through all its allowed values
(b) the inner loop increments k through all its allowed values and
(c) the kernel of the inner loop uses the process shown in
FIG. 2
to compute the location numbers from the indices of each array element.
The disadvantage of this process is that it involves multiplication or shift operations and nested loops, all of which are relatively slow operations to perform using computer hardware.
It is an object of the present invention to overcome or at least mitigate the above mentioned disadvantages of array address generating methods.
According to a first aspect of the present invention there is provided a method of sequentially generating a set of addresses, defined over a plurality of indices. for a multi-dimensional array stored in a memory, wherein at least one of the address indices is fixed at an actual value, the method comprising the steps of:
(a) providing a first binary address having address indices of arbitrary value;
(b) replacing all of the bit values of each fixed index in the first binary address with 1.'s;
(c) incrementing the resulting binary value, wherein any carry values(s) generated propagate(s) across each fixed index;
(d) replacing the bit values of each fixed index in the resulting binary value with the actual values to which each fixed index is set to provide a first address for the set; and
(e) repeating steps (b) to (d), using the preceding result of step (c) as a new first binary address value, until the required address set has been generated.
In an embodiment of the above first aspect of the invention, the method comprises the steps of:
(i) providing an accumulator and storing in the accumulator a binary value composed of a set of binary indices corresponding to the address indices;
(ii) performing a logical OR operation between the binary value stored in the accumulator and a first mask binary value, where the first mask, value is also composed of a set of binary indices with each index, corresponding to each fixed address index, being composed entirely of 1's and the other indices being composed entirely of 0's;
(iii) performing a logical ANT operation between the result of the OR operation in step (ii) and a second mask binary value composed of a set of binary indices, where each index, corresponding to each fixed address index, contains the corresponding binary value of the fixed address index, and the other indices are composed entirely of 1's, wherein the result of the AND operation provides a first address for the set;
(iv) incrementing the result of the OR operation performed in step (ii) and storing the result in the accumulator; and
(v) repeating steps (ii) to (iv) until the required address set has been generated.
The present invention makes it possible, by suitable use of mask bits, to so arrange the inputs to a conventional computer adder that the operations required to step through a multi-dimensional array can be performed by simple addition, ORing and ANDing.
The binary value initially stored in the accumulator may be any arbitrary value although it would normally be initialised to zero.
According to a second aspect of the present invention there is provided a digital computer memory comprising at least one digital data storage device and address generating means arranged to generate addresses according to the method of the above first aspect of the present invention for the purpose of accessing data stored in the or each data storage device.
According to a third aspect of the present invention there is provided apparatus for carrying out the method of the above first aspect of the invention and comprising:
a first register arranged to provide said accumulator;
a second register arranged to store the first mask binary value;
an OR logic unit coupled to said first and second registers for performing the OR operation of step (ii);
a third register coupled to the OR unit and arranged to store the result of said OR operation;
an incrementing unit coupled to said first and third registers and arranged to perform step (iv);
a fourth register arranged to store said second mask value; and
an AND logic unit coupled to said third and fourth registers and arranged to perform the AND operation of step (iii).
REFERENCES:
patent: 4819152 (1989-04-01), Deerfield et al.
patent: 5293596 (1994-03-01), Toyokura et al.
patent: 5586256 (1996-12-01), Thiel et al.
patent: 443 551 (1991-08-01), None
Proceedings of the Asilomar Conference on Signals, Systems and Computers Oct. 30-Nov. 1, 1989 vol. 1 of 2 Oct. 30, 1989 Chen R R. pp. 2-6 Sprinivasan et al. “A Novel addressing scheme for two dimensional data access in digital siganl processors”.*
Proceedings Of The Asilomar Conference On Signals, Systems & Computers, vol. 1 of 2, Oct. 30-Nov. 1, 1989, “A Novel Addressing Scheme For Two Dimensional Data Access In Digital Signal Processors”, Srinivasan et al, pp. 2-6.
Patent Abstract of Japan, Publication No. 03 139718, Jun. 13, 1991, “N-Bit Arithmetic Operation Circuit”.
Cockshott William Paul
McGregor Douglas Robert
Alston & Bird LLP
Thai Tuan V.
University of Strathclyde
LandOfFree
Array indexing with sequential address generator for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Array indexing with sequential address generator for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Array indexing with sequential address generator for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916531