# Impact of Process-Processor Mapping and Mapping Techniques

Posted By on March 17, 2016

• 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.