13.2 Embeddings and Their Usefulness Dilation Congestion 5Fig.132 \b Load tactor= Embedding a even-node 0 2 binary tree f into 2D 3」|4 meshes of Various sizes Dilation 2 Dilation Congestion =2 Congestion =2 Load factor Load factor s b「 Expansion: tio of the number of e nodes(9/7,8/7 3 4 5 and 4/7 here) Dilation: Longest path onto which an edge is mapped (routing slowdown) Congestion Max number of edges mapped onto one edge(contention slowdown) Load factor: Max number of nodes mapped onto one node(processing slowdown) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 10Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 10 Dilation: Longest path onto which an edge is mapped (routing slowdown) Congestion: Max number of edges mapped onto one edge (contention slowdown) Load factor: Max number of nodes mapped onto one node (processing slowdown) 13.2 Embeddings and Their Usefulness Fig. 13.2 Embedding a seven-node binary tree into 2D meshes of various sizes. 0 2 3 4 1 5 6 0 2 3 4 1 6 5 0,1 2 4 3 6 5 6 1 0 3,4 2,5 a b c d e f a b c d e f a b c d e f b c, d f Dilation = 1 Congestion = 1 Load factor = 1 Dilation = 2 Congestion = 2 Load factor = 1 Dilation = 1 Congestion = 2 Load factor = 2 Expansion: ratio of the number of nodes (9/7, 8/7, and 4/7 here)