JPH0746350B2 - Vector calculator - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Object of the Invention] (Field of Industrial Application) The present invention relates to a vector computer that performs vector processing by a pipeline system to perform high-speed processing such as scientific and technological calculation.

(Prior Art) For vector data regularly arranged in memory,
An operation for repeatedly executing the same operation is called a vector operation. Taking Fortran as an example, as shown in Fig. 6 (a), B and C in the vectors A, B, and C are used as operands, the result is assigned to destination A, and this is assigned by the DO loop. A vector operation is an operation that is repeatedly performed while sequentially changing the subscript I.

A pipeline method has been conventionally known as a method for speeding up this vector operation. According to this pipeline method, the operation of FIG. 6 (a) is performed as shown in FIG. 6 (b). This figure shows an example in which the number of pipeline stages is set to n = 3. First, B in cycle 1
(1), C (1) issues a read request, refers to the operand, and starts the operation. Next cycle 2, cycle 1
The calculation is started by referring to B (2) and C (2) without waiting for the result of the calculation started at. In cycle 3, since the result A (1) of the operation started in cycle 1 is obtained, the operation is started by writing this result and referring to B (3) and C (3) at the same time. Thereafter, similarly, in cycle i + 2, A (i) as the result of the operation started from cycle i is obtained and at the same time B
The calculation by (i + 2), C (i + 2) is started.

In this way, in the vectorization process in which the iterative operation is continuously processed without waiting for the result of one operation, even if two operation cycles are required as in the above example, the first operation result A (1) Although there is a delay of 2 cycles before the calculation of, there is an advantage that the calculation result is calculated every cycle thereafter.

Further, as shown in FIG. 7A, for example, the operand (A (1)) and the destination (A (I + 3))
In the case of recursive data reference in which the vectors of the same are the same, the difference (3) between the subscript of the destination vector A and the subscript of the operand vector A is (3)
If (= 3) or more, the result A (4) of the operation A (1) + C (1) started in cycle 1 ends in cycle 3, as shown in FIG. In cycle 4, A (4) and C (4) can be referenced. Therefore, this operation can be vectorized.

However, in such recursive data reference,
For example, as shown in FIG. 8A, when the difference (1) between the subscript of the destination vector A and the subscript of the operand vector A is less than the pipeline stage number n (= 3), the cycle 1 Since the calculation result A (2) of the started A (1) + C (1) has not yet been obtained in cycle 2, reference of A (2), C (2) can only be made in cycle 4 at which this calculation ends. Absent. Therefore, in this case, the operation cannot be vectorized.

As described above, even if the pipeline method is adopted, vectorization is not possible when the difference between the subscripts of the destination and operand vectors is less than the number of pipeline stages n.

Therefore, when recursive data reference occurs, the compiler is made to remember the pipeline stage number n in advance, and at the time of compilation, it is determined whether or not the difference between the above subscripts is greater than the pipeline stage number n. It is also possible to decide whether or not to vectorize. However, in this case, when the number of pipeline stages is increased, the compiler has to be rebuilt according to the new number of pipeline stages. In addition, if the number of pipeline stages is different for computers with the same architecture, it is necessary to prepare a compiler for each computer according to the number of pipeline stages of the computer. There was a problem of becoming.

Further, as shown in FIG. 9, when a variable k is included in the destination subscript, this variable k is not determined at compile time but is determined at run time. Therefore, even if k ≧ n at run time, vectorization is performed. It becomes impossible to do.

Furthermore, in the subroutine shown in FIG.
Although the destination and the operand of are not the same on the surface, if the first argument and the second argument are called with the same argument at the caller of the subroutine as shown in FIG. 10 (b), the same regression as above is performed. The problem of dynamic data reference arises. In this case, it is conceivable that the above problem can be avoided by applying a restriction such as not assigning the same variable to the first argument and the second argument, but in this case, the versatility of the subroutine is characteristic. Damaged and less portable of the program.

Furthermore, as shown in FIG. 11, in adjacent operations,
A similar problem occurs when a part of the memory is defined overlappingly. That is, this example is an example in which the address of the memory is attached in byte units with 2 bytes for 1 word.
Is a 1-byte integer and INTEGER is a declaration statement that declares a 2-byte integer. Here, at EQUIVALENCE (D, A), the 12th
As shown in the figure, since the areas of D and A are defined by overlapping, A which is a part of the storage location of the calculation result of sentence 1 is A.
(2) is referred to in the following sentence 2. Therefore, the statement 2 cannot be executed until the execution of the statement 1 is completed.

From the above, in the conventional vector computer, vectorization is abandoned for operations that may perform recursive data reference. For this reason, there is a problem that the calculation speed is several tens of times slower than the case of vectorization.

(Problems to be Solved by the Invention) As described above, in the conventional vector computer, since the vectorization is not performed when the recursive data reference occurs, the execution speed of the operation cannot be increased. was there.

The present invention has been made to solve such problems.
It is an object of the present invention to provide a vector computer which can vectorize all operations that can be vectorized even for operations that cause recursive data reference, thereby significantly increasing the operation speed.

[Structure of the Invention] (Means for Solving Problems) The present invention stores vector data, and at least two of word units, halfword units, or byte units are stored.
A vector computer in which an arithmetic processing unit sequentially reads vector data from a memory that can be accessed in various ways and performs vector arithmetic processing by pipeline processing of a predetermined number of stages is characterized by including the following means. That is, the present invention indicates the write memory address of the data being processed held in each stage of the pipeline and whether the data being processed is the word, the halfword, or the byte. In order to store the size in correspondence with each stage of the pipeline, a register file composed of a FIFO memory with registers of the number of stages set corresponding to the number of stages of the pipeline, and sequentially output from the arithmetic processing unit Storage means for storing the calculated operation result in a storage location of the memory designated by the write memory address sequentially read from the register file, and when the operation processing section reads the vector data from the memory, Read memory address and the size of the data to be read and the memory stored in the register file Inspecting means for inspecting whether or not the writing area and the reading area specified by the both memory addresses of the memory are overlapped based on the address and the size of the data, and when the inspection means detects the duplication, the inspection means And means for prohibiting the arithmetic processing unit from reading data from the memory and permitting the arithmetic processing unit to read data from the memory when no duplication is detected.

(Operation) In the present invention, the write memory address of the data and the size indicating whether the data is a word, a halfword, or a byte are associated with the data stored in each stage of the pipeline. Since the data is stored in the register file, if the memory address stored in the register file and this size are referred to, the data to be written at that memory address is currently undergoing arithmetic processing and that data is stored in the memory. You can see how much of the area to rewrite. Therefore, when the arithmetic processing unit attempts to read the vector data from the memory, the checking means determines the read memory address, the size of the data to be read, and the memory address and size of the data currently stored in the register file. Checking the overlap between the area of the memory to be read and the area of the memory currently being processed and subsequently written, and if the overlap is detected, the arithmetic processing unit reads the data from the memory. Is prohibited and the reading from the memory is made to wait. Therefore, the arithmetic processing unit can sequentially read the vector data from the memory and put it on the pipeline unless such a standby instruction is issued, so that all the vectorizable portions are vectorized.

As described above, according to the present invention, even if recursive data reference occurs, the process proceeds as vectorizable unless a read prohibition command for the memory is issued.
All the parts that can be vectorized are vectorized, which can significantly speed up vector operations.

(Example) Hereinafter, the details of the present invention will be described based on an example shown in the drawings.

FIG. 2 is a diagram showing a schematic configuration of a vector computer according to an embodiment of the present invention.

The vector calculator has a memory 11 for storing vector data.
And sequentially read vector data from the memory 11 to perform vector processing based on the pipeline system,
The operation processing unit 12 stores the operation result in the memory 11, and the pipeline control unit 13 for permitting the operation processing unit 12 to read data from the memory 11.

The memory 11 is a memory of 1 word and 2 bytes, has an address space of 8 bits, and can be accessed in two ways, word unit and byte unit.

The arithmetic processing unit 12 performs three-stage pipeline processing.

The pipeline control unit 13 is specifically configured as shown in FIG.

That is, the write information register (hereinafter, referred to as “W register”) 21 is provided with the write memory address (hereinafter, simply referred to as write address) WA given from the arithmetic processing unit 12 via the address bus AB and the DS line. The given data size WDS and the valid bit WVB given via the VB line are stored as write information.

The register file 22 is composed of three stages of registers 23, 24, 25 in a shift register configuration connected in cascade.
The writing information stored in the memory is sequentially stored and a first-in-first-out (FIFO) memory that outputs the information in the order stored is configured. The number of stages (three stages) of the register file 22 corresponds to the number of stages of the pipeline in the arithmetic processing unit 13. In each register 23 to 25 of this register file 22,
The write address WAi (i = 1, 2, 3) of the data in the middle of the operation currently in the pipeline stage, the data size DSi, and the valid bit VBi indicating the validity of the data are stored.

