JPH037976B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a high-performance external memory device system for supporting large-scale numerical calculations.

(Prior art and its problems) So-called supercomputers are provided with high-speed external memory to support large-scale numerical calculations.

The external memory architectures provided typically employ block random access, similar to disk devices. Block random access means that, for example, vector {v _i } is divided into blocks, v ₀ v ₁ ... v _o-1 , v _o v _o+1 ... v _2o-1 , v _3o
... is stored in the external memory as a block of length n. The purpose of adopting this architecture is to avoid rewriting existing programs or making major changes to the operating system.

However, block random architecture
There are cases where numerical calculations are inappropriate. for example,
Consider a two-dimensional array {A _ij }. This array
It is assumed that the blocks are divided and stored in the order of (i, j), such as A ₀₀ A ₀₁ . . . A _{0o -1} , A 0o . . . , A ₁₀ A ₁₁ . Now {A _ij |j∈[0,m]}i,
That is, vectors A _i0 , A _i1 , ... A _io -1 , A _io ... obtained by fixing i and changing only j to 0, 1, 2, etc.
When inputting and outputting data, efficient input and output can be achieved by transferring it in blocks.
However, on the other hand, for the vectors A _0j , A _1j , A _{2j .} With input or output of a vector of length m, in the worst case, m blocks of input or output are required. Such an access pattern necessarily exists because, for example, in the implicit method, which is one of the differential resolution methods for partial differential equations, scans using different axes are required. It also appears in multidimensional FETs and matrix products. In other words, it can be considered that such an access pattern appears quite commonly in numerical calculations. Therefore, in order to use block random access external memory efficiently, it is necessary to make efforts to devise programs, and even with such efforts, high performance may not be obtained.

(Object of the Invention) An object of the present invention is to provide an external memory device that achieves extremely high performance and flexible access by enabling word-by-word processing.

(Structure of the Invention) According to the present invention, there is provided an external memory device that transfers data based on instructions from a computing system, which retains a prime number of memory modules and vector data from the computing system. an input buffer, an output buffer for holding vector data from the calculation system, linear permutation means for linearly permuting the output of the memory module and sending it to the output buffer, and linear permutation means for linearly permuting the output of the input buffer and transmitting it to the memory An inverse linear replacement means to send to the module and a command from the calculation system are interpreted, and an address to the memory module is used to generate a write/read command, and to send the address to the memory module to the linear replacement means and the inverse linear replacement means. There is obtained an external memory device characterized in that it is comprised of a controller that sends control parameters.

(Principle of the invention) Next, the principle of the invention will be explained. First, consider a two-dimensional array {A _ij }. Access to the elements of this array depends on the computational algorithm, but typical access is column-wise or row-wise.
Alternatively, a diagonal direction is assumed. For simplicity, the size of this array is assumed to be A(4,4). Suppose that the following is stored in memory:

A ₀₀ A ₀₁ A ₀₂ A ₀₃ A ₁₀ A ₁₁ A ₁₂ A ₁₃ A ₂₀ A ₂₁ A ₂₂ A ₂₃ A ₃₀ A ₃₁ A ₃₂ A _33The data elements in the column direction of this array are stored next to each other. This case is called a 1-ordered vector format, or simply an ordered vector. One-row data elements A ₀₀ , A ₁₀ , A ₂₀ , A ₃₀ , A ₀₁ , A ₁₁ ,
Vectors such as A ₂₁ and A ₃₁ access elements four elements apart. Also, the opposing element
A ₀₀ , A ₁₁ , A ₂₂ , and A ₃₃ are accesses to elements five elements apart. These are called accesses to 4-ordered vectors and 5-ordered vectors, respectively.

Similarly, for the three-dimensional data array, A(n ₁ ,
n ₂ , n ₃ ) (where n ₁ , n ₂ , n ₃ represent the size), the vector obtained by changing k of A _ijk to 0, 1, 2, ... is an ordinal vector, and the vector obtained by changing j The vector obtained by changing i is an n ₃ -ordered vector, and the vector obtained by changing i is an n ₂ ·n ₃ -ordered vector.

