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