JPH05127904A - Information processing device and code generation device - Google Patents

Abstract

(57) [Summary] [Purpose] Information processing that allows loops to be executed in parallel that does not know in advance which end condition will be satisfied when the determination of the end condition of the loop depends on the data being processed. (EN) An apparatus and a code generation apparatus for converting the above loop into an object code that can be executed by the information processing apparatus. [Configuration] Other than the instruction processing device that gives the priority to the instruction processing device that is executing the youngest iteration among the instruction processing devices that are executing in parallel and transfers data to the memory or detects the end condition at the end of the loop By limiting the interruption of the processing in the instruction processing device of the above to the instruction processing device having the above priority, even if any instruction processing device detects the end condition of the loop, overtaking of the process does not occur, The above-mentioned loop is executed in parallel while guaranteeing that the same operation as that of the above is executed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an information processing apparatus for shortening instruction execution time by issuing instructions of a plurality of instruction streams in parallel.

[0002]

2. Description of the Related Art In recent years, information processing apparatuses have been sought to speed up instruction execution by processing instructions in parallel. The architectural definition of the current general-purpose computer is implicitly
It includes the sequentiality of instruction execution. But many years ago,
Designers of high performance serial machines have recognized that executing instructions in parallel is useful for improving machine performance. The first attempt along this direction is instruction processing pipelining. In early pipelined machines, a logical interlock (e.g., the input information of the Nth instruction was generated by the execution of the N-1th instruction) was used to execute one instruction per cycle. It was operating at a performance considerably lower than the normal limit. This problem is R
Almost solved by the advent of the ISC processor. That is, in the RISC processor, the number of instructions executed in each cycle is almost one, which is nearing the limit of speeding up. The MIPS R2000 / 3000 is an example of a high performance pipelined RISC processor.
In order to further improve performance, it is no longer possible to rely solely on pipeline technology.

Therefore, the designer can take a measure to increase the number of arithmetic units and the like, which makes it possible to issue a plurality of instructions for each cycle. The price to pay for this performance increase is the addition of hardware, which not only adds more functional units, but also the control complexity to maintain the logical sequentiality of instruction execution required by the architecture. Increase is also included. The Intel 80960CA is the first commercial microprocessor to use such superscalar technology.

However, the performance is not always improved by incorporating a plurality of processing units and increasing the number of instructions to be executed in parallel. Considering an ordinary application, it is said that only a few processes can be executed in parallel due to the logical interlock. The possibility of parallel execution of instructions is naturally limited (for example, "Nikkei Electronics", No. 487, pages 191 to 200). This problem occurs because there is one instruction stream used at the instruction execution level and there is a dependency between instructions. Therefore, an information processing apparatus has been proposed which realizes high throughput by obtaining instructions to be issued in parallel from a plurality of instruction streams and increasing instruction level parallelism (for example, Japanese Patent Laid-Open No. 3-134882). Furthermore, as a method of speeding up the execution of a single program, a method of executing each iteration of the loop in parallel as different streams has been proposed.

The parallel execution of the above loop will be described below with reference to the drawings. FIG. 8 shows an example of a loop written in a high level programming language. Here, the variable i is called a control variable of the loop, and in this example, the loop is executed while the value of i is increased by one. Reference numeral 81 describes a loop end condition, and while the value of the variable i is less than 10000, the loop main body portion (hereinafter referred to as the loop body) indicated by the portion 82 is executed.
Further, FIG. 9 is an example of an information processing apparatus having a plurality of instruction processing units. In this example, the number of instruction processing units is four.
Reference numerals 91 to 94 each denote an instruction processing unit, which internally includes a program counter and a register that hold a context for interpreting and executing an instruction from an instruction stream. In order to execute the above loops in parallel by using this information processing apparatus, it is sufficient that four instruction processing units each execute one quarter of the loop. There are several methods for dividing the loop at this time.

For example, the instruction processing unit 91 uses i = 0, 4,
, 9996 executes the body of the loop, and the instruction processing unit 92 executes the body of the loop when i = 1, 5, ..., 9997, and so on. There is a way to split the loop by determining the initial value of and the increment. FIG. 10 shows an instruction executed by each instruction processing unit at this time. In the example, 101 is an instruction stream processed by the instruction processing unit 91, 102 is an instruction stream processed by the instruction processing unit 92, 103 is an instruction stream processed by the instruction processing unit 93, and 104 is an instruction stream processed by the instruction processing unit 94. is there. As described above, the processing time can be shortened by executing one loop in parallel by the plurality of instruction processing units.

[0007]

