Method and compiler for parallel execution of a program

Claim 2

In a computer having a plurality of processors, a method for increasing the speed of program execution by decomposing loops in a source program onto the processors and having said processors execute them in parallel, said method comprising the steps of: (a) reading the source program; (b) specifying a loop to be executed in parallel in said source program; (c) determining data dependence vectors indicating true and anti dependences relatives to said loop being specified; (d) decomposing the iteration spaces of said loop and assigning the spaces to said plurality of processors; (e) determining the area of each iteration space assigned to said plurality of processors where data is required to be read from any other processor for parallel processing; (f) calculating communication vectors based on information on the area of said iteration space which has been determined that data is required to be read from any other processor, said vectors are the ones which indicate whether interprocessor communication exists or not for each loop; (g) calculating communication dependence vectors based on said data dependence vectors and said communication vectors, said dependence vectors are calculated by ANDing said communication vectors with said dependence vectors; (h) determining the manner of communication based on the values of said communication dependence vectors; and (i) generating codes for specifying communication and loop execution methods by detecting the method of communication between respective operands, based on said manner of communication being determined.

Claim 3

The method for parallel execution of a program according to claim 1, further comprising the step of sequentially applying steps (e) to (i) from outer to inner loops if said loop is a nested loop.

Claim 4

The method for parallel execution of a program according to claim 2, further comprising the step of removing such operand as can be prefetched from a target loop in said nested loop in response to the finding of the loop which can be prefetched and inserting a code outside said nested loop which specifies that the operand can be prefetched.

Claim 5

The method for parallel execution of a program according to claim 1 wherein said method of communication is either prefetch communication, pipeline sending, or pipeline receiving.

Claim 6

The method for parallel execution of a program according to claim 1 wherein said method of loop execution is either parallel operation, pipeline operation, or operation which cannot be made parallel.

Claim 7

The method for parallel execution of a program according to claim 1 wherein said source program includes the number of processors used and a statement for assigning the arrays in the loop to said processors.

Claim 8

The method for parallel execution of a program according to claim 1 wherein said AND operation is performed in accordance with a rule indicated by a truth table: + & 1=+ + & 0=0 0 & 1=0 0 & 0=0 - & 1=- - & 0=0 where +, - and 0 are values which the components of data dependence vectors can assume, and 1 and 0 are values which the components of communication vectors can assume.

Claim 9

In a computer having a plurality of processors, a compiler including a processing unit for increasing the speed of program execution by decomposing loops in a source program onto the processors and having said processors execute them in parallel, said compiler comprising: (a) means for reading the source program; (b) means for specifying a loop to be executed in parallel in said source program; (c) means for determining data dependence vectors indicating true and anti dependences relative to said loop being specified; (d) means for decomposing the iteration spaces of said loop and assigning the spaces to said plurality of processors; (e) means for determining the area of each iteration space assigned to said plurality of processors where data is required to be read from any other processor for parallel processing; (f) means for calculating communication vectors based on information on the area of said iteration space which has been determined that data is required to be read from any other processor, said vectors are the ones which indicate whether interprocessor communication exists or not for each loop; (g) means for calculating communication dependence vectors based on said data dependence vectors and said communication vectors, said dependence vectors are calculated by ANDing said communication vectors with said dependence vectors; (h) means for determining the manner of communication based on the values of said communication dependence vectors; and (i) means for generating codes for specifying communication and loop execution methods by detecting the method of communication between respective operands, based on said manner of communication being determined.

Claim 10

In a computer having a plurality of processors, a compiler including a processing unit for increasing the speed of program execution by decomposing loops in a source program onto the processors and having said processors execute them in parallel, said compiler comprising: (a) means for reading the source program; (b) means for specifying a loop to be executed in parallel in said source program; (c) means for determining data dependence vectors indicating true and anti dependences relative to said loop being specified; (d) means for decomposing the iteration spaces of said loop and assigning the spaces to said plurality of processors; (e) means for determining the area of each iteration space assigned to said plurality of processors where data is required to be read from any other processor for parallel processing; (f) means for calculating communication vectors based on information on the area of said iteration space which has been determined that data is required to be read from any other processor, said vectors are the ones which indicate whether interprocessor communication exists or not for each loop; (g) means for calculating communication dependence vectors based on said data dependence vectors and said communication vectors, said dependence vectors are calculated by ANDing said communication vectors with said dependence vectors; (h) means for determining the manner of communication based on the values of said communication dependence vectors; and (i) means for generating codes for specifying communication and loop execution methods by detecting the method of communication between respective operands, based on said manner of communication being determined.

Claim 11

The compiler according to claim 8, further comprising means for sequentially applying means (e) to (i) from outer to inner loops if said loop is a nested loop.

Claim 12

The compiler according to claim 8 wherein said method of communication is either prefetch communication, pipeline sending, or pipeline receiving.

Claim 13

The compiler according to claim 8 wherein said method of loop execution is either parallel operation, pipeline operation, or operation which cannot be made parallel.

Claim 14

The compiler according to claim 8 wherein said AND operation is performed in accordance with a rule indicated by a truth table: + & 1=+ + & 0=0 0 & 1=0 0 & 0=0 - & 1=- - & 0=0 where +, - and 0 are values which the components of data dependence vectors can assume, and 1 and 0 are values which the components of communication vectors can assume.

Claim 15

The compiler according to claim 8 wherein said source program includes the number of processors used and a statement for assigning the arrays in the loop to said processors.

Claim 16

The compiler according to claim 13 wherein said source program is a FORTRAN code.

Claim 17

The compiler according to claim 14 wherein said source program is a FORTRAN90 code.

Claim 18

The compiler according to claim 15 wherein said means for specifying a loop to be executed in parallel includes means for specifying array representations in the source program and TIF as loops.