Routing Mechanisms for Interconnection Networks

Posted By on March 17, 2016


Download PDF
Communication Costs in Parallel Machines
Impact of Process-Processor Mapping and Mapping Techniques

Routing mechanism – determines the path a message takes from source to sink.

  • Input: source and sink nodes
  • Output: One or more paths from source to sink
  • Types of routing mechanisms:
    • Minimal – Always selects the shortest path between source and sink. Can lead to congestion.
    • Non-minimal – May route along a longer path to avoid congestion.
    • Deterministic – Selects a unique path based on source and sink, ignoring info about the network. Results in uneven use of resources.
    • Adaptive – Determines a path from source to sink based on information about the network.
  • Dimension Ordered Routing (minimal and deterministic) – assigns successive channels for traversal by a message based on a numbering scheme determined by the dimensions of the channel.
    • XY-routing – uses a 2-D mesh.
      • To reach PDy,Dx from PSy,Sx, traverse a minimal route from PSy,Sx to PSy,Dx then traverse a minimal route from PSy,Dx to PDy,Dx.
      • The length of this path is |Sx – Dx| + |Sy – Dy|.
    • E-cube routing – uses a hypercube
      • Compute the exclusive-or of Ps and Pd (Ps ⊕ Pd). Traverse from Ps to Pi along the dimension corresponding to the lowest ‘1’ bit in Ps ⊕ Pd. Repeat this process, replacing Ps with Pi, Pi+1, … until Pd is reached.
      • The minimum distance is the number of ones in Ps ⊕ Pd.
Communication Costs in Parallel Machines
Impact of Process-Processor Mapping and Mapping Techniques

Download PDF

Posted by Akash Kurup

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

Website: http://world4engineers.com