However, the parallel processing of the loop as described above depends on the data being processed in the judgment of the loop end condition, and the judgment of the loop end cannot be made independently in each stream. Not applicable in all cases. FIG. 4 is an example of such a loop. In this example, the value of the variable ptr is set in the previous execution of the loop, and the nth loop cannot be executed until the execution of the (n-1) th loop is completed. Further, since the end condition of the loop can be determined only by sequentially tracing the data of the list structure, when executed by a plurality of streams, only one stream can detect the end condition. Therefore, in the conventional parallel information processing apparatus, a loop as shown in FIG. 4 cannot perform parallel processing.

[0008]

[Means for Solving the Problems] First invention (Claim 1)
Information processing apparatus is a parallel information processing apparatus that simultaneously processes instructions from P (P is 2 or more) instruction streams, and an instruction processing unit that processes instructions of an n-th (1 ≦ n ≦ P) instruction stream. Therefore, it is characterized by having a queue for transferring data to the instruction processing unit that processes the instruction of the n + 1th instruction stream (however, the first instruction stream when n = P).

The information processing apparatus of the second invention (claim 2) is a parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams.
The context necessary for executing the processing of the nth instruction stream is copied from the instruction processing unit that processes the instruction stream of n ≦ P) to the other P−1 instruction processing units. , And has a context copy mechanism.

An information processing apparatus according to a third aspect of the present invention (claim 3) is a parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams.
(n ≦ P) The instruction processing unit for processing the instruction stream has a priority display mechanism indicating that it has priority over the other P−1 instruction processing units, and the priority display mechanism described above. Only when it is indicated that the instruction processing unit has the priority right, the priority processing unit corresponds to the instruction processing unit that processes the instruction of the n + 1th instruction stream (however, when n = P, the first instruction stream). If there is no priority right, the processing of the instruction processing unit is stopped until the priority right is obtained, and the priority right is given after the priority right is obtained.
It is characterized by having a conditional priority moving mechanism that moves to a priority display mechanism corresponding to an instruction processing unit that processes an instruction of an instruction stream of +1 (however, it is first when n = P).

An information processing apparatus according to a fourth invention (claim 4) is a parallel information processing apparatus which simultaneously processes instructions from P (P is 2 or more) instruction streams.
Only when the instruction processing unit for processing the instructions of the instruction stream of n ≦ P) is shown to have the priority by the priority display mechanism of the third invention, other P-1 instructions When the processing of the instruction stream being executed in the processing unit is interrupted and the priority is not granted, the processing of the instruction processing unit is stopped until the priority is obtained, and after the priority is obtained, another P- It is characterized by having a conditional instruction stream interruption mechanism for interrupting the processing of the instruction stream being executed by one instruction processing unit.

An information processing apparatus according to a fifth aspect of the present invention is a parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams.
(n ≦ P) The instruction processing unit for processing the instruction stream executes the data transfer to the memory only when it is indicated by the third invention priority display mechanism that the instruction processing unit has the priority. If you do not have the priority right, you should have a conditional data transfer mechanism that stops the processing of the above instruction processing unit until the priority right is obtained and executes data transfer to the memory after the priority right is obtained. It has a feature.

An information processing apparatus according to a sixth invention (claim 6) is a parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams. A context copy mechanism of the second invention, a priority display mechanism and a conditional priority transfer mechanism of the third invention,
It is characterized by having the conditional instruction stream interruption mechanism of the fourth invention and the conditional data transfer mechanism of the fifth invention.

A code generating apparatus according to a first aspect of the present invention (claim 7) is a code generating apparatus employed in a compiler for generating a target program by using a source program written in a high-level programming language as an input, and detecting a loop. Then
Each iteration of the loop is treated as a separate thread by the thread generator that generates the target program as an instruction string that is executed in parallel by multiple instruction processors, and the value of the variable set during the previous iteration during the loop. A dependency detection unit that detects the use during the current iterative execution, and a dependent variable detected by the dependency detection unit are received from the instruction processing unit that executes the previous iteration through the queue of the first invention. A dependent variable acceptance command generation unit that generates a command, and a dependence variable transmission command generation unit that generates a command to transmit a variable having a dependency detected by the dependence detection unit to the command processing unit that executes the next iteration through the queue. When one iteration is completed, the priority is moved to the instruction processing unit that executes the next iteration by using the priority moving mechanism of the third invention. Using the priority transfer instruction generating unit that generates an instruction and the instruction stream interruption mechanism shown in the fourth invention as an instruction executed when the loop end condition is satisfied and the execution of the loop iteration is ended. It is characterized by comprising a stream interruption instruction generation unit for generating an instruction for interrupting the execution of an instruction stream other than the instruction stream satisfying the above condition.

A code generating apparatus according to a second invention (claim 8) is the code generating apparatus according to the first invention, which is adopted in a compiler for generating a target program by inputting a source program written in a high-level programming language. Out-of-loop used variable detection part that detects that the value calculated in the execution of the last iteration is used after the end of the loop, with the value calculated in each execution of the loop. And a conditional data transfer instruction generating section for generating an instruction using the conditional data transfer mechanism of the fifth invention for transferring the variable detected by the section to the memory.

