JPH0750448B2 - Array subscript converter - Google Patents

Description

TECHNICAL FIELD The present invention relates to an array subscript conversion device, and more particularly to an array subscript conversion device used for allocating a multidimensional array to a storage space having a one-dimensional address structure in an information processing system.

2. Description of the Related Art Many storage areas of an information processing system including a main memory have a one-dimensional address structure which is addressed by a continuous integer value. In the storage space having such a one-dimensional address structure, a multidimensional array whose elements are specified by a plurality of subscripts cannot be allocated as it is.

Therefore, conventionally, the one-dimensional array A is stored in the storage space.
(T) is allocated and the multidimensional array M (i1, i2, ..., i
A pseudo multidimensional array is realized by using an array subscript conversion device that inputs the subscripts i1, i2, ..., In of n) and outputs t. Such an array subscript conversion device may be realized as dedicated hardware or may be realized by hardware and software. The conventional configuration realized as hardware is the fifth one.
There is something like the figure. In the figure, n multipliers 81 to
8n and an adder 9 that obtains the added value of these multiplication outputs. The coefficient k1, is added to each subscript i1, i2, ..., In of the multidimensional array.
The output t is obtained by multiplying each of k2, ..., Kn and adding all these products.

Here, k1, k2, ..., Kn are constants depending on the range of possible values of the subscripts, and in general, ia (a = 1,2, ...
, N) takes an integer value of 0 or more and Na or less, k _n = 1,
k _n-1 = N _n + 1, k _n-2 = (N _n-1 +1) ・ (N _n +1), ..., Is.

In the above-mentioned conventional array subscript conversion apparatus, since a constant that depends on the range of values that the subscript can take is used as a coefficient in the conversion, a multidimensional array whose elements are specified by n subscripts (hereinafter , N-dimensional array) to a one-dimensional array, there is a drawback in that the maximum value of at least n-1 subscripts must be established.

Further, when the range of values that can be taken by the subscript is expanded, the output of the array subscript conversion device changes accordingly, so that there is a drawback that the allocation position in the storage space of each element of the array must be moved. is there.

Object of the Invention An object of the present invention is to perform array subscript conversion that can be easily assigned to a one-dimensional array, regardless of whether the values that subscripts can take are established or how the range of values that subscripts can take is expanded. It is to provide a device.

According to the present invention, a one-dimensional array area allocated in a storage space is used as a multidimensional array in which elements are specified by a plurality of subscripts each having an integer including 0 as a value. An array subscript conversion device for converting an array into a one-dimensional array, wherein maximum value selection means for outputting the maximum value of all subscript values that specify elements of the multidimensional array, and each of the subscripts are output in series. Serializing means, a first register having the maximum value as an initial value, and a multiplication value of the content of the first register and the maximum value only when the maximum value and the output of the serializing means are not equal. A first multiplication means for obtaining the new contents of the first register, a second register having an initial value of 0, and a second multiplication means for obtaining a multiplication value of the contents of the second register and the maximum value. And the maximum value and the series When the output of the converting means is equal, the contents of the first register, the multiplication value of the second multiplying means, and further the second value.
The contents of the register are added, and when the maximum value and the output of the serialization means are not equal, the multiplication value of the second multiplication means and the contents of the second register are added and the result is added to the second register. A first addition means that is a new content of
The third register having 0 as an initial value, the third multiplication means for obtaining a multiplication value of the content of the third register and the maximum value, and the third value only when the maximum value and the output of the serialization means are not equal to each other. The second addition means for obtaining the addition value of the multiplication value of the third multiplication means and the output of the serialization means and making it the new content of the third register, and the values of all the subscripts are output from the serialization means. And a means for adding the contents held in the second and third registers to produce an output of the device.

Embodiments Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention. In the figure, the maximum value selector 1 is a circuit that selects the maximum value from the n subscripts i1 to in, and the serializer 2 has these n subscripts i1 to i1.
It is a circuit that outputs ~ in serially in time series.

3 is a power holding unit, which is a multiplier 31 and a power register 32.
And a switch 33. The exponentiation register 32 holds in advance the maximum value of the subscripts i1 to in which is the output of the maximum value selector 1 as an initial value. The multiplier 31 multiplies the output of the maximum value selector 1 and the contents of the exponentiation register 32, and supplies this multiplication value to the exponentiation register 32 via the switch 33.

The switch 33 operates so that it is turned off when the output of the maximum value selector 1 and the output of the serializer 2 are equal, and is turned on when they are not equal. Therefore, when the maximum value and the output of the serializer 2 are equal, the contents of the exponentiation register 32 keeps the previous value, and when they are not equal to each other, the multiplier 31
The power value that is the output of will be retained as new content.

