# Impact of Process-Processor Mapping and Mapping Techniques

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

Contents

#### 1 Mapping Techniques for Graphs

- Definitions (Based on a mapping from
to*G(V,E)*)*G(V’,E’)***Congestion**– The maximum number of edges inmapped onto edges in*E*.*E’***Dilation**– The maximum number of links inthat any edge in*E’*is mapped onto.*E***Expansion**– The ratio of nodes in the setto nodes in*V’*.*V*

##### Embedding a Linear Array into a Hypercube

**Binary reflected Gray code**(RGC) – A linear array (or ring) of 2^{d}nodes (labeled 0 through 2^{d}-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 2
^{r}x 2^{s}wraparound mesh can be embedded into a 2^{r+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
*p*+ 1 for a^{1/2}*p*node mapping. - A proven lower bound for congestion for any mapping of a Mesh into a linear array is
*p*.^{1/2}

- In general, the congestion of this mapping is

##### Embedding a Hypercube into a 2-D Mesh

- Define the
*p*-node hypercube as a collections of*p*node subcubes, each with^{1/2}*p*nodes.^{1/2} - 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
*p*node subcube is mapped to a^{1/2}*p*node row of the mesh.^{1/2} - The congestion of this mapping is
*p*.^{1/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.