[0016]

According to the first aspect of the invention, the information processing apparatus transfers variables that are dependent on each iteration of the loop to the instruction processing unit that executes the next iteration via the queue. Also,
The information processing apparatus of the second invention copies the context required for parallel execution of the loop to another instruction processing unit by the context copy mechanism before starting the execution of the loop. In the information processing apparatus according to the third aspect of the present invention, first, the instruction processing unit that executes the first loop is given priority, and when the processing of the first iteration is completed, the priority is sequentially changed to the next priority. By moving to the instruction processing unit that is performing the iteration, the instruction processing unit that is always performing the youngest iteration among the respective iterations of the loops being executed in parallel has the priority.

The information processing apparatus according to the fourth aspect of the invention, when the instruction processing unit satisfies the loop termination condition, allows the instruction processing unit to interrupt the processing in another instruction processing unit, and further It is assumed that the interruption is completed after the instruction processing unit obtains the priority, so that the repeated execution satisfying the end condition is completed after all the younger executed executions are completed.

In the information processing apparatus of the fifth invention, when there is a variable used in the loop after the loop ends, the variable is transferred to the memory by waiting until the instruction processing unit gets the priority. Since the data is transferred to the memory, the data is transferred to the memory in order from the instruction processing unit that is performing the young iteration, and after the end of the loop, the data transferred in the last iteration is present in the memory.

A sixth aspect of the present invention is a parallel execution of a loop, such as that shown in FIG. 4, which cannot be executed in parallel by a conventional information processing apparatus, due to the combination of the constituent features of the first to fifth inventions. Will be done.

The code generation device of the first invention divides the loop into a plurality of streams to be executed in parallel, performs dependency detection of variables across the loops, generates transfer instructions between instruction processing units, and At the end of one iteration, an instruction to move the priority right to the instruction processing unit that is performing the next iteration is generated, and after the loop ends, the instruction processing unit that detects the loop end condition is another instruction. By generating the instruction for interrupting the processing of the processing unit, the object code executable by the information processing apparatus of the sixth invention is generated.

The code generating device of the second invention is the code generating device of the first invention.
In addition to the operation of the code generation device of the invention of claim 5, a variable that is used even after the end of the loop is detected in the variable set in the loop, and the conditional data of the fifth invention is used as a transfer instruction of the variable to the memory. An instruction that uses the transfer mechanism will be generated.

[0022]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the configuration of the information processing apparatus in the first embodiment of the present invention. In this embodiment, the description will be given assuming that the number of plural instruction processing units is four.

In FIG. 1, 1 to 4 are instruction processing units for simultaneously processing instructions from P (P is 2 or more) instruction streams, and 5 to 8 are nth (1≤n≤P) instructions. A queue for transferring data from an instruction processing unit that processes an instruction of a stream to an instruction processing unit that processes an instruction of an n + 1th instruction stream (however, 1 when n = P), 9 is an nth instruction From the instruction processing unit that processes the instruction of the instruction stream of (1 ≦ n ≦ P), the context necessary for executing the processing of the nth instruction stream is set to another P
-1 is a context copy mechanism for copying to one instruction processing unit.

10 to 13 are id registers corresponding to the respective instruction processing units, and 14 to 17 are instruction processing units for processing the instructions of the nth (1≤n≤P) instruction stream, and the other P-
A priority display mechanism indicating that one instruction processing unit has a priority right, and reference numerals 18 to 21 only when the instruction processing unit indicates that the instruction processing unit has a priority right. Then, the priority is moved to the priority display mechanism corresponding to the instruction processing unit that processes the instruction of the instruction stream of n + 1th (however, when n = P) instruction stream, and if there is no priority, The processing of the instruction processing unit is stopped until the priority is obtained, and after the priority is obtained, the priority is
This is a conditional priority moving mechanism that moves to the priority display mechanism corresponding to the instruction processing unit that processes the instruction of the n + 1th instruction stream (where n is the first instruction when n = P).

22 to 25 are the other P-1s only when the priority display mechanism indicates that they have priority.
If the instruction stream being executed by each instruction processing unit is interrupted and the user does not have the priority right, the processing of the instruction processing unit is stopped until the priority right is obtained, and after the priority right is obtained, Conditional instruction stream interruption mechanism for interrupting the processing of the instruction stream being executed by P-1 instruction processing units, and 26 to 29 are instruction processing for processing instructions of the nth (1 ≦ n ≦ P) instruction stream Part performs data transfer to the memory only when the priority display mechanism indicates that it has the priority, and if it does not have the priority, the above instruction processing is performed until the priority is obtained. This is a conditional data transfer mechanism that stops the processing of the unit and executes the data transfer to the memory after the priority is obtained.

