Browse Prior Art Database

Efficient Execution of Reduction Operation for Parallel Computing Systems

IP.com Disclosure Number: IPCOM000115389D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 63K

Publishing Venue

IBM

Related People

Komatsu, H: AUTHOR [+2]

Abstract

Disclosed is an effcient execution method of reduction operation on multi-processor computing systems. In this method, the execution constraint pattern on each of participating processors is analyzed, and the communication is generated in an efficient manner based on the analysis. As a result the reduction operation can be executed faster than in the case by conventional method.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 57% of the total text.

Efficient Execution of Reduction Operation for Parallel Computing
Systems

      Disclosed is an effcient execution method of reduction
operation on multi-processor computing systems.  In this method, the
execution constraint pattern on each of participating processors is
analyzed, and the communication is generated in an efficient manner
based on the analysis.  As a result the reduction operation can be
executed faster than in the case by conventional method.

      In the conventional method, a reduction loop in a program is
transformed into a runtime library call.  The runtime function
computes the local reduction result on each of the processor, and
then combines them to get the final result, which necessarily entails
the synchronization among processors.

      In the new method, the reduction loops are not automatically
transformed into library calls.  Rather an execution constraint loop
is searched by the following algorithm after loop parallelization in
the compiler optimization phase.
  1.  Starting from a reduction loop, traverse the program backward
       along the control flow.
  2.  When find a loop, if it is:
      a.  do-parallel loop or do-serial loop, then traverse backward
           further along the control flow and go to 2.
      b.  do-pipeline loop then return the loop.
  3.  When the beginning of the program is reached, return
       no-constraint.  If an execution constraint loop is found in
t...