US 5,852,734 AGranted

Method and compiler for parallel execution of a program

AssigneeInternational Business Machines Corporation

InventorsHideaki Komatsu, Kazuaki Ishizaki, Osamu Gohda

Life of this patent

Estimating the term…

Loading patent…

Abstract

To increase the speed of program execution by decomposing a loop onto a plurality of processors and executing them in parallel. First, a loop in a source program is located which is to be executed in parallel. This loop is then analyzed for data dependence. The result of the analysis is used for calculating data dependence vectors. Then all areas of the index executed in the loop are decomposed and assigned to a number of processors. Further, it is determined whether data needs to be transferred between processors. Based on the array index space, communication vectors are calculated. Data dependence vectors and communication vectors are ANDed to calculate communication dependence vectors. Then, the manner of communication of operands and loop execution are determined based on the values of communication dependence vectors.

Claims16

Dependent claims

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.

7 more elements

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.

7 more elements

Dependencies are inferred from the claim text.