The instruction processing units 1 to 4 can decode and execute the instructions from the independent instruction streams. Each instruction processing unit includes a program counter and a register for holding the context of the program being executed. Queues 5 to 8 are located between the instruction processing units, and, for example,
The instruction processing unit 2 can read the data written in the queue 5 by the instruction processing unit 1 from the queue 5. The queues 5 to 8 each have a ready flag indicating that the data is already stored therein, and the instruction processing unit that attempts to read the data from the empty queue interlocks until the data is written in the queue.

The context copy mechanism 9 copies context information such as a program counter and a register provided in a certain instruction processing unit to a program counter and a register in another instruction processing unit. At this time, an id for distinguishing the copy source instruction processing unit and the copy destination instruction processing unit is set in the id registers corresponding to the instruction processing units 10 to 13. The priority display mechanism indicates which of the four instruction processing units has the priority. The conditional priority moving mechanisms 18 to 21 move the priority to the priority display mechanism corresponding to the adjacent instruction processing unit when the instruction processing unit having the priority gives an instruction to move the priority. .. If the instruction processing unit that does not have priority issues an instruction to move the priority, the processing of the instruction processing unit is interlocked until the priority is obtained, and the process is restarted when the priority is obtained. Then, the priority is transferred.

The conditional instruction stream interruption mechanisms 22 to 25 immediately interrupt the processing being executed by another instruction processing unit when the instruction processing unit having the priority gives an instruction to interrupt the instruction processing. Let If an instruction processing unit that does not have priority orders to suspend instruction processing, the processing of that instruction processing unit is interlocked until the priority is obtained, and the process is restarted when the priority is obtained. , The processing in other instruction processing units is interrupted. The conditional data transfer mechanisms 26 to 29 execute the data transfer to the memory when the instruction processing unit having the priority has instructed the data transfer. If an instruction processing unit that does not have priority orders data transfer, the processing of that instruction processing unit is interlocked until the priority is obtained, and when the priority is obtained, the process is restarted and the memory is restarted. Data transfer to.

FIG. 4 shows a loop executed in parallel in the information processing apparatus of this embodiment in a high-level language, and FIG. 5 shows object code actually executed. The conversion from the high-level language shown in FIG. 4 to the object code shown in FIG. 5 will be described in detail when the second embodiment is described. Here, the operation of the first embodiment will be described with reference to FIG.

Until the processing of the loop is started, the object code is sequentially executed by any of the instruction processing units. Here, for the sake of explanation, it is assumed that the processing is executed by the instruction processing unit 1. When the processing of the loop is started, the instruction processing unit 1 repeats the 1st, 5th, ... th iteration, the instruction processing unit 2 repeats the 2,6, ... th iteration, the instruction processing unit 3 repeats the 3,7, ... th iteration. , The instruction processing unit 4, 4, 8, ...
The second iteration is executed. First, the instruction processing unit 1 executes the load instruction 51, and the value of the variable ptr is initialized. Next, at 52, qi of a part of one instruction stream
When the nit instruction is executed, all queues are initialized and the contents become empty. Next, by executing the fork instruction, the context of the instruction processing unit 1 is copied to another instruction processing unit by using the context copy mechanism 9. Further, different values are set in the id registers 10 to 13 in order to distinguish the copy source and copy destination instruction processing units.

In this embodiment, i of the instruction processing unit of the copy source is
In the d register 10, 0 is the id of the copy destination instruction processing unit.
A value other than 0 is set in the registers 11 to 13. At the same time, the priority is set in the priority display mechanism 14 corresponding to the instruction processing unit 1. The instruction processing unit 1 performs the processing based on the initial value instead of fetching the value from the queue 8 and processing it only when executing the first iteration. Therefore, the instruction of the portion 53 is executed to label Lstart. Branch off. Here, the getid instruction is an instruction for fetching a value from the id register corresponding to each instruction processing unit and setting it in the register. The other instruction processing unit executes the instruction of 54 without branching because the content of the id register is not 0. The instruction 54 is an instruction for each instruction processing unit to take a value from the corresponding queue, add an offset and load the value into a register, and a new value of the variable ptr is set in the register. If the value is not yet written in the queue, the instruction execution is interrupted at that point and the value is written in the queue. The instruction processing unit 1 executing the first loop and the instruction processing unit that has been able to read the value from the queue execute the instruction 55 and check whether the loop termination condition is satisfied.
The instruction processing unit 1 executing the first loop executes the instruction 5
It is checked whether the initial value set in 1 satisfies the end condition of the loop, and the other instruction processing unit checks whether the value loaded in the register by the execution of the instruction 54 satisfies the end condition. If there is an instruction processing unit that has detected a value satisfying the end condition, the instruction processing unit branches to the label Lexit. If the end condition is not satisfied, each instruction processing unit does not branch and
Execute instruction 56 to write the new value of the dependent variable ptr to the queue. The instruction processing unit waiting for the data to be written in the queue restarts the processing by this writing. For example, if the instruction processing unit 2 is stopped at the time of fetching data from the queue 5, the instruction processing unit 1 writes the data to the queue 5, whereby the processing of the instruction processing unit 2 is restarted and the instruction processing unit 1 writes the data. However, the data will be retrieved.

