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 *
* 03-1
Direct Network Graph Representation
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.
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-1 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-1
03-2 *
* 03-2
Notation
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 used in radix-k form.
Let i be an integer.
Let k be an integer and a 2 hki .
Then notation i(a) indicates digit a in i's radix-k representation.
Digit 0 is the least significant, digit k 1 is the most significant.
Other Useful Notation
hxi j f0; 1; : : :; x 1g.
E.g., h4i j f0; 1; 2; 3g.
03-2 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-2
03-3 *
* 03-3
k-ary n-cube (KNC) Network Family
Popular direct network family.
Also called: n-dimensional mesh, generalized cube.
Properties
- All members are easily routed.
- Members exhibit medium to high diameter.
- Suitable for many parallel algorithms.
Plan
- Special Cases Described
- Family Described
03-3 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-3
03-4 *
* 03-4
Linear Network
Nodes arranged in a line.
Graph description of N -node linear network:
V = hN i = f0; 1; : : :; N 1g
E = f (i; i + 1) j i 2 hN 1i g
Properties
Degree, ffi = 2.
Routing: increment (or decrement) vertex of current position until
destination reached.
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.
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-4 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-4
03-5 *
* 03-5
Two-Dimensional Mesh Network
Generalization of linear network to two dimensions.
Graph description of k2 -node 2-dimensional mesh:
ff
V = k2 = f0; 1; : : :; k2 1g
2 ff
E = f (i; i + 1) j i 2 k ; (i mod k) < k 1 g
2 ff
[ f (i; i + k) j i 2 k k g
Properties
Degree, ffi = 4.
Routing:
- Treat vertex as 2-digit, radix-k number.
- Increment (or decrement) least-significant digit of vertex of cur-
rent position until equal to least-significant digit of destination
vertex.
- Increment (or decrement) most-significant digit of vertex of cur-
rent 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 (1 + k) k ( 1 + k)
d = ____________________________3:(1 + k2 )
Bisection width, k.
03-5 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-5
03-6 *
* 03-6
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-6 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-6
03-7 *
* 03-7
KNC: Generalization of previous two networks to n dimensions.
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.
Properties
Degree:
ae
ffi = 2n;n; ifikf>k2;= 2.
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.
n1X fi fi
Distance, du;v = fiu(i) v(i)fi .
i=0
Diameter, D = n(k 1).
Average Distance:
__ (k1)(k+1)kn1
d = n_3___________________(kns1)s n_3 k 1_k .
Bisection width, kn1 .
03-7 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-7
03-8 *
* 03-8
Usefulness For k = 2.
Short (logarithmic) average distance and diameter.
Easy to route.
Large degree (bad).
03-8 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-8
03-9 *
* 03-9
Choice of k and n for KNC
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-9 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli0*
*3. 03-9
03-10 *
* 03-10
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 of KNC.
) n = log k N
) k = N 1_n
Latency (For These Comparisons)
__ M
L = d + ____w 1
03-10 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-10
03-11 *
* 03-11
Moore Bound
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-11 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-11
03-12 *
* 03-12
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-12 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-12
03-13 *
* 03-13
Let N denote the total number of nodes in a network of diameter d
and degree ffi.
X d
N = N 0(i)
i=0
X d
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.
If ffi AE 1:
d ss log ffiN .
Note that this is much better than the KNC family.
But do such networks exist?
03-13 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-13
03-14 *
* 03-14
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:
j u k
oem;k (u) j mu + __k (mod mk).
Examples:
oe2;4 (1) = 2
oe2;4 (0) = 0
oe2;4 (5) = 3
03-14 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-14
03-15 *
* 03-15
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-15 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-15
03-16 *
* 03-16
Relationship Between Shu- e and Shift Functions
The shu- e function is a special case of the shift functions.
That is:
- 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 h jSji ,
- set of integers h jSjn 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 se-
quence of digits.
03-16 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-16
03-17 *
* 03-17
The Exchange Function
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
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-17 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-17
03-18 *
* 03-18
Shu- e-Exchange Graph
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.
Characteristics:
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;mn 1 = 2n 1.
Average distance: not known, probably close to diameter.
Bisection width: for m = 2: BW = (2n1 ).
03-18 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-18
03-19 *
* 03-19
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 destina-
tion.
(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-19 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-19
03-20 *
* 03-20
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.
Characteristics:
Degree: ffi = 2m.
Distance: du;v n.
The exact distance cannot be expressed in a compact form.
Diameter: D = n.
For example, d0;mn 1 = 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-20 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-20
03-21 *
* 03-21
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-21 EE 7725 Lecture Transparency. Formatted 12:54, 6 September 1996 from lsli*
*03. 03-21
| David M. Koppelman - koppel@ee.lsu.edu | Modified 9 Sep 1996 12:55 (17:55 UTC) |