Browse Prior Art Database

Primitive Set Operation for Program Parallelization

IP.com Disclosure Number: IPCOM000114615D
Original Publication Date: 1995-Jan-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 4 page(s) / 90K

Publishing Venue

IBM

Related People

Komatsu, H: AUTHOR [+2]

Abstract

Disclosed is a set of primitive set operations for array data access space and loop index iteration space for use of array reference and communication analysis. The operations include intersection, union, difference, cut and map for two sets of data or iteration space. By this method, programs can be analyzed efficiently for parallelizing on multi-processor computer systems.

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

Primitive Set Operation for Program Parallelization

      Disclosed is a set of primitive set operations for array data
access space and loop index iteration space for use of array
reference and communication analysis.  The operations include
intersection, union, difference, cut and map for two sets of data or
iteration space.  By this method, programs can be analyzed
efficiently for parallelizing on multi-processor computer systems.

      Let S = (S sub <1> , S sub <2> , ...S sub <n> ) denote data or
iteration space of rank n. The operations of intersection, union, and
difference for two sets S and T can be defined as follows.
  1.  Intersection: The product of two sets is given by the product
of
       all the dimension.
        S intersect T = (S sub <1> intersect T sub <1>, S sub <2>
         intersect T sub <2>, ..., S sub <n> intersect T sub <n>)
  2.  Difference: The difference of two sets is a list of sets which
       is obtained by the difference taken along one array dimension.
        S - T = List {(S sub <1> -T sub <1>, S sub <2>, .. S sub
<n>),
         (S sub <1>, S sub <2> -T sub <2>, .. S sub <n>), ..., (S sub
         <1>, .., S sub <n-1>, S sub <n> -T sub <n>)}
  3.  Union: The union of two sets is represented by difference as
       follows.
        S union T = List { (S - T), T}
      In the special case, when two sets S and T differ only in one
       dimension i, then the union of the two sets is given by the
union
       of that dimension.
        S union T = (S sub <1>, S sub <2>, ... S sub <i-1>, S sub <i>
         union T sub <i>, S sub <i+1>, .., S sub <n> )

          Fig. 1 shows the illustration of these three kind of
primitive set operations.  Data space and iteration space are closed
under these set operations, and these operation can be applied
iteratively.  When the result is represented as a list, each set of
the
list have to be applied in the subsequent set operations.

          Next, let DS = (DS sub <1>, DS sub <2>, .., DS sub <n>)
denote then mutually disjoint data sets, and EXP = (P1, P2, .. Pn)
denote the expression of shift or scaling operation.  The operation
of
cut and map can be defined as follows.
  4.  Cut: The cut of S by a disjoint set DS is the set of
       intersection of S and each section of DS.
        S / DS = (S intersect DS sub <1>, S intersect DS sub <2>,
         .. S intersect DS sub <n>)
  5.  Map: The map of S by the expression EXP is obtained by applying
       the given sh...