Skip Navigation

The Computer Journal 2001 44(4):303-320; doi:10.1093/comjnl/44.4.303
© 2001 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Amor, M.
Right arrow Articles by Zapata, E. L.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

A Data-Parallel Formulation for Divide and Conquer Algorithms

M. Amor1, F. Argüello2, J. López3, O. Plata3 and E. L. Zapata3

1 Department of Electronics and Systems, University of La Coruña, E–15071 La Coruña, Spain Email: margaaml@udc.es 2 Department of Electronics and Computation, University of Santiago de Compostela, E–15782 Santiago de Compostela, Spain 3 Department of Computer Architecture, University of Málaga, E–29071 Málaga, Spain

This paper presents a general data-parallel formulation for a class of problems based on the divide and conquer strategy. A combination of three techniques—mapping vectors, index-digit permutations and space-filling curves—are used to reorganize the algorithmic dataflow, providing great flexibility to efficiently exploit data locality and to reduce and optimize communications. In addition, these techniques allow the easy translation of the reorganized dataflows into HPF (High Performance Fortran) constructs. Finally, experimental results on the Cray T3E validate our method.

Received 23 December, 1999. Revised 5 April, 2001.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.