Read information register (hereinafter referred to as "R register") 26
Is a read memory address (hereinafter simply referred to as read address) RA given from the arithmetic processing unit 12 via the address bus AB, and a data size RDS given via the DS line.
And the valid bit RVB provided via the VB line are stored as read information. The write timing to both the registers 21 and 26 is given by the write signal W output from the arithmetic processing unit 11, for example.

These write information and read information are 10-bit data, and as shown in FIG. 3, address information is arranged in lower 8 bits, size bit is arranged in upper 2 bits, and most significant bit (msb). The valid bit is placed in. The size bit indicates that the size of data to be written or read is a word when it is "0", and that the size of data to be read or written is a byte when it is "1". When the valid bit is "1", it indicates that the address is valid, and when the valid bit is "0", it indicates that the address is invalid.

The write information stored in the respective registers 23 to 25 of the register file 22 and the read information stored in the R register 26 are given to the comparators 27, 28 and 29, respectively. Comparators 27 to 29, from the write information and the read information stored in each of the registers 23 to 25, to check the overlap of the write area and the read area of the memory 12, as a result, if the overlap is detected, Outputs "0", and outputs "1" if no duplication is detected. The inspection results from these comparators 27 to 29 are given to the AND gate 30. When the duplication is detected by any one of the comparators 27 to 29, the AND gate 30 sets the REQ signal to “0” to prohibit the arithmetic processing unit 11 from reading the data from the memory 12, and the comparator 27 to 29 If no duplicates are detected from 29, REQ
The signal is set to "1" to allow the arithmetic processing unit 11 to read data from the memory 12.

FIG. 4 is a diagram showing a more detailed configuration of the comparator 27. Since the comparators 28 and 29 also have the same configuration as this, the description thereof will be omitted.

Eight XOR gates 31-38 are 1 in register file 22
This is for comparing the corresponding bits of the 8-bit write address WA1 on the register 23 in the second stage and the 8-bit read address RA on the R register 26, and outputs "0" when the bits match. To do. XOR comparing the LSB of the address
The output of gate 31 is provided as one input of AND gate 40. The size bit WDS stored in the register 23 at the first stage of the register file 22 and the size bit RDS stored in the R register 26 are input to the other two inputs of the AND gate 40. This AND gate 40 is provided when the size of the data to be read or the data processed in the first stage of the pipeline indicates a word, that is, when either RDS or WDS1 indicates "0", This is to make the output "0" regardless of whether the address LSBs match or mismatch. The output of this AND gate 40 and XO
The outputs of the R gates 32 to 38 are input to the NOR gate 41. The NOR gate 41 has a write address WA1 stored in the register 23 of the first stage of the register file 22 and an R register 2
When the read address RA stored in 6 matches or partially overlaps, "1" is output. The output of the NOR gate 41 is given to one input of the NAND gate 42.
The valid bit WVB1 stored in the register 23 in the first stage of the register file 22 is input to the other input of the NAND gate 42. The output of this NAND gate 42 is AN
It is input to the D gate 43, and the valid bit RVB on the R register 26 is input to the other input of the AND gate 43. These NAND gate 42 and AND gate 43
Are provided to correct the result of the address comparison with the valid bits WVB1 and RVB. These two gates make the address on the R register 26 invalid, that is, RVB
When is "0", the read address is invalid even if the address areas do not overlap. Therefore, the comparator reads "0" so that data is not read from memory.
Is output, and the address on the R register 26 is valid,
And when the address in the register fill 22 is invalid, that is,
When WVB1 is "0", even if duplicate read address and write address are detected, the comparison address is 1
Since one is invalid, the comparator outputs "1".

Next, the operation of the vector computer according to the present embodiment configured as described above will be described.

First, in the first cycle C1, the write information of the address "10H" and the size "word" is stored in the register 23 of the first stage of the register file 22, and the address "11" is stored in the R register 26.
It is assumed that read information of "H" and size "byte" is stored. Since both of these information are valid, valid bit WV
B1 and RVB are both "1". It should be noted that the W register 21 stores the address at which the result of the operation based on the data in the memory indicated by the R register 26 should be stored. In cycle C1, the comparator 27 compares the address “10H” with the address “11H”, but the comparison result of both is the same, and since both addresses are valid, the output of the comparator 27 becomes “0” and the REQ signal Becomes "0" and data is not read at address "11H".
Address "11H" remains valid on R register 26.
At the same time, the address “10H” moves to the second stage of the register file 22.

In the second cycle C2, the two addresses are compared by the comparator 28, "0" is similarly output, the address "11H" remains on the R register 26, and the address "10H".
Moves to the third stage.

In the next third cycle C3, the two addresses are compared by the comparator 29, "0" is similarly output, and the address "11H" remains in the R register 26.

