MPI Collective Algorithm Selection and Quadtree Encoding

Additional resources on the web

Information about paper

Authors Jelena Pjesivac-Grbovic, Graham E. Fagg, Thara Angskun, George Bosilca, Jack J. Dongarra
Title "MPI Collective Algorithm Selection and Quadtree Encoding"
Publication venue*Submitted to Special Edition of Journal of Parallel Computing, published by Elsevier.
Abstract We explore the applicability of the quadtree encoding method to the run-time MPI collective algorithm selection problem. Measured algorithm performance data was used to construct quadtrees with different properties. The quality and performance of generated decision functions and in-memory decision systems was evaluated.

Experimental data shows that in some cases, a decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5\% performance penalty on average. Experimentally measured data was fully represented using quadtrees with maximum of 6 levels. Our results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.

Draft version #1 Available here.

Figures
Figure 1  
Reduce decision map  
Figure 2a Figure 4a
Max-depth limited bcast decision map on frodo Accuracy-threshold limited bcast decision map on frodo
Figure 2b Figure 4b
Max-depth limited bcast decision map on grig Accuracy-threshold limited bcast decision map on grig
Legend for Figures 2 and 4  
Legend for Broadcast decision maps  
Figure 3a Figure 5
Performance penalty of Max-depth limited bcast decision map on frodo Quadtree depth vs. Accuracy-threshold Performance penalty vs. Accuracy-threshold
Figure 3b Figure 6
Performance penalty of Max-depth limited bcast decision map on grig Performance penalty vs Quadtree depth for Bcast Performance penalty vs Quadtree depth for Reduce