US 5,475,842 AGranted

Method of compilation optimization using an N-dimensional template for relocated and replicated alignment of arrays in data-parallel programs for reduced data communication during execution

AssigneeXerox Corporation

InventorsJohn R. Gilbert, Siddhartha Chatterjee, Robert S. Schreiber

Life of this patent

Estimating the term…

Loading patent…

Abstract

When a data-parallel language like Fortran 90 is compiled for a distributed-memory machine, aggregate data objects (such as arrays) are distributed across the processor memories. The mapping determines the amount of residual communication needed to bring operands of parallel operations into alignment with each other. A common approach is to break the mapping into two stages: first, an alignment that maps all the objects to an abstract template, and then a distribution that maps the template to the processors. This disclosure deals with two facets of the problem of finding alignments that reduce residual communication; namely, alignments that vary in loops, and objects that permit of replicated alignments. It is shown that loop-dependent dynamic alignment is sometimes necessary for optimum performance, and algorithms are provided so that a compiler can determine good dynamic alignments for objects within "do" loops. Also situations are identified in which replicated alignment is either required by the program itself (via spread operations) or can be used to improve performance. An algorithm based on network flow is proposed for determing which objects to replicate so as to minimize the total amount of broadcast communication in replication.

Claims1

Dependent claims

An optimizing compilation process for compiling a program written in a data-parallel language for execution on a computer having a distributed memory, parallel processor architecture, said compilation process comprising the steps of

producing an array-distributed graph representation of said program;
aligning in said representation of said program each multi-dimensional array-valued object of said program, so that each axis of each such object aligns with a corresponding axis of a N-dimensional template and has a stride which is an integer multiple of the stride of said template along said corresponding axis, where N is the dimensionality of the program object having the greatest dimensionality;
replicating at least some of said array-valued objects across one or more axes of said template to minimize the total amount of broadcast communication;
determining the offset alignment for an origin on each axis of each array-valued object of said program relative to the origin of the corresponding axis of said template, to minimize the total amount of offset communication between said objects on each of said axes;
dynamically readjusting the offset alignment of objects that participate in iterative control flow to minimize the total amount of offset communication between said objects on each of said axes when summed over every iteration of said control flow.

2 more elements

Dependencies are inferred from the claim text.