Next, each instruction processing unit executes the instruction 57 in the body of the loop. The command processing unit that has finished processing the command 57 executes the command 58 for priority transfer. By executing this instruction, each time the loop is executed once, the priority is transferred to the instruction processing unit executing the next iteration. Next, each instruction processing unit executes the instruction 59 and branches to the label Loop. After that, including the instruction processing unit 1,
All instruction processing units repeat the above processing in parallel.

The state of execution at this time is shown in FIG. Since the dependent variable ptr is transferred through the queue to the instruction processing unit that executes the next iteration at an early stage of each iteration, the execution of the body portion of the loop can be performed in parallel. The instruction processing unit that detects the end condition of the loop and branches to the label Lexit executes the instruction 510 to interrupt the processing of the instruction stream being executed by another instruction processing unit, and the subsequent execution is performed again sequentially. To do. This state is shown in FIG. Here, the priority is used to guarantee that the instruction processing unit that detects the loop end condition at the time when the processing of the loop ends does not overtake the processing of the instruction processing unit executing the previous iteration. It This will be explained below.

It is assumed that the instruction processing unit 3 now detects the loop end condition and branches to the label Lexit. The instruction processing unit 3 executes the instruction 510 and tries to interrupt the execution of the other instruction processing units. Conditional instruction stream interruption mechanism 5
3 waits until the instruction processing unit 3 has the priority right, and after obtaining the priority right, interrupts the processing of the instructions of the other instruction processing units. At the time when the instruction processing unit 3 executes the instruction 510, the instruction processing unit 2 has a younger priority even if it is still executing the previous iteration of the iteration in which the instruction processing unit 3 detected the end condition. The instruction processing unit that is executing the iteration is passed to the instruction processing unit that executes the next iteration when the execution of the iteration is completed. Therefore, the instruction processing unit 3 is executed until the processing of the instruction processing unit 2 is completed. Have no priority. Therefore, when the instruction processing unit 3 obtains the priority, it is guaranteed that the execution of the iteration before the iteration in which the termination condition is detected by the instruction processing unit 3 is finished. Since the transfer of priority itself is also moved by the conditional priority transfer mechanism,
Only one priority will move sequentially through the instruction processor as each iteration of the loop ends.

Next, the function of the conditional data transfer mechanism will be described. If the value of the variable tmp is used after the loop ends in the loop shown in FIG. 4, the value of the variable tmp after the end of the loop is the value of the variable tmp calculated in the iteration immediately before the iteration that satisfies the loop end condition. Must be. Therefore, if an instruction using a conditional data transfer mechanism is used to write the value of the variable tmp back to the memory, the instruction processing unit having priority will transfer the data to the memory. Similar to the description of the interruption processing of (1), the data transferred to the memory is due to the execution of the final iteration.

As described above, according to this embodiment, the nth (1
From the instruction processing unit that processes the instruction of the instruction stream of ≦ n ≦ 4, the same applies hereinafter, n + 1 (1 when n = P)
No., the same shall apply hereinafter) to the instruction processing unit for processing the instructions of the instruction stream, and the queue for transferring the data and the instruction processing unit for processing the instructions of the nth instruction stream, The context copy mechanism that copies the context necessary for executing the processing to the other three instruction processing units and the instruction processing unit that processes the instruction of the nth instruction stream are the other three. To the instruction processing unit of FIG. 2 only if the priority display mechanism indicating that the instruction processing unit has priority and the instruction processing unit indicates that the instruction processing unit has priority. To the priority display mechanism corresponding to the instruction processing unit that processes the instruction of the n + 1th instruction stream, and if it does not have the priority, the processing of the instruction processing unit is stopped until the priority is obtained, priority n + its priority from been obtained
The conditional priority moving mechanism that moves to the priority display mechanism corresponding to the instruction processing unit that processes the instruction stream of the first instruction stream, and the instruction processing unit that processes the instruction of the nth instruction stream are Only when the display mechanism indicates that it has the priority, the processing of the instruction stream being executed by the other three instruction processing units is interrupted, and when the priority is not given, the priority is changed. A conditional instruction stream interruption mechanism for stopping the processing of the instruction processing unit until it is obtained, and interrupting the processing of the instruction stream being executed by the other three instruction processing units after the priority is obtained; When the instruction processing unit that processes the instruction stream of the instruction executes the data transfer to the memory and does not have the priority, only when the priority display mechanism indicates that the instruction processing unit has the priority. Is preferred By executing the conditional data transfer mechanism that suspends the processing of the instruction processing unit until the priority is obtained and executes the data transfer to the memory after the priority is obtained, the loop can be executed in parallel and executed. The speed can be improved.

