Method of reducing unnecessary barrier instructions

Details Method of reducing unnecessary barrier instructions Method of reducing unnecessary barrier instructions

1999-03-11

2001-09-18

Powell, Mark R. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C709S241000, C709S241000, C709S241000

Reexamination Certificate

active

06292939

ABSTRACT:

FIELD OF THE INVENTION
The present invention generally relates to a method of reducing unnecessary barrier instructions and, more particularly, to a method of reducing unnecessary barrier instructions affecting the execution performance of parallel processing of an object program in a multiprocessor system.
BACKGROUND OF THE INVENTION
A general barrier instruction issuing condition in a multiprocessor system occurs when a dependency between a certain data reference and a following data reference or the dependency relationship is unclear. If the presence or absence of this data dependency cannot be determined except at the time of instruction execution, or the dependency analysis of a compiler is disabled, barrier instructions are output for execution in the parallel processing object program.
Conventional methods for reducing unnecessary barrier instructions are known. In one example, a barrier instruction reduction directive statement for a compiler is inserted with a user directive statement or a data dependency cancellation directive statement is inserted in the source program.
FIG. 3
shows an example of a source program in which a directive statement for reducing unnecessary barrier instructions is inserted. This source program is written in an implementation of FORTRAN that is extended for paralleling capability. A description of an example of the source program is as follows.
The source program shown in the example of
FIG. 3
includes a DO loop
31
for iterative execution of processing by substituting the values i=1 to n sequentially into an array indicated by a(i). If an overlap between the reference range of array “a” in the DO loop
31
and the reference range of a following array
33
cannot be determined at the time of compilation and therefore can be determined only at the time of instruction execution, a barrier instruction reducing directive statement
32
for the compiler needs to be inserted by the user with a user directive statement. It should be noted that this directive statement
32
may be a data dependency cancellation directive statement. It should also be noted that “POPOPTION” is a directive statement indicating that the user provides a directive for paralleling a portion of the program that cannot be automatically put in parallel processing form by a parallel processing capability implemented by a FORTRAN processing system.
SUMMARY OF THE INVENTION
Generally, the execution of a barrier instruction causes overhead. The execution performance of the processing system is decreased by the amount of execution of unnecessary barrier instructions. The above-mentioned prior art is intended to reduce the number of unnecessary barrier instructions to prevent an associated decrease in execution performance of the processing system. However, the conventional methods are not suitable for removing all of the unnecessary barrier instructions unless the user knows very well the way in which the parallel program will execute. Thus, a problem arises in that it is difficult to remove all of the unnecessary barrier instructions.
It is therefore an object of the present invention to provide a method of reducing unnecessary barrier instructions by which unnecessary barrier instructions are dynamically reduced without user (human) intervention, thereby enhancing the execution performance of the object code or module.
According to one aspect of the invention, unnecessary barrier instructions are reduced in a compiler for generating a parallel processing object program from a source program, wherein the compiler converts the source program into parallel processing objects (parallel processing execution divisions), which are units or blocks of code for parallel processing, and preferably issues immediately before a parallel processing execution division, a pre dynamic barrier instruction having information in parameters used for determining the necessity for a barrier. Further, preferably the compiler issues a post dynamic barrier instruction immediately before a reference position, which is a point in the source code or object code before each variable or array reference (or group of array references) to be referenced after a parallel processing loop in the parallel processing execution division. The post dynamic barrier instruction has information in parameters thereof for determining the necessity for a barrier. Further, according to the invention, the parallel processing object program is preferably implemented by a hardware system for determining the presence or absence of data dependency, thereby dynamically reducing unnecessary barrier instructions based on the parameters of the pre dynamic barrier instruction and the post dynamic barrier instruction.
The above-mentioned object is also achieved by a compiler that generates, in converting the source program into the parallel processing object program or module, an instruction inserted before a parallel processing execution division having a parameter(s) with information used for determining the necessity for a barrier and an instruction inserted after the parallel processing execution division having a parameter(s) with information used for determining the necessity of a barrier before a variable or an array reference to be referenced after the parallel processing execution division. Further, the compiler determines the presence or absence of data dependency based on these parameters to dynamically switch between execution and nonexecution of a barrier instruction.
The above-mentioned object is also achieved, according to an embodiment of the invention, by a device that executes parallel processing of object code including dynamically determining the necessity for a barrier operation by checking whether any of the following barrier instruction deletable conditions (1) through (3) are met by processing a parameter(s) with hardware, wherein a compiler generates a sequence of instructions to be used in making the determination or is provided with means for generating a code for switching between execution or nonexecution of a barrier instruction by a branch instruction that uses the barrier instruction deletable conditions (1) and (2) as a decision equation.
The barrier instruction deletable conditions are as follows:
(1) Between PEs (Processor Elements), no dependency exists between a variable reference or an array reference to be referenced and a following reference;
(2) Between PEs, a dependency exists between a variable reference or an array reference to be referenced and a following reference but this dependency is only within the same PEs and no dependency exists between different PEs; and
(3) In hardware, memory coherence processing has been completed at a memory location at which a dependent relation occurs between PEs.


REFERENCES:
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5778423 (1998-07-01), Sites et al.
patent: 5781775 (1998-07-01), Ueno
patent: 5802374 (1998-09-01), Gupta et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 6016505 (2000-01-01), Badovinatz et al.
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6098089 (2000-08-01), O'Connor et al.
patent: 6216174 (2001-04-01), Scott et al.
Title: Eliminating redundant barrier synchronizations in rule-based programs, Anurag Acharya, ACM, 1996.*
Title: A simulation of dynamic task allocation in a distributed computer system, Ed Andert, ACM, 1987.*
Title: Semantics of barriers in a non-strict, implicitly-parallel language, Aditya et al, ACM, 1995.*
Title: Compiler optimizations for eliminating barrier synchronization, Chau-Wen Tseng; ACM, 1995.*
Title: Distributed shared memory system with improved barrier synchronization and data transfer, Tzeng, ACM, 1997.

Affiliated with

Also associated with

Rating

Method of reducing unnecessary barrier instructions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of reducing unnecessary barrier instructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of reducing unnecessary barrier instructions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2514339