Communication Costs in Parallel Machines
- Communication Costs – Overhead for communicating between processing elements.
1 Message Passing Costs in Parallel Computers
- Communication time = Message prep time + Network traversal time
- Startup time – time required to handle the message at the sending and recieveing nodes.
- Per-hop time (or node latency) – time taken by the header of a message to travel between two directly-connected nodes.
- Per-word transfer time – 1 / r where r is channel bandwidth (r words per second)
- Types of routing
- Store-and-forward routing – Each intermediate node on the path forwards the message to the next node only after it has recieved and stored the entire message.
- Linear time – tcomm = ts + (mtw + th) * L
- Parallel time – tcomm = ts + mLtw
- Packet routing – Break up the message into smaller packets and then forward them through the network
- Time – tcomm = ts + thL + twm where tw = tw1 + tw2(1 + s/r)
- Cut through routing – Assign messages predefined routes based on message type then transfer as “flits”
- Time – tcomm = ts + Lth + twm
- Cut-through routing can be optimized using the following techniques
- Communicate in bulk – save on startup time by sending larger messages
- Minimize the volume of data – reduce per word overhead
- Minimize distance of data transfer – minimze number of hops
2 Communication Costs in Shared-Address-Space
- Associating communication costs with parallel programs is harder in message passing architectures than in shared-access-space architectures. This is because in message passing systems:
- Memory layout is determined by the system
- Finite cache sizes can result in cache thrashing
- Overheads associated with invalidate and update operations are difficult to quantify
- Spatial locality is difficult to model
- Prefetching can play a role in reducing the overhead associated with data access.
- False sharing is often an important overhead in many programs
- Contention in shared accesses is often a major contributing overhead in shared address space machines.