EECS Publication
Using Quadtree Encoding for MPI Collective Algorithm Selection Process
Jelena Pjesivac-Grbovic and Graham E. Fagg and Jack J. Dongarra
The performance of an MPI collective operation depends on a number of different factors, some of which are at the hardware level such as network characteristics and topology, while some others are at the software level: algorithm implementation, choice of segment size (if applicable), and the collective operation parameters. Selecting the best possible collective implementation for the particular set of parameters is important for overall application performance. In this paper, we focus on MPI collective algorithm selection process and explore the applicability of the quadtree encoding method to this problem. We construct quadtrees with different properties from the measured algorithm performance data and analyze the quality and performance of decision functions generated from these trees. The experimental data shows that in some cases, the decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5% performance penalty on average. The exact, experimentally measured, decision function for all tested collectives could be fully represented using quadtrees with a maximum of 6 levels. We also evaluate the performance of prototype version of quadtree-based in-memory decision systems, and find that that the decision can be obtained from a 6-level quadtree in close to 170ns. In comparison, fixed reduce decision in FTMPI takes 45ns to evaluate and is not an exact decision. Our results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.
Published 2006-05-15 04:00:00 as ut-cs-06-577 (ID:135)