Communication Costs in Parallel Machines

Posted By on March 17, 2016

Download PDF
Physical Organization of Parallel Programs
Routing Mechanisms for Interconnection Networks
  • 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.
Physical Organization of Parallel Programs
Routing Mechanisms for Interconnection Networks

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby