Impact of Process-Processor Mapping and Mapping Techniques

Posted By on March 17, 2016

Download PDF
Routing Mechanisms for Interconnection Networks
Principles of Parallel Algorithm Design
  • The programmer has no control over how logical processes are mapped to network nodes. This can lead to congestion problems if the programmer does not understand the mapping algorithm used.

1 Mapping Techniques for Graphs

  • Definitions (Based on a mapping from G(V,E) to G(V’,E’))
    • Congestion – The maximum number of edges in E mapped onto edges in E’.
    • Dilation – The maximum number of links in E’ that any edge in E is mapped onto.
    • Expansion – The ratio of nodes in the set V’ to nodes in V.
Embedding a Linear Array into a Hypercube
  • Binary reflected Gray code (RGC) – A linear array (or ring) of 2d nodes (labeled 0 through 2d-1) can be embedded into a d-dimensional hypercube by mapping node i of the linear array onto node G(i,d) of the hypercube. The function G(i,x) is defined as follows:
G(0,1) = 0
G(1,1) = 1
G(i, x+1) = 
  G(i,x)                     if i < 2^x
  2^x + G(2^x+1 - 1 - i, x)  if i >= 2^x
  • The “reflection” of the RGC is along the midpoint of the bits at a dimension.
  • RGC has a dilation and congestion of 1.
Embedding a Mesh into a Hypercube
  • A 2r x 2s wraparound mesh can be embedded into a 2r+s-node hypercube by mapping node (i,j) of the mesh onto node G(i,r-1)||G(j,s-1) (where ‘||’ is the concatenation of the two Gray codes).
  • This mapping has a congestion and dilation of 1.
Embedding a Mesh into a Linear Array
  • Use the inverse of G(i,x) to obtain a mapping of a mesh into a linear array.
    • In general, the congestion of this mapping is p1/2 + 1 for a p node mapping.
    • A proven lower bound for congestion for any mapping of a Mesh into a linear array is p1/2.
Embedding a Hypercube into a 2-D Mesh
  • Define the p-node hypercube as a collections of p1/2 node subcubes, each with p1/2 nodes.
  • Let d = log p
  • Take the d/2 LSB and use them to define individual sub-cubes
  • From these sub-cubes, define another subcube by its d/2 MSBs.
  • Each p1/2 node subcube is mapped to a p1/2 node row of the mesh.
  • The congestion of this mapping is p1/2/2.
Process-Processor Mapping and Design of Interconnection Networks
  • Since denser networks can be mapped to sparser networks with congestion overhead, it is possible to make a sparser network perform as well as a denser network by increasing link bandwidth to compensate. These “mapped-to” sparse networks are called fattened networks.

2 Cost-Performance Tradeoffs

  • The cost of traversal in a sparse network and be made comparable to a dense network by increasing wires per channel.
Routing Mechanisms for Interconnection Networks
Principles of Parallel Algorithm Design

Download PDF

Posted by Akash Kurup

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