18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers Ouroboros: A Tool for Building Generic, Hybrid, Divide and Conquer Algorithms Santa Fe, New Mexico April 26-April 30 ISBN: 0-7695-2132-0
A hybrid divide and conquer algorithm is one that switches from a divide and conquer to an iterative strategy at a specified problem size. Such algorithms can provide significant performance improvements relative to alternatives that use a single strategy. However, the identification of the optimal problem size at which to switch for a particular algorithm and platform can be challenging. We describe an automated approach to this problem that first conducts experiments to explore the performance space on a particular platform and then uses the resulting performance data to construct an optimal hybrid algorithm on that platform. We implement this technique in a tool, Ouroboros, that automatically constructs a high-performance hybrid algorithm from a set of registered algorithms. We present results obtained with this tool for several classical divide and conquer algorithms, including matrix multiply and sorting, and report speedups of up to six times achieved over non-hybrid algorithms.
Citation:
John R. Johnson, Ian Foster, "Ouroboros: A Tool for Building Generic, Hybrid, Divide and Conquer Algorithms," ipdps, vol. 1, pp.78a, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers, 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||