Since the output of the AND gate 30 is 0 during the cycles C1 to C3, the address and size are not moved from the W register 21 to the register file 22. Therefore, the read address and the write address of the same operation are not compared. In cycle C3, data is written by the address “10H”, and the address “10H” disappears from the register file 22. As a result, in the next fourth cycle C4, the data is read by the address "11H", the address and size on the W register 21 are stored in the register file 22, and the R register 26 and the W register 21 are stored. , The address and size of the data for the next operation are stored.

If the size of address "10H" is byte, it is determined that it does not overlap the area of address "11H" because all bits of the address are compared, and in cycle C1 the address "11H" Read-out is performed.

As described above, according to this embodiment, the reading of the data overlapping the area of the address where the writing is to be performed is delayed until the writing is performed, and the definition and reference order of the data are reversed from the case of the sequential processing. There is no. Further, if there is no overlap, the overlap of the memory address areas is accurately determined so that the reading is not delayed. As a result, it is not necessary to determine whether or not pipeline processing is possible at the time of compilation, and the performance of pipeline processing can be sufficiently brought out.

The present invention is not limited to the above embodiment.
That is, although only one read address is set in the above embodiment, a plurality of read addresses may be set. Further, the number of stages of the operation pipeline may be different for each operation. In that case, it is possible to prepare by preparing the register file of the FIFO structure. Furthermore, the size of the data that is the unit of access is 2 for words and bytes.
Although limited to types, the present invention allows various access sizes such as 2-byte halfwords for 4-byte words. Similarly, in this embodiment, the case where the entire area of data for either reading or writing overlaps with the other area is taken as an example, but as shown in FIG. The present invention can be applied even in the case where only a part of each overlaps.

[Effects of the Invention] As described above, according to the present invention, the overlap of the word areas of the read and write data is accurately determined at the time of execution, and the order of data definition and reference is set in the order of the program statement. I can do it. As a result, pipeline processing can be executed for many operations that cannot accurately determine the overlap of data areas during compilation. And
At that time, the correctness of the execution result is guaranteed. Therefore,
It is not necessary to limit the programming language to the pipeline type computer. In addition, without creating a language processing system such as a huge compiler that incorporates complicated processing that attempts to accurately determine the definition and reference relationship of data,
Even if such a compiler is incorporated, the performance of pipeline processing can be sufficiently brought out. Furthermore, these effects can be realized with a simple configuration as shown in the embodiment.

[Brief description of drawings]

1 to 4 are diagrams for explaining a vector computer according to an embodiment of the present invention. FIG. 1 is a block diagram showing a main configuration, FIG. 2 is a block diagram showing an overall configuration, FIG. 3 is a diagram showing a structure of information stored in each register, FIG. 4 is a detailed block diagram of a comparator, and FIG. 5 is a diagram showing a manner of overlapping memory addresses inspected in another embodiment of the present invention. 6 and 7 are diagrams for explaining the conventional pipeline process, and FIGS. 8 to 12 are diagrams showing examples in which the conventional pipeline process cannot be executed. 11 ... Arithmetic processing unit, 12 ... Memory, 13 ... Pipeline control unit, 21 ... Write information register (W register), 22
...... Register file, 23 to 25 ...... Register, 26 ...... Read information register (R register), 27 to 29 ...... Comparator, 30,40,43 ...... AND gate, 31 to 38 ...... XOR gate,
41 …… NOR gate, 42 …… NAND gate.

Claims (1)

[Claims] 1. A memory that stores vector data and can be accessed in at least two ways in word units, halfword units, or byte units, and a pipeline having a predetermined number of stages by sequentially reading vector data from this memory. An arithmetic processing unit that performs vector arithmetic processing by processing and stores the arithmetic result in the memory, a write memory address of the arithmetic processing data held in each stage of the pipeline, and the arithmetic processing data In order to store the size indicating whether it is a word, a halfword, or a byte in correspondence with each stage of the pipeline, a register of the number of stages set corresponding to the number of stages of the pipeline. FIFO
A register file including a memory; a storage unit that stores the calculation result sequentially output from the calculation processing unit in a storage location of the memory designated by the write memory address sequentially read from the register file; When the unit reads the vector data from the memory, the memory of the memory is read based on the read memory address, the size of the data to be read, and the memory address and the size of the data stored in the register file. Inspection means for inspecting whether or not the write area and the read area specified by both memory addresses overlap each other, and prohibits the arithmetic processing unit from reading data from the memory when the overlap is detected by the inspection means. However, when the duplication is not detected, the arithmetic processing unit is allowed to read the data from the memory. Vector calculator, characterized by comprising a means for.