loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
John R. Johnson, University of Chicago and Lawrence Livermore National Laboratory
Ian Foster, University of Chicago and Argonne National Laboratory
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.