Programming Model



next up previous
Next: Measurement Methodology Up: Message Passing Previous: Message Passing

Programming Model

Processes of a parallel application distributed over a collection of processors must communicate problem parameters and results. In distributed memory multiprocessors or workstations on a network, the information is typically communicated with explicit message-passing subroutine calls. To send data to another process, a subroutine is usually provided that requires a destination address, message, and message length. The receiving process usually provides a buffer, a maximum length, and the senders address. The programming model is often extended to include both synchronous and asynchronous communication, group communication (broadcast and multicast), and aggregate operations (e.g., global sum).

Message passing performance is usually measured in units of time or bandwidth (bytes per second). In this report, we choose time as the measure of performance for sending a small message. The time for a small, or zero length, message is usually bounded by the speed of the signal through the media (latency) and any software overhead in sending/receiving the message. Small message times are important in synchronization and determining optimal granularity of parallelism. For large messages, bandwidth is the bounded metric, usually approaching the maximum bandwidth of the media. Choosing two numbers to represent the performance of a network can be misleading, so the reader is encouraged to plot communication time as function of message length to compare and understand the behavior of message passing systems.

Message passing time is usually a linear function of message size for two processors that are directly connected. For more complicated a networks, a per-hop delay may increase the message passing time. Message-passing time, , can be modeled as

with a start-up time, , a per-byte cost, , and a per-hop delay, , where is the number of bytes per message and the number of hops a message must travel. On most current message-passing multiprocessors the per-hop delay is negligible due to ``worm-hole'' routing techniques and the small diameter of the communication network [3]. The results reported in this report reflect nearest-neighbor communication. A linear least-squares fit can be used to calculate and from experimental data of message-passing times versus message length. The start-up time, , may be slightly different than the zero-length time, and should be asymptotic bandwidth. The message length at which half the maximum bandwidth is achieved, , is another metric of interest and is equal to [6]. As with any metric that is a ratio, any notion of ``goodness'' or ``optimality'' of should only be considered in the context of the underlying metrics and .

There are a number of factors that can affect the message passing performance. The number of times the message has to be copied or touched (e.g., checksums) is probably most influential and obviously a function of message size. The vendor may provide hints as to how to reduce message copies, for example, posting the receive before the send. Second order effects of message size may also affect performance. Message lengths that are powers of two or cache-line size may provide better performance than shorter lengths. Buffer alignment on word, cache-line, or page may also affect performance. For small messages, context-switch times may contribute to delays. Touching all the pages of the buffers can reduce virtual memory effects. For shared media, contention may also affect performance. There also may be some first-time effects that can be identified or eliminated by performing some ``warm up'' tests before collecting performance data.

There are of course other parameters of a message-passing system that may affect performance for given applications. The aggregate bandwidth of the network, the amount of concurrency, reliability, scalability, and congestion management may be issues.



next up previous
Next: Measurement Methodology Up: Message Passing Previous: Message Passing



Jack Dongarra
Fri Aug 4 04:24:58 EDT 1995