Scheideler C. Universal Routing Strategies for Interconnection Networks

Подождите немного. Документ загружается.

3. Terminology

In this chapter we present all models and terminology we will need in the

following. We start with giving basic definitions and inequalities, followed

by a short introduction in probability theory and graph theory. Afterwards,

we present in Section 3.4 all models and terminology in the field of routing

theory that will be used in this book.

3.1 Basic Definitions and Inequalities

We frequently use the following notations.

If we use "e" in formulas, we always mean the Euler number (2.71828..).

- By "log" we mean the logarithm to the base of 2. "In" denotes the logarithm

to the base of e. If we use any other base, say b, we write "logb".

logkn means (logn) k.

1N means the set of integers {1, 2, 3, 4,...}, and IN0 = IN U {0}.

- By "with high probability" (or "w.h.p." for short) we mean a probability

of at least 1 -

1/n k

for any constant k > 0, where n is the number of ele-

mentary events (usually the number of messages) in a random experiment.

Let M be an arbitrary set. Given any subset A c_ M, JA] denotes the number

of elements in A, and .4 = M \ A. 7~(M) is called

power set

of M and consists

of all subsets A c_ M. For any c E IN, the set [c] represents the numbers

{0,...,c- 1}.

We frequently use the following basic inequalities:

For all n E IN,

and

(l-i- 1)n __< e _< (1 + 1) n+l

For all k, n E IN with k _< n it holds that

(nk) (en~ k

28 3. Terminology

3.2 Basic Definitions in Probability Theory

We will use many concepts from probability theory to analyze our protocols

and embedding strategies. In this section we will give a short introduction to

this theory.

Let /2 be an arbitrary nonempty set. Any element w E /2 is called

(ele-

mentary) event.

We call a function p : P(/2) -~ [0, 1]

probability measure

/2 if

- p(O) = 0 and p(w) > 0

for all w E/2,

- for any subset {wl,...,

wn} C/2

we have p((Jin__l wi) = ~in_-i

p(w,),

and

- p(/2) = 1

In this case we call (/2,p)

probability space.

A function X :/2 ~ ~ is called

random variable

on /2. X is called

non-negative

X(w) > 0

for all w e /2.

For the special case that X maps elements in/2 to {0, 1}, X is called

binary

random variable. The most important measure used in combination with

random variables is the expectation.

Definition 3.2.1 (Expectation).

Let (/2, p) denote an arbitrary probability

space and X : /2 --~ I~ be an arbitrary function. Then the

expectation

of X

is defined as

E[X]

= ~_, X(w) .p(w) .

wEg2

The following nice inequality can be shown for arbitrary random variables.

Theorem

3.2.1 (Markov Inequality).

Let X be an arbitrary non-negative

random variable with expectation #. Then, for every k > O,

Pr[Z > k] < I~

- - k "

Of special interest are binary random variables. We distinguish between

the following properties of these variables.

Definition

3.2.2.

Given n binary random variables X1,...,Xn, we call

them

negatively correlated

if for all i, k E

{1,... ,n},

and ]or all {jl,... ,jk}

{1,...,n} \

{i}

Pr[XI = 1 IX A ..... Xj~ = 1] < Pr[Xi = 1].

- positively correlated

if for all i,k e (1,... ,n}, and for all (jl,... ,jk} C

{1,...,n} \ {i}

Pr[Xi = 1 I XA ..... Xjk = 1] > Pr[Xi = 1].

3.3 Basic Definitions in Graph Theory 29

In case that equality holds, we call the random variables independent.

Usually, we want to prove results that hold with high probability. An

important tool will be the following theorem. It is a combination of results

in [AV79] and IRa88]. See also [Ho87].

Theorem 3.2.2. Let X1, . . . , X,~ be n independent binary random variables.

Let X = )-~=1Xi and I~- < E[X] _< #+ for some #_,#+ >_ O. Then it holds

for all e >_ 0 that

