Routing in Parallel Computers

The problem we shall discuss here is of routing message packets in a parallel computer, which we model as a directed graph: each vertex is a processor, and each edge is a one-way communication link. We suppose this system is synchronous, and that at most one packet can be sent on a link per time step. Thus, if several packets are routed through a certain link at the same time, a queue will result, and there will be delays. We want to minimize delays with routing strategies that can be implemented in a distributed sense. We follow the presentation in Motwani and Raghavan's book Randomized Algorithms , and begin with a common topology in parallel computers and some general concepts.

Definition 13453

Let the n-dimensional hypercube be the graph where the vertex set is the set of bit-strings of length n, and where there are directed edges between two vertices if they differ in exactly one bit.

Let the route of a packet be the path it takes from its origin to its destination. We call a routing strategy oblivious if this route is a function only of the origin and the destination. For a hypercube, we can easily find an oblivious routing strategy:

Definition 13462

We shall do oblivious routing in the hypercube as follows: Let i be the origin and d the destination of a packet p. Notice that in the hypercube, by flipping a bit of a vertex, we get an adjacent vertex. So consider the bits where i and d differ. We get a path from i to d by flipping each of these differing bits, one at a time. Let the route of p be the path that results from flipping these bits in order.

For this strategy we have a simple lemma:

Lemma 13469

  Let $\rho _1$ and $\rho _2$ be the routes of two packets. $\rho _1$ and $\rho _2$ may have a common (directed) subpath. However, once $\rho _1$ and $\rho _2$ separate, they do not rejoin.

Proof. Let $\rho _1$ and $\rho _2$ have the edge e = (u,v) in common. Let (v, w₁) be the next edge in $\rho _1$ and let (v, w₂) be the next edge in $\rho _2$. Going to w₁ means flipping a bit in v at some position b₁, and going to w₂ means flipping a bit in v at some position b₂. If $w_1 \neq w_2$, then $b_1 \neq b_2$. Let b be the minimum of b₁ and b₂. Then w₁ and w₂ differ at position b, and neither in $\rho _1$ nor in $\rho _2$ will there be any later change in this position.$\Box$

We now turn to a specific problem.

Definition 13498

In the permutational routing problem, a graph is given along with a permutation $\Pi$ of its vertices. At each vertex i, there is a packet p_i with destination $d_i = \Pi (i)$.

Theorem 13501 (Valiant and Brebner)

  For the permutational routing problem on hypercubes, there is a randomized oblivious strategy taking O(n) steps, where n is the dimension of the hypercube.

Proof. The protocol works as follows: Each vertex i picks, for its packet, an intermediate destination $\sigma _i$ at random. Then, in a first phase, p_i (with the final destination attached) is sent to $\sigma _i$ with the oblivious routing strategy described above for hypergraphs. In a second phase, using the same strategy, p_i is sent on to d_i. However, $\sigma _i$ is not instructed to forward p_i immediately, but to wait (probably) until some time when it is almost certain that all other packets have also reached their intermediate destinations. (Provided they have, phase one and phase two will not interfere.)

In the following lemmas, we analyze an arbitrary phase under the assumption that the other phase does not interfere.

Lemma 13521

  For each i, let $\rho _i$ be the route of p_i in the concerned phase. Then, for a particular i, let S be the set of packets, other than p_i, whose routes have at least one edge in common with $\rho _i$. Obviously, these are the only packets that can delay p_i on its route $\rho _i$. In fact, the delay incurred by p_i is at most |S|.

Proof. Let $(e_1, \dots , e_k)$ be the sequence of edges in $\rho _i$, and let the routing start at time 1. Then, as long as p_i is not delayed, it traverses e_t at time t. Naturally therefore, if p_i is waiting to traverse e_j at time t, we define its lag at t to be t-j. To facilitate the following argument, we make the same definition for packets in S. Also for a packet in S, we say that it leaves $\rho _i$ when it traverses an edge of $\rho _i$ for the last time. Notice that the lag of p_i is zero initially, and that the total delay incurred by p_i is its lag when it traverses e_k.

We now prove the lemma by showing that for each increase in the lag of p_i, there is at least one packet in S that leaves $\rho _i$ (and, by definition, does not come back). So assume that the lag of p_i has just increased from l to l+1. Thus there is some packet in S that just traversed the edge that p_i is in line for. This traversal occurred with lag l.

Let t be the last time step at which there is a packet in S with lag l. Thus there is a packet $p \in S$ traversing an edge e_j with lag l at time t. The next edge in the route of p cannot be e_j+1 though, since then p or some other packet in S would traverse e_j+1 at time t+1, obviously with lag l, and thus contradicting our assumption about t. According to Lemma  14.1, e_j therefore is the last edge in the route of p that is also in $\rho _i$. In other words, $p \in S$ leaves $\rho _i$, and it does so with lag l. $\Box$

Lemma 13576

  For an edge e, let T(e) be the number of routes (in the concerned phase) that pass through e. Then, the expected value of T(e), , is 1/2.

Proof. We let n be the dimension of the hypercube. The number of vertices is N=2ⁿ, and the number of edges (directed) is Nn. Since intermediate destinations are just random bit strings, the expected length of a route is n/2, and the expected total route length is Nn/2. By symmetry, is independent of e. It follows that $\ensuremath{\mathrm{E} [T(e)]} = 1/2$. $\Box$

Lemma 13588

  With probability at least 1 - 2^-2n, every packet reaches its destination (in the concerned phase) in at most 4n steps.

Proof. For each i, let $\rho _i$ be the route of p_i. Also let H_ij be 1 if $\rho _i$ and $\rho _j$ have some edge in common, and 0 otherwise. Then, for a given i, Lemma  14.2 shows that the delay incurred by p_i is at most $H = \sum _{j \neq i} H_{ij}$. To study this sum, we begin by fixing $\sigma _i$. Then, the terms of H are mutually independent, and we can apply the Chernoff bound. With $\mu$ denoting the expectancy of H, we have, for any $\delta \gt$:

$$\ensuremath{\mathrm{Pr} [H \gt (1+\delta)\mu]} < \left[ \f... ...} < \left[ \frac {e}{(1+\delta)} \right] ^ {(1+\delta)\mu}.$$

For $1+\delta \gt 2e$, we get the simpler form

$$\ensuremath{\mathrm{Pr} [H \gt (1+\delta)\mu]} < 2^ {-(1+\delta)\mu}.$$

Differently stated, $\ensuremath{\mathrm{Pr} [H \gt \Delta]} < 2^ {-\Delta}$, provided that $\Delta / \mu \gt 2e$.

We therefore bound $\mu = \ensuremath{\mathrm{E} [H]}$. For an edge e, let T'(e) be the number of routes, other than $\rho _i$, that pass through e. Then

$$H = \sum _{j \neq i} H_{ij} \leq \sum _{e \in \rho _i} T'(e).$$

The expectancy (with $\rho _i$ fixed) of T'(e) is less than the expectancy (with respect to $\rho _i$ also) of T(e), defined in Lemma  14.3, so

$$\mu = \ensuremath{\mathrm{E} [H]} \leq \sum _{e \in \rho _i}... ...th{\mathrm{E} [T'(e)]} < \sum _{e \in \rho _i} 1/2 \leq n/2.$$

Hence, $\Delta = 3n$ satisfies $\Delta / \mu \gt 2e$, and we can say that $\ensuremath{\mathrm{Pr} [H \gt 3n]} < 2^ {-3n}$. That is, we have shown that the probability that packet p_i is delayed more than 3n time units is less than 2^-3n. Since there are 2ⁿ packets altogether, we find that with probability at least 1 - 2^-2n, no packet is delayed more than 3n time units, or equivalently, needs more than 4n time units to complete its route. $\Box$

To complete the proof of Theorem  14.1, we define that vertices shall wait until 4n steps have elapsed before they start phase 2. Lemma  14.4 then shows that all packets will complete both phases in at most 8n steps with probability at least 1 - 2^1-2n, that is, at least 1 - 1/N, where N=2ⁿ is the number of vertices in the hypercube.$\Box$