ALCOMFT-TR-01-3

Alexandre Tiskin
A new way to divide and conquer
Warwick. Work packages 1 and 4. January 2001.

Abstract: Valiant's model of bulk-synchronous parallel (BSP) computation does not allow the programmer to synchronise a subset, rather than the complete set of parallel computer's processors. This is perceived by many to be an obstacle to expressing divide-and-conquer algorithms in the BSP model. We argue that the divide-and-conquer paradigm fits naturally into the BSP model, without any need for subset synchronisation. The proposed method of divide-and-conquer BSP programming is fully compliant with the BSP computation model. The method is based on sequentially interleaved threads of BSP computation, called superthreads.

Postscript file: ALCOMFT-TR-01-3.ps.gz (69 kb).