Generally, data is transferred from an external memory to a computing system by replacing an n-ordered vector with an ordered vector, and writing to an external memory is performed by replacing an ordinal vector with an n-ordered vector. Corresponds to transfer. To explain more specifically, linear permutation L _d is defined as follows.

L _d :b+d・i→i (mod M) Also, its inverse substitution L ^-1 _d is L ^-1 _d :i→b+d・i (mod M) Here, b and d are constants, and d is d - is a constant corresponding to an ordinal vector.

b and d are given as follows. Consider a program as an example. In the example below, the subscript
i ₁ , i ₂ , i ₃ start from 0, and are respectively n ₁ -1, n ₂ -1,
Assume that it ends with n ₃ −1.

Here, i ₁ , i ₂ , i ₃ are constants, and k is an index variable. Assuming that array A is stored starting from address a, the address of A(i ₁ , i ₂ , k) is a+
Since n ₂・n ₃・i ₁ +n ₃・i ₂ +k, b=a+
n ₂ · n ₃ · i ₁ + n ₃ · i ₂ , d=1. Similarly, A(i ₁ ,
k, i ₃ ), b=a+n ₂・n ₃・i ₁ +i ₃ , d=
_n3 .

Next, storage in memory will be explained. Parallel processing is essential for high-speed transfer, and memory is divided into multiple memory modules. Array data is stored as vectors along the memory module. For example, A _ij is A ₁₁ in memory module 0, A 12 in module 1, and A ₁₂ in module 2.
A ₁₃ , etc. are stored in A 13 , etc.

Assuming that there are M memory modules, the module number and address within the module of the address Add are Add mod M and [Add/M], respectively.

Also, the address of the vector element to be transferred is
If we write about the i-th address, then b+d・i
The module number and address within the module are (b+d・i) mod M, [(b+d・i)/
M]. Here, [x] represents the largest integer smaller than x.

Here, = b (mod M), = d (mod M)
Then, the i-th module number can be expressed as (+·i) mod M (known from number theory).

The linear permutation is (+・i)→i(mod M), and this permutation is (,M)=1, that is,
This is done without contention when b and M are relatively prime. Therefore, although it is desirable that M be selected from prime numbers, it is not necessary to limit it to prime numbers if a means for resolving conflicts is also used.

The linear permutation is performed as follows. First, the -order vector is converted into an order vector, and then the obtained order vector is rotated and permuted. This replacement will be explained with an example. now,
Assume that there are five memory modules, that the size of array A is 8×8, and that array A is stored starting from address 0. A(1,2), A(2,2), A(3,
2), the vector A(4,2) is b=(A1,
2), and by setting d=8, the address of the element can be obtained. The address of A(1,2) is 10, =10mod5=0,=8mod5=3
It is. The address of each element is A(1,2), A(2,
2) are 10, 18, 26, and 34 in the order of memory modules 0, 3, and 3, respectively.
It's in 1 and 4.

The vector read from each module is A
(1,2), A(3,2), -, A(2,2), A(4
，
2), and the following substitutions must be made: 0 3 1 4 0 1 2 3. For this reason,
=0, that is, rotational replacement is performed at 0 position. The resulting vectors are A(1,2), A(3,2), -, A(2,2), A
(4,2). If we collect these vector elements in 3-element intervals, we get A(1,2), A(2,2), A(3,2), A(4
，
2), -, and an ordered vector is obtained. This replacement is called skip replacement.

In this way, linear permutation can be realized by combining rotational permutation and skip permutation.

On the other hand, the inverse permutation L ^-1 _d is an inverse permutation of the linear permutation described above, and is achieved by first performing a skip permutation and then performing a rotation permutation. Parameters b′ given to skip permutation and rotation permutation in this case,
d' is obtained from b'=M-b(mod M) d'・d=1(mod M).

(Example) Next, a detailed explanation will be given using the drawings. FIG. 1 is a system configuration diagram showing an embodiment of the present invention.
The calculation system 1 inputs and outputs commands to and from the external memory device 2 via the transfer line 18 and vector data via the transfer buses 13 and 71. Computing system 1 sends commands of the following format to control processor 8.

command (b, d, n) where command is read or write, b is the vector base address, d is the skip distance,
n is the vector length to be transferred.