Pr[X > (1 + e)#+] g (1 + e) l+e (3.1)

In case that 0 < e < 1, a more careful estimation yields

Pr[X > (1 + e)#+] g e -~2~'+/2,

and in case that e > 1 we can reduce (3.1) to

Pr[X _> (1 + e)#+] _< e -~"+/3

Furthermore, it holds for all 0 < e < 1 that

Pr[X

<_ (1 - e)#_] < e -e2•-/2 _< (1 + e) l+e (3.2)

The bounds in the theorem are usually called Chernoj~-Hoe~ding bounds

or Chernoff bounds for short. For an elementary proof see [HR90]. Note that

Inequality (3.1) also holds if the X~ are negatively correlated, and Inequality

(3.2) also holds if the X, are positively correlated.

3.3 Basic Definitions in Graph Theory

In this section we introduce the basic concepts of graph theory.

A graph G = (V, E) consists of a set of nodes V and a set of edges E. The

size of G is defined as the number of nodes it contains. For all v, w E V, let

(v, w) denote a directed edge from v to w, and {v, w} denote an undirected

edge connecting v and w. G is called undirected if E C {{v,w} ] v,w E V},

and directed if E C_ {(v, w) I v, w E V}. Unless explicitly mentioned, we

assume in this book that G is undirected.

A sequence of contiguous edges in G is called a path. The length of a path

is defined as the number of edges it contains. A path is called node-simple

if it visits every node in G at most once. Similarly, it is called edge-simple

(or simple for short) if it contains every edge in G at most once. G is called

connected if, for any pair of nodes v, w E V, there is a path in G from v to

w. We call a path cycle if it starts and ends at the same node. The girth of a

30 3. Terminology

graph G is defined as the length of the shortest cycle G contains. G is called

tree

if it is connected and contains no cycle. A graph T = (V', E') is called

spanning tree

of G if V I = V, E ~ C_ E, and T is a tree. G is called

bipartite

if its node set can be partitioned into two node sets V1 and 1/2 such that

E C_ {{v,w} Iv 9 1/1, w 9 V2}.

For any pair of nodes v, w 9 V, let 5(v, w) denote the

distance

of v and w

in G, that is, the length of a shortest path from v to w. The

diameter D

of G

is defined as max{5(v, w) [ v, w 9 V}. If {v, w} 9 E then v is called

neighbor

of w. The number of neighbors of v is called the

degree

of v and denoted by

dr.

The degree of G is defined

as d = max{dr ] v 9 V}. If

all nodes in G have

the same degree then G is called

regular.

A family of graphs G = {Gn [ n 9 IN} has degree d if for all n 9 IN

the degree of

d(n).

We are mainly interested in classes of graphs with

constant degree. If it is clear to which family a graph belongs we say that this

graph has constant (or bounded) degree iff its family has constant degree.

For any subset U C_ V we define

F(U) = {v G V \ U [ 3u 9 U : {u,v} 9 E} .

G is said to have a

matching

of size k if and only if it contains k node-

disjoint edges. If a graph of size N contains a matching of size

N/2

it is

said to contain a

perfect matching.

The following result can be shown about

matchings in bipartite graphs. It's proof is similar to the proof of the well-

known Matching Theorem by Hall (see [Le92], p. 191).

Theorem 3.3.1.

Let G = (V1,V2,E) be an arbitrary bipartite graph with

IV1] ~ ]1/2].

Then G contains a matching of size

IV1]

if for any subset S C_ V1

it holds that

IF(S)[ > IS[.

The following result can be easily shown.

Theorem 3.3.2.

For any graph G with degree d, d+ 1 colors suj~ice to color

the nodes of G in such a way that no two neighbors in G have the same color.

Proof.

Suppose on the contrary that this is not possible. Then there must

exist a node in G whose neighbors already use all d + 1 colors. Since the

degree of any node can be at most d, this can not happen. 0

3.4 Basic Definitions in Routing Theory

In this section we present all parts of a model we need for studying the

performance of routing algorithms: the hardware model, the routing problem,

routing strategies, message passing models, and a model for storing routing

information.

3.4 Basic Definitions in Routing Theory 31

3.4.1 The Hardware Model

We model the topology of a network as an undirected graph G = (V, E). V

represents the computers or processors, and E represents the communication

links. We assume the communication links to work bidirectional, that is, each

edge represents two

links,

one in each direction. The

bandwidth

of a link is

defined as the number of

channels

it supports. A

packet

is defined as the

amount of data that can be sent along a channel in one time unit. Hence

the number of packets a link can forward in one time step is at most the

number of channels it supports. Unless explicitly mentioned we assume that

the bandwidth of the links is one. The

size N

of G is defined as the number

of nodes G contains.

Each node in V contains an

injection buffer

and a

delivery buffer.

The

task of the injection buffer of a node v is to store all messages v wants to

send out, and the task of the delivery buffer is to store all messages that are

destined for v. Fhrther we assume that each link has a

link buffer

(or

buffer

for short). The

size

of a buffer is defined as the maximal number of packets

a buffer can store. (Note that a message may consist of several packets.) In

the

multi-port

model each node can forward packets simultaneously along all

of its outgoing links in one time step, whereas in the

single-port

model each

node can forward packets along at most one of its outgoing links in one time

step. We only consider the multi-port model in the following, since it has

become most common for packet routing in the last years.

The following two items are important for a network to have a good

communication performance.

- The diameter should be small, since it is a lower bound for the worst-

case time necessary to send messages between pairs of nodes that have

maximal distance. If the degree is constant then the best diameter that

can be reached for a graph of size N is O(log N).

- The network should have no "bottleneck" that forces many messages to

traverse a small set of edges. The complete binary tree, for instance, is

a very bad communication network since one half of its nodes can only

communicate with the other half via its root.

In order to measure the second parameter, the bisection width or expansion

of a network is often considered. For every U, U t C_ V, let 0 = V \ U and

C(U, U ~)

be the number of edges in E that have one endpoint in U and one

endpoint in U I. The

bisection width

of G is defined as

min

C(U, U)

uc_v, lui=LIvl/2]

[UI

A more general form is the

flux

[LR88] or

expansion

of a graph G. It is defined

min

C(U, U)

ucY, iUi<iiYi/2] ]U]

