A data-parallel formulation for divide and conquer algorithms

This paper presents a general data-parallel formulation for a class of prob lems based on the divide and conquer strategy. A combination of three techn iques-mapping vectors, index-digit permutations and space-filling curves-ar e used to reorganize the algorithmic dataflow, providing great flexibility to efficiently exploit data locality and to reduce and optimize communicati ons. In addition, these techniques allow the easy translation of the reorga nized dataflows into HPF (High Performance Fortran) constructs. Finally, ex perimental results on the Cray T3E validate our method.