Reference numeral 4 denotes an offset holding unit, which has a multiplier 41 and an adder 42.
And an offset register 43 and a switch 44.
The offset register 43 holds “0” as an initial value in advance. The multiplier 41 multiplies the output of the maximum value selector 1 and the offset register 43, and the adder 42 is the multiplier.
In addition to the addition of the output of 41 and the output of the offset register 43, when the switch 44 is on, the contents currently held in the exponentiation register 32 are also input for addition.

The switch 44 operates so that it is turned on when the output of the maximum value selector 1 and the output of the serializer 2 are equal, and is turned off when they are not equal. Therefore, the offset register 43, when the maximum value and the output of the serializer 2 are equal, the contents of the exponentiation register 44, the multiplication output of the multiplier 41,
The contents are updated by the result of the 3-input addition with the current contents of the offset register 43. Conversely, when they are not equal, the multiplier
2 of the multiplication output of 41 and the current contents of the offset register 43
The contents are updated according to the input addition result.

5 is a displacement holding unit, which is a multiplier 51,
It includes an adder 52, a displacement register 53, and a switch 54. The register 53 holds “0” as an initial value in advance. The multiplier 51 multiplies the contents of the register 53 and the output of the maximum value selector 1, and the adder 52 adds the multiplication result and the output of the serializer 2. The addition result is input to the register 53 via the switch 54.

The switch 54 is turned off when the maximum value and the output of the serializer 2 are not equal, and is turned on when they are equal. Therefore, the contents of the displacement register 53 are updated by the output of the adder 52 when the maximum value and the output of the serializer 2 are not equal, and conversely, the displacement register 53 keeps the previous contents.

The adder 6 adds the contents of both the offset register 43 and the displacement register 53 to obtain the device output t, and the addition timing is immediately after all the subscripts i1 to in have been output by the serializer 2. Timing.

The switch controller 7 controls each of the above-described operations of the switches 33, 44 and 54, and the maximum value output by the maximum value selector 1 and the subscript i1 sequentially output from the serializer 2
Each value of ~ in is compared with each other, and the above switch control is performed according to the magnitude relation.