32 3. Terminology

Network Topologies. The most commonly used networks in the routing

literature and in parallel computers are meshes, tori and butterflies. These

classes are defined in the following.

Definition

3.4.1 (Butterfly).

Let d E l~. The

d-dimensional butterfly

BF(d) is defined as an undirected graph with node set

V = [d + 1] • [2] 4

and an edge set E = E1 U E2 with

and

EI = {{(i,a),(i + 1, a))li e [a~, a E [2] 4 }

E2 = {((i,a),(i+1,/3)} lie [d], ~,/3E

[2] d, c~

andl3 differ

only at the ith position) .

The

d-dimensional wrap-around butterfly

W-BF(d) is defined by taking the

BF(d) and identifying level d with level O.

Figure 3.1 shows the 3-dimensional butterfly BF(3).

BF(d)

has (d + 1)2 d

nodes, 2d. 2 d edges and degree 4.

000 001 010 011 100 101 110 Ill

Fig.

3.1. The structure of BF(3).

The wrap-around butterfly is related to the following graph.

Definition

3.4.2 (Shuffle-Exchange).

Let d E ~q. The

d-dimensional

shuffle-exchange

SE(d) is defined as an undirected graph with node set V =

[2] d

and an edge set E = E1 U E2 with

E1 = {{(a4-1...a0),(a4-1...a0)} I(a4-1.--ao) E [21 d, ao = 1-ao}

and

E2 = {{(ad-1...

ao), (aoad-1... al)}l(ad-1..,

ao) e

[2] 4)

9

Figure 3.2 shows the 3- and 4-dimensional shuffle-exchange graph.

3.4 Basic Definitions in Routing Theory 33

SE(3) 100 lOl

000 0012/~ ........... rN~l lO 111

' .......... ",4

........... [/ ...........

010 Oil

9

........ 4

E 1

: _-

E 2

SE(4) 1ooo

ioo] ]1oo

11Ol

(X}~ {}(DI//~;; ~)""" ~" "" ;:];~1110 |111

9 ........ ....... r"I ...... ........ "

(}010 (}011 0110 Olll

Fig. 3.2. The structure of SE(3) and SE(4).

Definition 3.4.3 (Torus, Mesh). Let m, d 9 1~I. The (m, d)-mesh M(m, d)

is a graph with node set V = [m]d and edge set

d-1 /

E = {(aa-1...ao),(bd-1...bo)} I ai, bi 9 [m], ~Iai - bil = 1

'/=0

The (m, d)-torus T(m, d) consists 4 an (m, d)-mesh and additionally an edge

from (ad-1... ai+10 ai-1.., ao) to (ad-1... ai+l(m -- 1)ai-1... a0) for every

i 9 [a~ and aj 9 [m]. M(m, 1) is also called linear array, T(m, 1) cycle, and

M(2, d) = T(2, d) d-dimensional hypercube.

Figure 3.3 presents a linear array, a torus, and a hypercube.

0~1~2 ..... m-1

| | i

00- -10--20- -30" 110 111

, ! , ,

/I /1

I I I I

9 01- -ll--21" -31" l

I I I I

9 02- -]2--22" -32" ]1

I I I I

- 3J

..J

M(m, 1) T (4,2) M(2,3)

Fig. 3.3. The structure of M(m, 1), T(4, 2), and M(2, 3).

Next we define the class of node-symmetric graphs.

Definition 3.4.4 (Node-Symmetric Graph). A graph G = (V,E) is

called node-symmetric if for any pair of nodes u, v E V there exists an iso-

morphism qo : V -r V with qo(u) = v such that the graph G~ = (V, E~) with

E~ -- {{~(x), qo(y)} ] {x, y} 9 E} is equal to G.