In this embodiment, the case where each instruction processing device is physically plural is described.
It may be configured by an information processing device that processes instructions of a plurality of instruction streams in parallel by a plurality of logical instruction processing devices as disclosed in Japanese Patent No. 882. Next, a code generation device according to a second embodiment of the present invention will be described with reference to the drawings. FIG. 6 is a block diagram of a code generation device of a compiler according to the second exemplary embodiment of the present invention. This code generation device includes a thread generation unit 61, a dependency detection unit 62, a dependent variable acceptance instruction generation unit 63, and a dependency The variable transmission command generation unit 64, the priority transfer command generation unit 65, and the stream interruption command generation unit 66 are configured. The thread generation unit 61 detects a loop, and generates each object program as an instruction string that is executed in parallel by a plurality of instruction processing units as a separate thread for each iteration of the loop. The dependency detection unit 62 detects that the value of the variable set during the previous repeated execution is being used during the loop during the current repeated execution. The loop break detection unit 63 detects that there is an instruction to jump out of the loop according to the value of the variable set during the repeated execution. The dependent variable acceptance instruction generator 63 generates an instruction to receive the dependent variable detected by the dependency detector 62 from the instruction processor that executes the previous iteration through the queue described in the first embodiment. The dependent variable sending command generating unit 64 generates a command for sending the dependent variable detected by the dependency detecting unit 62 to the command processing unit executing the next iteration through the queue.

The priority transfer instruction generation unit 65 uses the priority transfer mechanism described in the first embodiment at the end of one iteration to give priority to the instruction processing unit that executes the next iteration. Generate a move instruction. The stream interruption instruction generation unit 66 determines whether the first instruction is executed when the loop end condition is satisfied and the loop execution is ended.
Using the instruction stream interruption mechanism shown in the embodiment, an instruction for interrupting the execution of an instruction stream other than the instruction stream satisfying the loop end condition is generated.

FIG. 4 describes a loop processed by the code generation device of this embodiment in a high-level language. FIG. 5 shows the object code generated by the code generation device of this embodiment for this loop. The operation of the code generator will be described below based on this loop. When the thread generation unit 61 detects a loop, the loop and the queue are initialized in order to execute the loops in parallel in the plurality of instruction processing units, and a context copy for starting the execution in another instruction processing unit is generated. Instructions 51 and 52 to be executed are generated. Further, the instruction 53 required only for the first iteration of the loop is generated. The dependent variable acceptance instruction generation unit 63 generates an instruction 54 for taking out the variable ptr detected by the dependent variable detection unit 62 from the queue and storing it in a register. In addition, the dependent variable transmission instruction generation unit 64 generates the instruction 56 for writing the new value of the variable ptr in the queue. The priority move instruction generation unit 65 generates a priority move instruction 58 after the instruction string 57 of the body of the loop. Also, the stream interruption instruction generation unit 66
Generates a stream interruption instruction 510 at the beginning of the instruction executed after the loop ends.

As described above, according to this embodiment, the code generation device detects a loop, and each iteration of the loop is treated as a separate thread and the target program is stored as an instruction string to be executed in parallel by a plurality of instruction processing units. A thread generation unit that generates a thread, a dependency detection unit that detects that the value of the variable set during the previous iteration of the loop is being used during the current iteration, and the dependency detection unit that detects the dependency Through the queue described in the first embodiment, the dependent variables are generated by the dependent variable acceptance instruction generation unit that generates an instruction to be received from the instruction processing unit that executes the previous iteration, and there is the dependency detected by the dependency detection unit. A dependent variable sending command generation unit that generates a command to send a variable to the command processing unit that executes the next iteration through the queue, and at the end of one iteration The priority transfer instruction generating unit that generates an instruction to transfer the priority to the instruction processing unit that executes the next iteration using the priority transfer mechanism described in the first embodiment; Using the instruction stream interruption mechanism shown in the first embodiment as an instruction to be executed when execution is terminated, a stream interruption for generating an instruction for interrupting execution of an instruction stream other than the instruction stream satisfying the loop end condition By providing the instruction generation unit, the information processing apparatus according to the first embodiment can generate the object code of the loop that can be executed in parallel.

