Alexandros V Gerbessiotis and Constantinos J Siniolakis
October 1996, 12pp.
The design of a complex algorithm relies heavily on a set of primitive operations and the instruments required to compile these operations into an algorithm. In this work, we examine some of these basic primitive operations and present algorithms that are suitable for the Bulk-Synchronous Parallel model. In particular, we consider algorithms for the following primitive operations: broadcasting, parallel-prefix, merging, generalized and integer sorting.
While our algorithms are fairly simple themselves, description of their performance in terms of the BSP parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables software to be written once and for all that can be migrated efficiently among a variety of parallel machines.