Bulk Synchronous Parallel - Communication

Communication

In many parallel programming systems, communications are considered at the level of individual actions: sending and receiving a message, memory to memory transfer, etc. This is difficult to work with, since there are many simultaneous communication actions in a parallel program, and their interactions are typically complex. In particular, it is difficult to say much about the time any single communication action will take to complete.

The BSP model considers communication actions en masse. This has the effect that an upper bound on the time taken to communicate a set of data can be given. BSP considers all communication actions of a superstep as one unit, and assumes all messages have a fixed size.

The maximum number of incoming or outgoing messages for a superstep is denoted by . The ability of a communication network to deliver data is captured by a parameter, defined such that it takes time for a processor to deliver messages of size 1.

A message of length obviously takes longer to send than a message of size 1. However, the BSP model does not make a distinction between a message length of or messages of length 1. In either case the cost is said to be .

The parameter is dependent on the following factors:

• The protocols used to interact within the communication network.
• Buffer management by both the processors and the communication network.
• The routing strategy used in the network.
• The BSP runtime system.

A value for is, in practice, determined empirically for each parallel computer. Note that is not the normalised single-word delivery time, but the single-word delivery time under continuous traffic conditions.