Parasol Compilers: Adaptive Reduction Parallelization

Parasol Compilers Group
Adaptive Reduction Parallelization Techniques

Hybrid Analysis of Memory Reference Patterns
Lawrence Rauchwerger, Hao Yu, Dongmin Zhang

Description

One of the most important operations in scientific applications is the reduction operation, and the parallelization of reductions is crucial to the overall performance of parallel codes. In this work, we adapt reduction parallelization to the actual reference pattern found from executing the reduction loop. The following picture describes our algorithm.

Reduction Algorithm

In order to recognize the access pattern, we have defined the following parameters:

Reduction Parameters

In addition, we have developed three new methods for reduction parallelization:

Linked-list replicated buffers - This method adds links among touched units in the replicated reduction space for each reduction element. When the pattern remains unchanged, instead of going through every replicated reduction unit, it only traverses through the touched units. This method trades 50% more memory usage for faster cross-processor reduction collection. When the access pattern is sparse, it performs better than replicated buffers.

Selective privatization - Based on linked-list replicated buffers, this method reduces the memory overhead by reconstructing the replicated reduction space in a compact representation and builds corresponding links to make both the reduction operation and cross-processor collection fast. When the data set is large, and there are small hot spot areas, it performs better than linked-list replicated buffers. However, it does have a expensive setup phase.

Hash table privatization - Similar to selective privatization. Instead of using arrays (direct addressing), a hash table is used for the replicated reduction space. When the access pattern is extremely sparse, this scheme wins.

Since there is not a single reduction parallelization scheme that always performs the best for all access patterns, we also have developed a decision scheme to choose from suitable reduction parallelization methods according to the different access patterns at run-time. This tree-like decision process uses the parameters we defined and corresponding values we picked up at run-time to choose from the suitable reduction parallelization scheme.

Reduction Decision Tree

Experimental Results

The experimental results show that our adaptive modeling scheme works rather well most of the time. Although it failed to select the best reduction parallelization scheme in some cases, experimental results showed that the absolute performance of our choice was quite close to the best scheme in these cases.

Papers

An Adaptive Algorithm Selection Framework, Hao Yu, Dongmin Zhang, Lawrence Rauchwerger, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), Antibes Juan-les-Pins, France, Sep 2004.
Proceedings(ps, pdf, abstract)

An Adaptive Algorithm Selection Framework, Hao Yu, Dongmin Zhang, Francis Dang, Lawrence Rauchwerger, Technical Report, TR04-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2004.
Technical Report(ps, pdf, abstract)

Architectural Support for Parallel Reductions in Scalable Shared-Memory Multiprocessors, Maria Jesus Garzaran, Milos Prvulovic, Ye Zhang, Alin Jula, Hao Yu, Lawrence Rauchwerger, Josep Torrellas, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), Barcelona, Spain, Sep 2001.
Proceedings(ps, pdf, abstract)

Adaptive Reduction Parallelization Techniques, Hao Yu, Lawrence Rauchwerger, In Proc. ACM Int. Conf. Supercomputing (ICS), pp. 66-77, Santa Fe, New Mexico, USA, May 2000.
Proceedings(ps, pdf, abstract)

Run-time Parallelization Optimization Techniques, Hao Yu, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), San Diego, CA, Aug 1999.
Proceedings(ps, pdf, abstract)

Site Map