JPH037977B2 - - 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, a vector {v _i } is divided into blocks, v ₀ v ₁ ...v _o-1 , v _o , v _o+1 ...v _2o-1 ,
It is stored in external memory as a block of length n, such as v _2o . 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, 2
Consider a 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 |∈[0,m]}i, that is, the 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 FFT and matrix multiplication. In other words, it can be considered that such an access pattern appears quite commonly in numerical calculations. Therefore, in order to efficiently use block random access external memory, it is necessary to make efforts to devise programs, and even with such efforts, high performance may not be obtained.

Another problem is that when attempting to calculate random phenomena such as plasma particle codes, random values may be handled as a data structure. In general, list vector (indirect address)
Is required. Vector processors usually do not work well in this case. For this reason, an attempt is made to sort the data set by value. It is possible to sort using a calculation system, but it generally requires a considerable burden and requires a lot of I/O.
No improvement in execution speed can be expected. For this reason, it is desirable to sort them in external memory.

(Object of the Invention) An object of the present invention is to provide an external memory device that has high performance, allows flexible access, and can also support random simulation.

(Structure of the Invention) According to the present invention, an external memory that transfers data based on instructions from a computing system includes a prime number of memory modules, and an input that holds vector data from the computing system. a buffer, an output buffer for holding vector data to the computing system, inverse linear permutation means for replacing vector data from the input buffer and sending it to the memory module, and replacing the vector data from the memory module. linear permutation means for sending to the output buffer; parallel sorting means for performing a part of parallel sorting between the output buffer and the input buffer; A memory device is obtained, comprising a control unit that generates read/write commands and addresses, generates the first and second replacement commands, and controls the parallel sorting means.

(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). Assume 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 direction data elements A ₀₀ , A ₁₀ , A ₂₀ , A ₃₀ , A ₀₁ , A ₁₁ ,
Vectors such as A ₂₁ and A ₃₁ access elements separated by four elements. Also, the opposing element
A ₀₀ , A ₁₁ , A ₂₂ , and A ₃₃ are accesses to elements five elements apart. These are called accesses to a 4-ordered vector and a 5-ordered vector, 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 if j is 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 (modM), and its inverse substitution L ^-1 _d is L ^-1 _d :i→b+d・i (modM), where 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 subscripts i ₁ , i ₂ ,
i ₃ starts from 0, n ₁ -1, n ₂ -1, n ₃ -1 respectively
It shall end with

Here, i ₁ , i ₂ , i ₃ are constants, and k is an index variable. If array A is stored starting from address a, then A(i ₁ , i ₂ , k) is a+n ₂ n ₃ i ₁ +
n ₃ i ₂ +k, that is, b=a+n ₂ −n ₃ ·i ₁ +n ₃ ·i ₂ , and d=1. Similarly, for A(i ₁ , k, i ₃ ), b=a+n ₂ ·n ₃ ·i ₁ +i ₃ and d=n ₃ .

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 stored in memory module 0 as A ₁₁ , memory module 1 as A ₁₂ , memory module 2 as A ₁₃ , and so on.

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 respectively expressed as (b+d·i) modM and [b+d−i)/M]. Here, [x] represents the largest integer smaller than x.

Here, if =b(modM) and =d(modM), the i-th module number can be expressed as (+·i)modM (known from number theory).

The linear permutation is (+・i)→i(modM), 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 limited to prime numbers if a means for resolving conflicts is used.