34 3. Terminology

Intuitively, node-symmetry means that a graph looks the same from any

node. Node-symmetric graphs form a very general class and include most

of the standard networks such as the d-dimensional torus, the wrap-around

butterfly, the hypercube, etc. Another important class of graphs are the edge-

symmetric graphs.

Definition 3.4.5 (Edge-Symmetric Graph). A graph G = (V, E) is call-

ed edge-symmetric i] ]or any pair o] edges {u,v}, {u',v'} E E there exists an

isomorphism ~ : Y --~ Y with {~(u),~(v)} = {u',v'} such that the graph

= (y, with =

V(v)}

I v} 9 E} i, equal to a.

Note that every regular edge-symmetric graph is also node-symmetric.

The d-dimensional torus, for instance, is edge-symmetric. Another important

class of graphs are the leveled graphs.

Definition 3.4.6 (Leveled Graph). A graph G = (V, E) is called leveled

with depth D if the nodes of G can be partitioned into D + 1 levels Lo,... , LD

such that every edge in E connects nodes of consecutive levels. Nodes in level

0 are called inputs, and nodes in level D are called outputs. If, in addition,

ILol = ILDI and Lo is identified with LD, then G is called a wrapped leveled

graph with depth D.

The d-dimensional butterfly, for instance, is a leveled graph with depth

d, and the d-dimensional wrap-around butterfly is a wrapped leveled graph

with depth d. Another important class of graphs are the expanders.

Definition 3.4.7 (Expander). A graph is called expander if it has a con-

stant expansion.

Note that there exist expanders of constant degree. So far, the best ex-

panders that have an explicit construction are all node-symmetric (see, e.g.,

[LPS88, Ma88, Mo94]).

3.4.2 The Routing Problem

There are two kinds of routing problems studied in the literature: static and

dynamic routing. In case of static routing it is assumed that all messages are

given in advance, whereas in case of dynamic routing it is assumed that new

messages are continuously injected into the network. Hence within the dy-

namic routing model one is primarily interested in protocols that can sustain

a certain arrival rate of messages, whereas within the static routing model

one is primarily interested in protocols that can deliver the messages as fast

as possible. In this book we only deal with static routing problems. This type

of problems is defined as follows.

Consider an arbitrary network G with node set IN]. An instance of the

static routing problem is defined by a multi-set

3.4 Basic Definitions in Routing Theory 35

n---- {(sl,D1),...,(sn,D,)} ,

where each pair (si, Di) E IN] • (P([N]) \ {0}) represents a message that has