A code generator according to the third embodiment of the present invention will be described below with reference to the drawings. FIG. 7 is a block diagram of a code generation device of a compiler according to the third embodiment of the present invention. This code generation device includes a thread generation unit 61, a dependency detection unit 62, and a loop break detection unit 63.
, A dependent variable acceptance command generation unit 63, a dependent variable transmission command generation unit 64, a priority transfer command generation unit 65, a stream interruption command generation unit 66, and a variable used outside loop detection unit 71.
And a conditional data transfer instruction generator 72. The out-of-loop use variable detection unit 71 detects that the value calculated in the execution of each iteration of the loop is the value calculated in the execution of the final iteration that is used after the end of the loop. The conditional data transfer instruction generation unit 72
An instruction is generated that uses the conditional data transfer mechanism described in the first embodiment to transfer the variable detected by the out-of-loop use variable detection unit 71 to the memory.

The operation of this embodiment will be described with reference to FIG. The outside-loop use variable detection unit 71 detects that the variable tmp in FIG. 4 is used after the end of the loop, and stores the detected variable tmp in the memory as an instruction using the conditional data transfer mechanism. The transfer command generation unit 72 generates the transfer command. As described above, according to the present embodiment, a thread that detects a loop in the code generation device and generates the target program as an instruction sequence that is executed in parallel by a plurality of instruction processing units as each thread of each iteration of the loop. There is a generation unit, a dependency detection unit that detects that the value of the variable set during the previous iteration is being used during the current iteration, and a dependency detected by the dependency detection unit. A dependent variable acceptance instruction generator that generates an instruction to receive a variable from an instruction processor that executes the previous iteration through the queue described in the first embodiment;
A dependent variable sending command generation unit for generating a command for sending the dependent variable detected by the dependence detection unit to the command processing unit executing the next iteration through the queue;
A priority move instruction generation unit that generates an instruction to move the priority to an instruction processing unit that executes the next iteration by using the priority movement mechanism described in the first embodiment at the end of the repetition of the number of times; Execution of an instruction stream other than the instruction stream satisfying the loop end condition by using the instruction stream interruption mechanism shown in the first embodiment as the instruction executed when the loop end condition is satisfied and the execution of the loop iteration is ended. Detects that the value calculated in the execution of each iteration of the loop is used after the end of the loop, with the stream interruption instruction generator that generates the instruction to interrupt An instruction to use the variable outside the loop detection unit and the conditional data transfer mechanism described in the first embodiment for transferring the variable detected by the variable outside the loop detection unit to the memory. By providing a conditional data transfer instruction generator that generates, in the information processing apparatus according to the first embodiment, it is possible to generate an object code executable loop in parallel.

[0043]

As described above, according to the present invention, an instruction for processing each iteration of a dependent variable for a loop that cannot be executed in parallel by a conventional parallel information processing apparatus because the loop end condition depends on data. Execution of the instruction processing unit that transfers using the queue provided between the processing units and that executes the iteration that satisfies the end condition using the priority is executed by another instruction processing that is still executing the iteration. By providing an information processing apparatus that enables parallel execution of generated object code by guaranteeing that it does not overtake the processing of a unit, and a code generation apparatus that generates parallel executable object code, The range of types of loops that can be executed can be expanded, and this can greatly contribute to the improvement of program execution efficiency.

[Brief description of drawings]

FIG. 1 is a block diagram of an information processing apparatus according to a first embodiment of the present invention.

[Fig. 2] Schematic diagram of executing a loop

[Fig. 3] Schematic diagram at the end of the loop

FIG. 4 is a diagram showing a program in which a loop is written in a high level language.

FIG. 5 is a diagram showing an object code obtained by processing the loop of FIG. 4 by the code generation device shown in the second embodiment of the present invention.

FIG. 6 is a block diagram of a code generation device according to a second exemplary embodiment of the present invention.

FIG. 7 is a block diagram of a code generation device according to a third embodiment of the present invention.

FIG. 8 is a diagram showing an example of a loop written in a high-level programming language.

FIG. 9 is a block diagram showing an example of an information processing apparatus having a plurality of instruction processing units.

10 is a diagram showing an instruction stream when the loop of FIG. 8 is executed by the information processing apparatus of FIG.

[Explanation of symbols]

 1 to 4 instruction processing unit 5 to 8 queue 9 context copy mechanism 10 to 13 id register 14 to 17 priority display mechanism 18 to 21 conditional priority moving mechanism 22 to 25 conditional instruction stream interruption mechanism 26 to 29 conditional Data transfer mechanism 51 Initialization instruction 52 Multi-threaded instruction group 53 Copy source determination instruction group 54 Instruction for fetching data from queue 55 End condition determination instruction group 56 Instruction for writing data to queue 57 Loop body 58 Priority move instruction 59 Jump Instruction 510 Interruption instruction 61 Thread generation unit 62 Dependence detection unit 63 Dependent variable acceptance instruction generation unit 64 Dependent variable transmission instruction generation unit 65 Priority transfer instruction generation unit 66 Stream interruption instruction generation unit 71 Loop outside used variable detection unit 72 Conditional data Transfer command generation part 81 Termination of loop 82 loop body 91-94 instruction processing unit 101 instruction stream processed by instruction processing unit 91 instruction stream processed by instruction processing unit 92 103 instruction stream processed by instruction processing unit 93 104 processed by instruction processing unit 94 Instruction stream

