Bulk synchronous parallel without barriers

BSP oriented runtime systems try to get closer actual machines to the BSP ideal machine by packing individual messages generated during a superstep and optimizing communication time by rearranging the order in which messages are sent at the end of the superstep. These design considerations strongly contribute to the remarkable accuracy of BSP runtime systems. Unfortunately, barrier synchronization imposes some limits both in the range of available algorithms and in their performance. Although BSP programs can be expressed using PVM and MPI, the counterpart is not always true. The asynchronous nature of some MPI/PVM programs does not easily fit inside the BSP model. Through the generalization of the concept of superstep we propose two extensions to the BSP model: the BSP without barriers (BSPWB) and the Message Passing Machine (MPM) models. These new models are oriented to MPI/PVM parallel programming. The parameters of the models and their quality are evaluated on four standard parallel platforms. The use of these BSP extensions is illustrated through a fast Fourier transform algorithm.