to be sent from node si to all nodes in D~. The following routing problems

are usually studied.

- Permutation routing: Let SN be the set of all permutations ~r : IN] -4 [N].

Given a permutation r E SN, route a message from node i to node ~r(i)

for all i 9 [N].

- h-]unction routing: Let Fh,g be the set of all h-functions f : [hi x IN] -4 IN].

Given an h-function ] 9 Fh,g, route a message from node i to node f(j, i)

for all i 9 IN] and j 9 [hi. A 1-function is simply called ]unction.

h-relation routing: An h-relation is defined as an h-function f 9 Fh,g with

If-l(i)I -- h for all i 9 IN]. Given an h-relation f 9 Fh,N, route a message

from node i to node f(j, i) for all i 9 [N] and j 9 [h].

- Broadcasting: Given a node i 9 IN], route the same message from node i

to all nodes j 9 [N].

- Gossiping: For every node i 9 IN], route the same message from node i to

all nodes j 9 [N].

- Total exchange: For every node i 9 IN], route a distinct message from node

i to node j for all j 9 IN].

The solution to a routing problem is called routing protocol. It determines for

each time step which message to forward along which link (or set of links). Its

basic component is the contention resolution rule that decides which messages

win if too many messages try to use the same link at the same time.

3.4.3 Message Passing Models

In the following we consider a message to have the following format.

header

... data...'[ routing information I source I destination I"

Fig. 3.4. The format of a message.

In a network with N nodes the source and destination need flog N 1 bits,

each, to have a unique identification number. Throughout this paper we re-

strict the routing information to be very small, namely of length at most

O(log N). It is usually needed to store information about the path a message

has to follow or the priority level of a message. It may also be used for error

detection. The routing information, source, and destination together form

the header of a message. In contrast to the header of a message, its data field

36 3. Terminology

might be of arbitrary size. Unless explicitly mentioned, we assume in the fol-

lowing that the data fields of all messages that have to be routed according

to some routing problem 7~ are of the same size. In this book, we study the

following two models: the

store-and-forward routing

model and the

wormhole

routing

model.

Store-and-Forward Routing. The most commonly used and well under-

stood routing model in the literature is the store-and-forward routing model.

In this model time is partitioned into synchronous

steps.

One step is defined

as the time a message needs to be sent along a link. (It is usually assumed

that every link needs the same amount of time to forward a message. Fur-

thermore, internal computations of processors are usually not counted as time

steps as long as they are bounded by some small polynomial, since it is often

assumed that the time to send a message Mong a link is much higher than the

time needed to execute internal instructions.) A node must store an entire

message before it can forward any part of the message along the next link on

its route. Hence messages can be viewed as single packets.

Wormhole Routing. In wormhole routing, messages are sent as

worms,

each of which consists of a sequence of fixed size packets called

flits.

A flit is

defined as the amount of data that can be sent along a channel in one time

step. The

length

of a worm is the number of flits it contains. We call the first

flit of a worm

head

and the remaining flits

body.

The first flits of a worm store

the header and the remaining flits the data field of a message. In order to

keep the routing hardware in a node small, the capacity of each link to buffer

flits is usually limited to at most one per outgoing channel. Because a link

can not identify which worm a flit belongs to from its contents, the flits of

a worm must arrive on the incoming channel in a contiguous fashion. Since

each channel can only buffer one flit of a worm, if the head of a worm can

not advance then the flits following the head must stall.

Note that

circuit-switching

(i.e., establishing a connection between pairs

of nodes in a network) can be viewed as a special case of wormhole routing

in which the length of each worm is at least as large as the distance between

the worm's source and its destination.

3.4.4 Routing Strategies

We distinguish between two kinds of protocols:

Offtine

protocols and

online

protocols. In case of offline protocols, we allow all processors of a parallel

system to have complete knowledge about the routing problem. This enables

them in principle to develop an optimal strategy for sending the messages

to their destinations (note that we do not count internal computations, but

only communication rounds). In this area, important questions are, how fast

such a strategy can be, and whether (asymptotically) optimal strategies can

be computed in polynomial time. Note that offline protocols are also referred

to as

global control

centralized protocols.