Claims (8)

[Claims] 1. A parallel information processing apparatus for simultaneously processing instructions from P (where P is 2 or more) instruction streams,
From the instruction processing unit that processes the instruction of the nth (1 ≦ n ≦ P) instruction stream, the n + 1th instruction (1 when n = P
An information processing device having a queue for transferring data to an instruction processing unit for processing an instruction of the instruction stream No.). 2. A parallel information processing apparatus for simultaneously processing instructions from P (where P is 2 or more) instruction streams,
From the instruction processing unit that processes the instruction of the n-th (1 ≦ n ≦ P) instruction stream, the context necessary to execute the processing of the n-th instruction stream is set to the other P−1 instruction processing units. An information processing device having a context copy mechanism for copying to and from. 3. A parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams,
an instruction processing unit that processes an instruction of an n-th (1 ≦ n ≦ P) instruction stream has a priority display mechanism that indicates that it has priority over the other P−1 instruction processing units; Only when the instruction display unit indicates that the instruction processing unit has the priority right, the instruction is processed in the instruction stream of the n + 1th instruction stream (however, when n = P, the first instruction stream). Move to the priority display mechanism corresponding to the instruction processing unit, if you do not have the priority right, stop the processing of the above instruction processing unit until the priority right is obtained, and after the priority right is obtained, change the priority right. Information processing characterized by having a conditional priority transfer mechanism that moves to a priority display mechanism corresponding to an instruction processing unit that processes an instruction of an n + 1th instruction stream (however, 1 when n = P) apparatus. 4. A parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams,
Only when the instruction processing unit that processes the instruction of the n-th (1 ≦ n ≦ P) instruction stream is indicated as having the priority by the priority display mechanism according to claim 3, another P −
When the processing of the instruction stream being executed by one instruction processing unit is interrupted and the priority is not granted, the processing of the instruction processing unit is stopped until the priority is obtained, and then the priority is obtained. An information processing apparatus having a conditional instruction stream interruption mechanism for interrupting the processing of an instruction stream being executed by other P-1 instruction processing units. 5. A parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams,
Only when the instruction processing unit for processing the instruction of the n-th (1 ≦ n ≦ P) instruction stream is shown to have the priority by the priority display mechanism according to claim 3, If you perform a data transfer and do not have priority,
An information processing apparatus having a conditional data transfer mechanism that suspends the processing of the instruction processing unit until the priority is obtained and executes the data transfer to the memory after the priority is obtained. 6. A parallel information processing apparatus for simultaneously processing instructions from P (P is 2 or more) instruction streams,
The queue described in claim 1, the context copy mechanism described in claim 2, the priority display mechanism and the conditional priority transfer mechanism described in claim 3, and the conditional instruction stream interruption mechanism described in claim 4. An information processing apparatus having the conditional data transfer mechanism according to claim 5. 7. A code generator used in a compiler that generates a target program using a source program written in a high-level programming language as an input, wherein a loop is detected and each iteration of the loop is divided into a plurality of separate threads. The thread generation unit that generates the target program as an instruction string that is executed in parallel in the instruction processing unit and the value of the variable that was set during the previous iteration during the loop are used during the current iteration. And a dependency variable acceptance instruction generator that generates an instruction to receive a variable having a dependency detected by the dependency detector from the instruction processor that executes the previous iteration through the queue according to claim 1. An instruction for executing the next iteration through the queue according to claim 1 for a variable having a dependency detected by the dependency detector. A priority variable is given to a dependent variable transmission command generation unit that generates a command to be transmitted to the processing unit, and an instruction processing unit that executes the next iteration by using the priority moving mechanism according to claim 3 when one iteration is completed. A priority movement instruction generation unit for generating an instruction for moving a loop, and an instruction stream interruption mechanism according to claim 4 as an instruction to be executed when a loop end condition is satisfied and execution of loop iteration is completed, A code generation device including a stream interruption instruction generation unit that generates an instruction for interrupting execution of an instruction stream other than an instruction stream that satisfies an end condition. 8. A code generator used in a compiler that generates a target program using a source program written in a high-level programming language as an input, the value being calculated in each iteration of a loop, and the final iteration. 6. An out-of-loop use variable detection unit that detects that the value calculated by the execution of [1] is used after the end of the loop, and a variable detected by the outside-loop use variable detection unit is transferred to a memory. 8. The code generation device according to claim 7, further comprising a conditional data transfer instruction generation unit that generates an instruction using the conditional data transfer mechanism of.