This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
03-1 Direct Network Graph Representation *
* 03-1
Idea: describe (specify) direct network using graph.
Network , Graph
Links , Edges
Nodes , Vertices
Graph Representation
Uses two sets:
- Set of vertices, V .
- Set of edges E.
Usual notation, G = (V; E):
- G is the name of the graph.
- V is the set of vertices.
- E is the set of edges.
03-1 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-1
03-2 *
* 03-2
Consider G = (V; E).
Let u 2 V and v 2 V .
The following two statements are equivalent:
- There is an edge between u and v.
- (u; v) 2 E.
For any graph (V; E): E V V .
03-2 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-2
03-3 Notation *
* 03-3
For graphs used in class:
V is a set of consecutive integers starting at 0.
E.g., V = f 0; 1; 2 g.
Integers sometimes expressed in radix-k form.
Let i, k, and a be positive integers.
Then notation i(a) indicates digit a in i's radix-k representation.
Digit 0 is the least significant.
Digit notation can be juxtaposed: i = i(n1) i(n2) i(0),
where n is the number of radix-k digits in i.
Examples:
Let i = 123410 = 4d216 = 34127.
For k = 16, i = i(2)i(1)i(0) = 4d2 and so i(2) = 4, i(1) = d, i(0) = 2.
For k = 7, i = i(3)i(2)i(1)i(0) = 3412 and so i(3) = 3, i(2) = 4, i(1) = 1, i(0) = 2.
03-3 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-3
03-4 *
* 03-4
Other Useful Notation
hxi j f0; 1; : :;:x 1g.
E.g., h4i j f0; 1; 2; 3g.
03-4 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-4
03-5 k-ary n-cube (KNC) /n-D Mesh Network Families *
* 03-5
Popular direct network families.
n-D mesh is generalization of a 2-D mesh.
k-ary n-cube is n-D mesh with wraparound connections.
Properties
- All members are easily routed.
- Members exhibit medium to high diameter.
- Suitable for many parallel algorithms.
Plan
- Special Cases Described
- Families Described
03-5 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-5
03-6 *
* 03-6
Linear Network
Nodes arranged in a line.
Graph description of N -node linear network:
V = hN i = f0; 1; : :;:N 1g
Properties
E = f (i; i + 1) j i 2 hN 1i g
Degree, ffi = 2.
Routing: increment (or decrement) vertex of current position until at destination.
Distance, du;v = ju vj.
Diameter, D = N 1.
Average Distance:
__ 2 N2X N1X N + 1
d = ___________N (N 1) j i = _______.
i=0 j=i+1 3
Bisection width, 1.
03-6 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-6
03-7 *
* 03-7
Usefulness
Diameter and average distance too large for general use.
Bisection width too small for general use.
Might be useful for special-purpose applications.
Useful for simple classroom examples.
03-7 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-7
03-8 *
* 03-8
Two-Dimensional Mesh Network
Generalization of linear network to two dimensions.
Graph description of k2 -node 2-dimensional mesh:
2 ff 2
V = k = f0; 1; : :;:k 1g
2 ff 2 ff
E = f (i; i + 1) j i 2 k ; (i mod k) < k 1 g [ f (i; i + k) j i 2 k k g
03-8 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-8
03-9 Properties *
* 03-9
Degree, ffi = 4.
Routing:
- Treat vertex as 2-digit, radix-k number.
- Increment (or decrement) least-significant digit of vertex of current position until
equal to least-significant digit of destination vertex.
- Increment (or decrement) most-significant digit of vertex of current position until
equal to most-significant digit of destination vertex.
fi fi fi fi
Distance, du;v = fiu(0) v(0)fi+ fiu(1) v(1)fi.
Diameter, D = 2(k 1).
Average Distance:
__ 2 k (k + 1) (k 1)
d = ____________________3:(k2 1)
Bisection width, k.
03-9 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 fro*
*m lsli03. 03-9
03-10 *
* 03-10
Usefulness
Diameter large, but acceptable.
May be easy to build.
Used in general-purpose computers.
Well suited to some algorithms.
Works poorly with other algorithms.
03-10 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-10
03-11 *
* 03-11
n-D Mesh: Generalization of previous two networks to n dimensions.
Graph description:
V = hkn i.
E = f (u; u + ki) j i 2 hni ; u 2 V; u(i)< k 1 g.
03-11 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-11
03-12 *
* 03-12
Mesh Routing:
- Treat vertex as n-digit, radix-k number.
- Choose a digit.
- Increment (or decrement) this digit of the vertex of the current position until
equal to the corresponding digit of destination vertex.
- Repeat until all digits are chosen.
03-12 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-12
03-13 Mesh Properties *
* 03-13
Degree:
ae
ffi = 2n;n; ifikf>k2;= 2.
n1X fi fi
Distance, du;v = fiu(i) v(i)fi.
i=0
Diameter, D = n(k 1).
Average Distance:
__ n (k 1)(k + 1)kn1 n 1
d = __3____________________(knss1)_3 k __k .
Bisection width, kn1 .
03-13 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-13
03-14 *
* 03-14
Usefulness For k = 2.
Short (logarithmic) average distance and diameter.
Easy to route.
Large degree (bad).
03-14 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-14
03-15 Choice of k and n for Mesh *
* 03-15
Goal: determine tradeoffs when k and n varied.
Method:
- Fix some measures.
- Vary k and n.
- Observe effect on other measures.
Case 1: Fix N .
Observe effect on average distance, latency, bisection width, and cost.
Case 2: Fix N and Bisection Width
Observe effect on average distance, latency, and cost.
Case 3: Fix N and Cost
Observe effect on average distance, latency, and bisection width.
03-15 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-15
03-16 *
* 03-16
Equations for All Cases
Cost (For These Comparisons).
Count number of links, include width:
C = 1_2N ffiw.
Number of Nodes
N = kn by definition.
) n = logk N
) k = N 1_n
Latency (For These Comparisons)
__ M
L = d + ___w 1
03-16 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-16
03-17 k-ary n-cube: Mesh with Wraparound Connections *
* 03-17
Graph description of kn -node k-ary n-cube:
V = hkn i.
E = f (u; u + ki) j i 2 hni ; u 2 V; u(i)< k 1 g [
f (u; u (k 1)ki) j i 2 hni ; u 2 V; u(i)= k 1 g:
03-17 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-17
03-18 *
* 03-18
k-ary n-cube Routing (similar to mesh):
- Treat vertex as n-digit, radix-k number.
- Choose a digit.
- Increment (or decrement) this digit of the vertex of the current position until
equal to the corresponding digit of destination vertex.
- Repeat until all digits are chosen.
03-18 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-18
03-19 k-ary n-cube Properties *
* 03-19
Degree (same as mesh):
ae
ffi = 2n;n; ifikf>k2;= 2.
n1X fi fi fi fi
Distance, du;v = min fiu(i) v(i)fi; k fiu(i) v(i)fi .
i=0
k
Diameter, D = n __ .
2
8 n+1
>>>n__k______ if k even
__ < 4 kn 1
Average Distance, d = .
>>> n+1 n1
: n_k_____+_k______ if k odd
4 kn 1
ss nk_4
ae n1
Bisection width, k2kn1 ; ; ifikf=k2;>.2
03-19 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-19
03-20 Moore Bound *
* 03-20
Motivation: does the hypercube have a minimum diameter?
Can use Moore bound to answer this.
Method Outline:
- Fix degree and diameter of minimum-diameter network.
(Degree of ffi, diameter of d).
- Find maximum number of nodes that any such network could have.
- Solve for diameter.
03-20 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-20
03-21 *
* 03-21
Derivation
Call some node the center of the network.
Let N 0(i) denote the number of nodes at distance i from center.
Then:
N 0(0) = 1
N 0(1) ffi
N 0(2) ffi(ffi 1) = N 0(1)(ffi 1)
N 0(3) ffi(ffi 1)2 = N 0(2)(ffi 1)
N 0(i) N 0(i 1)(ffi 1) = ffi(ffi 1)(i1) for i > 1.
03-21 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-21
03-22 *
* 03-22
Let N denote the total number of nodes in a network of diameter d and degree ffi.
Xd
N = N 0(i)
i=0
Xd
N 0(0) + N 0(1) + N 0(i)
i=2
Xd
1 + ffi + ffi (ffi 1)i1
i=2
d1X
1 + ffi + ffi (ffi 1)j
j=1
d
1 + ffi + ffi (ffi__1)___(ffi__1)_(ffi 1) 1
d 2
ffi(ffi__1)___ffi 2
Solving for d yields:
d log(ffi2) N_(ffi__2)_+_2_ffi.
03-22 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-22
03-23 *
* 03-23
If ffi AE 1:
d ss logffiN .
Note that this is much better than the KNC family.
But do such networks exist?
03-23 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-23
03-24 *
* 03-24
Shu- e and Shift Functions
Used to describe edges in several graphs.
Idea: Rotate digits in a number (with an end-around shift).
Two definitions will be given:
Shu- e Function (for Integers)
Let u 2 hmki where m and k are positive integers.
The shu- e function oem;k j hmki ! hmki is given by:
ju k
oem;k (u) j mu + __k (mod mk).
Examples:
oe2;4(1) = 2
oe2;4(0) = 0
oe2;4(5) = 3
03-24 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-24
03-25 *
* 03-25
Shift Functions (for Sequences)
Let u(n1) u(n2) : : :u(0) be any sequence of symbols, where u(i)2 S,
and S be the set of all possible sequences.
Then the left-shift function oel j S ! S is given by:
oel u(n1) u(n2) : : :u(0) = u(n2) u(n3) : : :u(0)u(n1) .
Examples:
oel(abc) = bca
oel(1101) = 1011
The right-shift function oer j S ! S is given by:
oer u(n1) u(n2) : : :u(0) = u(0)u(n1) : : :u(2)u(1).
Examples:
oer(abc) = cab
oer(1101) = 1110
03-25 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-25
03-26 Relationship Between Shu- e and Shift Functions *
* 03-26
The shu- e function is a special case of the shift functions.
- Given any set of symbols S,
- any positive integer n,
- and any set of sequences S = S S S (n times),
- and any S 2 S,
there exist a corresponding:
- set of digits hjSji ,
- set of integers hjSjn i,
- a mapping S ! hjSjn i
such that for any S1 2 S if oel(S1) = S2 and oer(S1) = S3 then oejSj;jSjn1 (s1) = s2 and
oejSjn1 ;jSj(s1) = s3
where s1, s2, and s3 are the integers corresponding to S1, S2, and S3, respectively.
In other words, any sequence of symbols could be viewed as a sequence of digits.
03-26 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-26
03-27 The Exchange Function *
* 03-27
Used to describe edges in several graphs.
Idea: change least-significant-digit of a number.
Exchange function for Integers
Let u 2 hmki and i 2 hmi , where m and k are positive integers.
Then the exchange function O j hmki ; hmi ! hmki is given by
j u k
Om (u; i) = m ___m + i
Examples:
O2(5; 0) = 4
O3(13; 2) = 14
03-27 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-27
03-28 *
* 03-28
Exchange function for Sequences
Let u(n1) u(n2) : : :u(0) be any sequence of symbols, where u(i)2 S,
and S be the set of all possible sequences.
Then the exchange function O j S; S ! S is given by:
O(u(n1) u(n2) : : :u(0); x) = u(n1) u(n2) : : :x, where x 2 S.
Examples:
O(abc; d) = abd
O(1011; 0) = 1010
O("_"; ") = "_"
03-28 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-28
03-29 Shu- e-Exchange Graph *
* 03-29
Let m and n be positive integers.
The m; n shu- e-exchange, (V; E) graph is given by:
V = hmn i
E = f (u; oem;mn1 (u)) j u 2 V g [ f (u; Om (u; i)) j u 2 V; i 2 hmi g.
03-29 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-29
03-30 Shu- e-Exchange Graph Characteristics: *
* 03-30
Degree: ffi = m + 1.
Distance: du;v 2n 1.
The exact distance cannot be expressed in compact form.
Diameter: D = 2n 1.
For example, d0;mn1 = 2n 1.
Average distance: not known, probably close to diameter.
Bisection width: for m = 2: BW = (2n1 ).
03-30 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-30
03-31 *
* 03-31
Non-minimal Routing of Shu- e Exchange Graph
For request (u(n1) u(n2) u(0); v(n1) v(n2) v(0)):
- Step 0:
"Replace" least-significant-digit of source with MSD of destination.
(u(n1) u(n2) u(0); u(n1) u(n2) v(n1) ).
- Step i 2 f1; 2; : :;:n 1g:
Left shift the current node number.
(u(ni) u(ni1) u(1)v(n1) v(ni) ;
u(ni1) u(ni2) u(1)v(n1) u(ni) )
"Replace" digit n i of source with digit n i 1 of destination.
Take edge
(u(ni1) u(ni2) u(1)v(n1) u(ni) ;
u(ni1) u(ni2) u(1)v(n1) v(ni1) )
03-31 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-31
03-32 *
* 03-32
de Bruijn Graph
Also called Good graph.
Let m and n be positive integers.
The m; n de Bruijn Graph, (V; E) is given by:
V = hmn i
E = f (u; Om (oem;mn1 (u); i)) j u 2 V i 2 hmi g.
03-32 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-32
03-33 de Bruijn Graph Characteristics: *
* 03-33
Degree: ffi = 2m.
Distance: du;v n.
The exact distance cannot be expressed in a compact form.
Diameter: D = n.
For example, d0;mn1 = n.
Average distance:
8 9
>>>n 3 _8; if m = 2;
>>>
8_
__ >< n 1 9; if m = 3;
d >
>>>n 1 25_72; if m = 4;
>>>
: n 2(m+1)2__
m(m1)2 ; if m > 4.
03-33 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-33
03-34 *
* 03-34
Non-minimal Routing of the de Bruijn Graph
For request (u(n1) u(n2) u(0); v(n1) v(n2) v(0)):
- Step i 2 f0; 1; : :;:n 1g:
Left-shift the current node number, then exchange LSD.
(u(ni1) u(ni2) u(0)v(n1) v(ni) ;
u(ni2) u(ni3) u(0)v(n1) v(ni1) )
03-34 EE 7725 Lecture Transparency. Formatted 13:04, 10 September 1997 f*
*rom lsli03. 03-34
| David M. Koppelman - koppel@ee.lsu.edu | Modified 10 Sep 1997 13:05 (18:05 UTC) |