First, writing of vector data will be explained. A write (b, d, n) command is sent to the control processor 8 via the transfer line 18. The control processor 8 calculates b' and d' based on (b, d). (This calculation was explained in the explanation of the principle). The calculated b' and d' are sent to the inverse linear permutation means 4 via the transfer line 84, and a data transfer path between the input buffer 3 and the memory modules ₅₁ to _5n is established. In addition, the control processor is [(b+d・i)/
M], and calculates the addresses within each module. The calculated addresses are sent to the input buffer 3 via the transfer line 83, and are transferred to the transfer lines 34 ₁ to 3.
4 _n , the inverse linear substitution means 4 and the transfer lines 45 ₁ to 45 _n to the memory modules 5 ₁ to _{5 n} , and the control processor 8
5 Sends a write command to _n via the transfer line 85. The address is now set. Next, the vector data sent from the calculation system 1 is taken into the input buffer and sent to the memory modules 5 1 - 5 n via the transfer lines 34 ₁ - 34 _n , the inverse linear substitution means 4, and the transfer lines _{45 1} - 45 _{n .} sent to and written to. The vector length n indicates the range of vectors to be written, and the input buffer 3 uses this information to
Mask bits are generated and a method (not shown) is taken to prevent unauthorized writing.

Next, reading will be explained. A read (b, d, n) command is sent from the computing system 1. The control processor 8 generates and sends addresses to each memory module 5 ₁ to 5 _n in the same manner as in writing. Then, a read command is sent to each memory module 5 ₁ to 5 _n via the transfer line 85, and the read data is sent as vector data to the linear replacement means 6 via the transfer lines 56 ₁ to 56 _n . Before this, the control processor 8 generates (,) from (b, d) to the linear replacement means 6 via the transfer line 86, thereby establishing a transfer path. The data vector is replaced by the linear replacement means 6, and the transfer line 67
The data is sent to the output buffer 7 via ₁ to _67n . Vector length n is used to indicate the range of valid vectors (not shown). The contents of the output buffer 7 are sent to the computing system via a transfer bus 71.

As described above, data is transferred between the computing system and the external memory.

Next, FIG. 2 shows a block diagram of an example of the configuration of the linear replacement means. The rotation permutation means ₆₁ executes b-position rotation permutation corresponding to (,) sent through the transfer line 86, and is realized by a shift register. The outputs are sent to the skip replacement means ₆₂ via transfer lines ₆₁₁ to _61n . Skip replacement means 6 ₂ is (,),
Corresponding to d, - skip substitution is performed.
This skip substitution is based on Swanson, R.C.
(“Interconnections for Parallel Memories to
Unscramblep−ordered Vectors,” IEEE,
Trans on Comput, Vol.C−23, No.11,
pp1105-1115 (1974))
This can be easily realized by apart interconnection (k-interconnection).

(Effects of the Invention) As described above, according to the present invention, flexible access to large-scale data structures (mainly matrices and arrays) that appear in numerical calculations is possible.
Furthermore, parallel processing enables high-speed processing.

Furthermore, by making the number of memory modules a prime number, it is possible to eliminate memory contention, making it possible to create a high-performance external memory device with extremely simple control and a simple system configuration.

[Brief explanation of drawings]

FIG. 1 is a system configuration diagram of an external memory device showing one embodiment of the present invention, and FIG. 2 is a block diagram of linear replacement means which is a part of the external memory device. In the figure, 1... calculation system, 2... external memory device, 3... input buffer, 4... inverse linear replacement means, 5 ₁ to 5 _n ... memory module, 6...
. . . linear replacement means, 7 . . . output buffer, 8 . . . control processor, respectively.

Claims (1)

[Claims] 1 A prime number of memory modules, an input buffer that holds vector data from a computing system, an output buffer that holds vector data from the computing system, and linearly permutes the output of the memory module to the output buffer. a linear permutation means for inverse linear permutation of the output of the input buffer and sending it to the memory module; and an inverse linear permutation means for decoding the command from the calculation system and converting the address and write/read command to the memory module. An external memory device comprising: a control section that generates control parameters and sends control parameters to the linear replacement means and the inverse linear replacement means.