US 5,317,743 AGranted

System for compiling iterated loops based on the possibility of parallel execution

AssigneeKabushiki Kaisha Toshiba

InventorsToru Imai, Kenji Sirakawa

Life of this patent

Estimating the term…

Loading patent…

Abstract

A compiler apparatus in a computer converts source program to object program to be executed by the computer. If loop instructions are included in the object program, the resource reference extraction section extracts resources referred by the loop instructions and the resource change extraction section extracts resources changed by the loop instructions. The loop parallel decision section decides possibility of parallel execution for different stages of the loop instructions according to the extraction result. The code generation section generates object instructions which are parallely executed if the loop parallel decision section decides that the loop instructions can be parallely executed, generates object instructions which are not parallely executed if the loop parallel decision section decides that the loop instructions cannot be parallely executed, and generates object instructions which branches parallel execution instructions or non-parallel execution instructions according to condition to parallely execute at execution mode if the loop parallel decision section cannot decide whether the loop instructions can be parallely executed or not.

Claims10

Dependent claims

A loop compiler in a data processing system comprised of a plurality of processors, each capable of executing object programs, wherein the loop compiler compiles an object program consisting of a plurality of instructions to be executed by the data processing system, wherein a loop consists of a plurality of instructions to be executed a plurality of iterations by a one of the plurality of processors, the loop compiler comprising:

loop instructions extraction means for extracting a loop from the plurality of instructions;
resource reference extraction means for extracting resources read by at least one of the instructions in the extracted loop;
resource change extraction means for extracting resources changed by at least one of the instructions in the extracted loop;
loop parallel decision means for determining, in accordance with the extracted resources extracted by the resource reference extraction means and the resource change extraction means, whether it is impossible, possible or unknown if a first iteration and a second iteration of the loop can be parallely executed;
and
code generation means for generating, in accordance with the determination of the loop parallel decision means, object instructions, including at least one of a plurality of types of object instructions for the object program wherein the following types correspond, respectively, to the determination of possible, impossible or unknown
a first type wherein the object instructions are parallely executed by the plurality of processors,
a second type wherein the object instructions are executed by a one of the plurality of processors, and
a third type wherein the object instructions include branch parallel execution instructions, non-parallel execution instructions and parallel execution instructions, wherein the branch parallel execution instructions are used, during execution of the object program, to determine whether the non-parallel execution instructions are to be executed by a one of the parallel processors or the parallel execution instructions are to be executed by the plurality of processors.

6 more elements

In a data processing system including a plurality of microprocessors for parallel execution of a program including a plurality of object instructions, wherein loops consist of a plurality of the object instructions capable of being executed by one of the plurality of microprocessors a plurality of times, the method performed in the data processing system consisting of the steps:

identifying a loop in the program;
determining whether it is impossible, possible or unknown if a first iteration and a second iteration of the loop can be parallelly executed;
and
generating, in accordance with a possible or unknown determination, and adding to the program a plurality of new object instructions including a branch object instruction and parallel processing instructions, wherein the parallel processing instructions are comprised of at least one of the object instructions corresponding to the loop, and wherein the branch object instruction is used, during execution of the object program, to determine whether non-parallel execution instructions are to be executed by a one of the parallel microprocessors or the parallel processing instructions are to be executed by the plurality of microprocessors.

1 more element

Dependencies are inferred from the claim text.