Date: February 1, 2001
"Wir müssen wissen, wir werden wissen" (We must know, we shall know)
--- David Hilbert
On the other hand,
: A graph of processors. Packets can be sent on edges.
: The vertices (i.e., processors) of .
, and is a hypercube. Each processes is a binary string .
Question: Given a permutation , how to send the permutation and create minimum delay?
How do we sent a packet? We use bit fixing. Namely, the packet from the node, always go to the current adjacent node that have the first different bit as we scan the destination string . For example, packet from going to , would pass through , , .
We assume each edge have a FIFO queue. Here is the algorithm:
We analyze only (i) as (iii) follows from the same analysis. - the route taken by in (i).
- 1 if share an edge, 0 otherwise. Total delay for is . Note, that for a fixed , the variables are independent (not however, that are not independent!). , let be the number of routes that pass through .