The linear permutation is performed as follows. First, correspond to convert the -ordinal vector into an ordinal vector, then correspond to and rotate and permute the obtained ordinal vector. 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), A(4,2) is b=(A(1,
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 34, 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,
b=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 rotation 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. Parameter b′ given to skip permutation and rotation permutation in this case,
d' is obtained from b'=M-b(modM) d'・d=1(modM).

Linear replacement is performed as described above. A method for sorting a specified set of data by value using this linear permutation will be described below. This sort is a parallel sort, basically Batcher′s
It is based on the sort algorithm.

Batcher's sort algorithm is Bitonic sort, which is a method of creating a bitonic sequence of length 2n from bitonics of length n. Sorting requires N log ₂ N, where N is the number of elements, and is more time-consuming than heap sort, but it is advantageous in that processing is simple and parallel processing is possible.

First, we will explain the processing procedure of bitonic sort, and then we will explain how bitonic sort is supported by linear permutation.

A bitonic sequence of length 2n is expressed as follows a ₁ a ₂ …a _o a _o+1 …a _2o If {in then a _{i-1 <a i i>} n then a _i-1 > a _i }.

This sorting is accomplished by (log ₂ n+1) stages of shuffle exchange and comparison. In Figure 4, n=4
It is an explanatory diagram about the case. As shown in the figure, the shuffle replacement scheme is the same for each stage.
The pairs of data selected by the shuffle exchange are compared with each other, and based on the size relationship, the smaller one is moved to the left.
Output the larger one to the right.

This shuffle exchange creates a pair (i, n+i) for C _i , assuming that the comparison numbers are C ₀ , C ₁ , C ₂ , and C ₃ in order from the left. Therefore, the length
To sort 2n bitonic columns, first, vector element i is sent to i, vector element (n+i) is sent to i, and the pairs are compared.

The above pairs can be easily obtained by performing linear permutation (this can be done only by rotational permutation).

As explained above, by using linear permutation, we can flexibly access large arrays that appear in numerical calculations, and by introducing parallel sorting and supporting it with linear permutation, we can effectively perform random simulations. External memory devices such as those that can be used become possible.

(Example) Next, the present invention will be described in detail with reference to the drawings. FIG. 1 is a system configuration diagram showing an embodiment of the present invention. The calculation system 1 (not shown) is
Commands are input and output to the external memory device 2 via the transfer line 18, and vector data is input and output via the transfer buses 13 ₁ to 13 _n and 71 ₁ to 71 _n . 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 performs the above-mentioned processing based on (b, d).
Calculate b′ and d′. (This calculation was explained in the explanation of the principle). The calculated b' and d' are sent to the inverse linear substitution means 4 via the transfer line 84, and input to the input buffer 3.
A data transfer path is established between the memory modules 5 1 to 5 n and the memory modules 5 ₁ to 5 _n . Further, the control processor 8 calculates [(b+d・i)/M], calculates the address within each module, and the calculated address is sent to the input buffer 3 via the transfer line 83 and transferred to the transfer line 34. ₁ to 34 _o , inverse linear replacement means 4, transfer line 4
5 ₁ to 45 _n to memory modules 5 ₁ to 5 _n . Control processor 8 is memory module 5
A write designation is sent to ₁ to 5 _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 in the input buffer 3, mask bits are generated based on this information to prevent unauthorized writing (not shown).

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 of the memory modules 5 ₁ to 5 _n via the transfer line 85, and the read data and the read data are 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 first replacement means 6 via the transfer line 86, thereby establishing a transfer bus. The data vector is replaced by the first replacing means 6, and the data is sent to the output buffer 7 via the transfer lines 67 ₁ to 67 _n . 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 exchanged 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
Unscramble p-ordered Vectors,” IEEE,
Trans on Comput., Vol.C−23, No.11,
pp1105-1115 (1974))
This can be easily realized by apart interconnection (k-interconnection).

On the other hand, a sort command is issued from the calculation system 1 in the following format.

sort(a,n) a is the start address of the data vector to be sorted, and n is the number of elements. Assume that the data vector is a bitonic sequence of length n. The control processor 8 connects paths 79 ₁ to 9 _n to parallel sorts 9 ₁ to 9 n.
79 Open _n and prepare for sorting.

In bitonic sort, as explained in the section on the principle of the invention, it is necessary to send the pair (i, n+i) to the comparators 9 ₁ to 9 _n , so first element i is sent to the comparators 9 ₁ to 9 n.
9 Send to _n . (,) is sent to the linear permutation 6, where =i+a(modM), =1. The data vector of length m read from the memory module is sent to the output buffer 7 in the same manner as when reading, and is sent to the comparators 9 ₁ -9 _n via transfer lines 79 ₁ -79 _n . Next, control processor 8
is =a+i+n for the linear replacement means 6
(modM), = 1, and similarly sends the other data of the pair to the comparators 9 ₁ to 9 _n . The comparators 9 ₁ to 9 _n compare the magnitudes of these two data, exchange the data based on the commands from the control processor 8 supplied via the transfer line 89, and send the results to the transfer lines 93 ₁ to 93. Put it in _n . Then, in the same way as when writing, from the input buffer 3 through the inverse linear replacement means 4, the memory module 5 ₁
~5 written to _n . The address at this time can be obtained from the bitonic sort scheme shown in FIG.

FIG. 3 shows a block diagram of one of the comparators 9 ₁ -9 _n . Transfer line 79 _i (i=1, 2,..., m)
The first data sent through gate 9
11 to the transfer line 917 and register 9
Sent to 12th. The second data is gate 911
is sent to register 913 via transfer line 918. The magnitude comparator 914 is connected to registers 912 and 9.
13, the result is sent to the exchanger 915 via a transfer line 921 according to the content of a transfer line 89 from the control processor. Exchanger 915 is a data exchanger composed of ordinary selectors, and exchanges the data on transfer lines 918 and 920 according to the contents of transfer line 921, or sends the data to output lines 922 and 923 in that order. gate 916
first sends the contents of transfer line 922 to transfer line 93 _i ,
The contents of the transfer line 923 are sent to the transfer line _93i .

(Effects of the Invention) As explained above, according to the present invention, data can be exchanged quickly and flexibly with a calculation system for large-scale matrices and arrays that normally appear in numerical calculations, and support for random simulation is also provided. An external memory device that can support parallel sorting can be provided.

[Brief explanation of drawings]

FIG. 1 is a block diagram of an external memory device showing one embodiment of the present invention, FIG. 2 is a block diagram of a linear permutation means, FIG. 3 is a block diagram of one component of parallel sorting, and FIG. 4 is a block diagram of a bytenik. It is an explanatory diagram of sorting. In the figure, 2...external memory device, 3...input buffer, 4...inverse linear replacement means, _{51 to 5n} ...
...Memory module, 6...Linear replacement means, 7...
...Output buffer, 8...Control processor, 9 ₁ ~
9 _n ...Indicates a comparator.

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 to the computing system, and a memory module that replaces the vector data from the input buffer. linear permutation means for permuting vector data from the memory module and sending it to the output buffer; and a parallel permutation means between the output buffer and the input buffer for performing a part of the parallel sort. a control unit that interprets instructions from the computing system, generates read/write commands and addresses for the memory module, generates the first and second replacement commands, and controls the parallel sorting unit; A memory device comprising: