9. Mapping Techniques

Mapping Techniques for Graphs

When mapping a graph �(�,�)G(V,E) onto another graph �0(�0,�0)G0​(V0​,E0​), several metrics are essential to consider:

• Congestion: The maximum number of edges from �E mapped onto any edge in �0E0​. It indicates the level of traffic concentration on specific links.

• Dilation: The maximum number of links in �0E0​ that any edge from �E is mapped onto. It measures the stretching or expansion of paths in the mapping process.

• Expansion: The ratio of the number of nodes in set �0V0​ to that in set �V. It reflects how much the new graph has expanded compared to the original graph.

Embedding a Linear Array into a Hypercube

To embed a linear array (or ring) composed of 2�2d nodes into a �d-dimensional hypercube, we use a mapping function �(�,�)G(i,d). The function �(�,�)G(i,x) is defined recursively as follows:

• �(0,1)=0G(0,1)=0

• �(1,1)=1G(1,1)=1

• �(�,�+1)={�(�,�)if �<2�2�+�(2�+1−1−�,�)if �≥2�G(i,x+1)={G(i,x)2x+G(2x+1−1−i,x)​if i<2xif i≥2x​

This function is known as the binary reflected Gray code (RGC). It ensures that adjacent entries in the linear array differ by only one bit position, which corresponds to mapping processors to neighboring nodes in the hypercube.

Since adjacent entries in the linear array are mapped to neighboring nodes in the hypercube, the congestion, dilation, and expansion of the mapping are all equal to 1. This indicates an efficient and congestion-free embedding of the linear array into the hypercube.


…