Parallel Processing Letters cfl World Scientific Publishing Company A NEW WAY TO DIVIDE AND CONQUER

ABSTRACT Valiant's model of bulk-synchronous parallel (BSP) computation does not allow the programmer to synchronize a subset, rather than the complete set of a 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 synchronization. The proposed method of divideand-conquer BSP programming is fully compliant with the BSP computation model. The method is based on sequentially interleaved threads of BSP computation, called superthreads. Keywords: Bulk-synchronous parallel; BSP; Subset synchronization; Divideand-conquer; Superthreads