Next, as a specific description of the operation of this embodiment,
Assuming the case of converting a three-dimensional array into a one-dimensional array, the first, second and third subscripts i1, i2, i3 (hereinafter, (i
Abbreviated as (1, i2, i3)), for example, (5,2,1), (4,
5, 5) and (5, 5, 5) will be given as examples.

First, as a first example, when (i1, i2, i3) = (5,2,1), the output of the maximum value selector 1 is "5". This value is stored in the exponentiation register 32 as an initial value at the start of conversion. Further, both the offset register 43 and the displacement register 53 are cleared to 0.

Then, the serializer 2 outputs i1, that is, "5". In this case, the value of i1 is equal to the value of the maximum value selector 1, so the switch 44 is turned on, but both the switches 33 and 54 are turned off. At this time, the output of the multiplier 41 is "0", which is the product of the value "0" stored in the offset register 43 and the output "5" of the maximum value selector 1. Adder
The output of 42 is the sum of the output “0” of the multiplier 41, the value “0” held in the offset register 43, and the value “5” held in the exponentiation register 32. That is, it becomes “5”, and this value is newly stored in the offset register 43. Also, the values held in the exponentiation register 32 and the displacement register 53 do not change. This is because both the switches 33 and 54 are off.

Next, the serializer 2 outputs i2, that is, "2".
In this case, the value of i2 is not equal to the output "5" of the maximum value selector 1, so that the switches 33 and 54 are turned on, but the switch 44 is turned off. At this time, the multiplier 31 is a power register.
The product of the value "5" held in 32 and the output "5" of the maximum value selector 1, that is, "25" is output. Therefore, this value is stored in the exponentiation register 32.

On the other hand, the multiplier 41 operates in the same manner as when i1 is output, and its output becomes “5 × 5”, that is, “25”. Also adder
Since the input of 42 is only the output "25" of the multiplier 41 and the value "5" held in the offset register 43, the output thereof is "30". This value is newly stored in the offset register 43.

Further, the multiplier 51 outputs the value “0” held in the displacement register 53 and the output “5” of the maximum value selector 1.
And the adder 52 outputs the sum "2" of the output "0" of the multiplier 51 and the output i2 of the serializer 2, ie, "2". The output “2” of the adder 52 is stored in the displacement register 53.

Finally, when i3, that is, "1" is output from the serializer 2, the on / off states of the switches 33, 44 and 54 are the same as when i2 is output, so that the exponentiation register 32 stores "25 ×
5 ”or“ 125 ”is stored in the offset register 43 as“ 3 ”.
“0 × 5 + 30”, that is, “180”, and “2 × 5 + 1”, that is, “11” are stored in the displacement register 53, respectively. Thereafter, the adder 6 adds the value "180" held in the offset register 43 and the value "11" held in the displacement register 53, that is, "191" to the output t of the array subscript conversion apparatus. To do.

Hereinafter, in the second and third input examples, the operation of each component is the same as that in the first input example, and therefore only the change of the contents of each register will be shown with reference to FIG.

In the second input example (i1, i2, i3) = (4,5,5), the content of the exponentiation register 32 is set to “5” as an initial value each time each subscript is output from the serializer 2. , "25", "25", "25"
Therefore, the content of the offset register 43 changes to "0", "25", "175" with "0" as an initial value. The contents of the displacement register 53 are "4", "4", and "4" with "0" as the initial value. Therefore, the output t of the adder 6 becomes "179".

In the third input example (i1, i2, i3) = (5,5,5), the content of the exponentiation register 32 remains the initial value “5” each time the subscript is output from the serializer 2. The contents of the offset register 43 do not change until the end, and the contents of the offset register 43 are "0" as an initial value,
It changes to "35" and "215", and the content of the displacement register 53 remains the initial value "0" and does not change to the end. Therefore, the output t of the adder 6 becomes "215".

In this way, the array subscript conversion apparatus in this embodiment always outputs one for each set of integers i1, i2, i3 of 0 or more and different output for each set of different i1, i2, i3. The value t can be generated.

2 realized on the one-dimensional array A (t) by this embodiment.
The allocation positions of the individual elements of the dimensional array M (i1, i2) and the three-dimensional array Q (i1, i2, i3) are shown in FIGS. 3 and 4.

In the present embodiment, for convenience of explanation, only the case of a three-dimensional array is shown, but by changing the number of inputs to the maximum value selector 1 and the serializer 2, an arbitrary number of two or more dimensions can be obtained. It is clear that the same effect can be obtained with the dimensional array.

EFFECTS OF THE INVENTION As described above, according to the present invention, by performing subscript conversion from a multidimensional array to a one-dimensional array without depending on the range of values that the subscript can take, the values that the subscript can take It is possible to allocate a multidimensional array whose range is not fixed to a one-dimensional array-like area, and no matter how large the range of values that each subscript of the multidimensional array can take is expanded, The effect is that it is not necessary to move the position of the element in the storage space.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention, and FIG. 2 is a diagram showing a change state of contents of each register and a device output state in the block of FIG. 1 in relation to a three-dimensional subscript array,
FIG. 3 is a diagram showing allocation positions of individual elements of a two-dimensional array allocated on the one-dimensional array by the block of FIG. 1, and FIG. 4 is allocated on the one-dimensional array by the block of FIG. FIG. 5 is a block diagram showing the arrangement of individual elements of a three-dimensional array, and FIG. 5 is a block diagram showing the configuration of a conventional array subscript conversion device. Description of main part code 1 …… Maximum value selector 2 …… Serializer 6,42,52 …… Adder 31,41,51 …… Multiplier 32,43,53 …… Register 33,44,54 ……switch

Claims (1)

[Claims] 1. A one-dimensional array when a one-dimensional array area allocated in a storage space is used as a multi-dimensional array in which elements are specified by a plurality of subscripts each having an integer including 0 as a value. An array subscript conversion device to an array, wherein maximum value selecting means for outputting a maximum value among values of all subscripts for specifying elements of the multidimensional array, and serializing means for serially outputting each of the subscripts A first register having the maximum value as an initial value, and a multiplication value of the contents of the first register and the maximum value is obtained only when the maximum value and the output of the serialization means are not equal to each other. A first multiplication means having new contents of the first register; a second register having an initial value of 0; second multiplication means for obtaining a multiplication value of the contents of the second register and the maximum value; The value and the output of the serialization means When they are equal, the contents of the first register, the multiplication value of the second multiplication means, and the contents of the second register are added, and when the maximum value and the output of the serialization means are not equal, the second value is added. The first addition means for adding the multiplication value of the multiplication means and the contents of the second register to obtain the new contents of the second register, the third register having 0 as an initial value, and the third register A third multiplication means for obtaining a multiplication value of the content and the maximum value; and a multiplication value of the third multiplication means and an output of the serialization means only when the maximum value and the output of the serialization means are not equal. Second addition means for obtaining an addition value and making it the new contents of the third register, and adding the contents held in the second and third registers after the values of all the subscripts are output from the serialization means Means to output the device Array subscript conversion device, characterized in that.