Communication Costs in Parallel Machines

Communication overhead is a significant concern in parallel programs, alongside idling and contention. The cost of communication is influenced by various factors including programming model semantics, network topology, data handling, routing, and software protocols.

Message Passing Costs

The total time to transfer a message over a network consists of:

• Startup time (ts): Time spent at sending and receiving nodes, including routing algorithm execution.

• Per-hop time (th): Time per hop, determined by switch latencies, network delays, etc.

• Per-word transfer time (tw): Time per word, including link bandwidth, error checking, etc.

Store-and-Forward Routing

• Messages are completely received at intermediate hops before forwarding.

• Total communication cost for a message of size �m words traversing �l links: �comm=��+����tcomm​=ts+mltw.

Packet Routing

• Breaks messages into packets, pipelining them through the network.

• Each packet carries routing, error checking, and sequencing information.

• Total communication time: �comm=��+�ℎ�+���tcomm​=ts+thl+twm.

Cut-Through Routing

• Further divides messages into smaller units called flits.

• All flits take the same path in sequence, minimizing header information.

• Total communication time: �comm=��+�ℎ�+���tcomm​=ts+thl+twm, with typically smaller ��tw.

Simplified Cost Model

• Cost of communicating a message �l hops away using cut-through routing: �comm=��+��ℎ+���tcomm​=ts+lth+twm.

• Approximated as �comm=��+���tcomm​=ts+twm when �ℎth is smaller than ��ts and ��tw, and routing/placement of tasks cannot be controlled.

In summary, understanding communication costs in parallel machines is crucial for optimizing performance and efficiency in parallel programs. Factors such as routing algorithms, network topology, and message handling techniques significantly impact overall communication overhead.