Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
11 Randomly Wired Multistage Networks
11 Randomly Wired Multistage Networks
Pages 161-174
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 161... ...
Finally, and perhaps most importantly, they are highly fault tolerant. 11.1 Introduction Networks derived from hypercubes form the architectural basis of most paralle!
|
From page 162... ...
. 11.~.2 Delta Networks Butterfly and dilated butterfly networks belong to a larger class of networks called delta networks (see, e.g., Kruskal and Snir, 1986~.
|
From page 163... ...
In general, however, each switch may have several up- and down-edges, say of each, and each step of the logical path can be taken on any one of d edges. , ~u Il.~.3 Multibutterflies A ct-dilated butterfly can be thought of as ~ butterflies that are merged together by merging switches that have the same row and level numbers.
|
From page 164... ...
In fact, it now appears as though randomly wired multibutterfly networks V.~.' .~^V^~VV~^J ^~- ~V`~ u`L~`ll`~~)
|
From page 165... ...
Furthermore, the constructionsin §511.3 through 11.5 require ,3 > a,/2, but, at present, there are no known deterministic algorithms for constructing splitters with this much expansion in polynomial time. Splitters with expansion are good for routing because one must block Ok splitter outputs in order to block k- splitter inputs.
|
From page 166... ...
Finally, §11.5 sketches an algorithm for establishing connections in a randomly wired nonblocking network. ll.2 Packet Switching In a one-to-one packet-routing problem, each input sends a packet to a distinct output.
|
From page 167... ...
-bit-step algorithm for circuit switching on multibutterfly networks. The only previously known O(Iog N)
|
From page 168... ...
time for every path to be extended before it begins the extension at the next level. Instead, it executes path extension steps until the number of unextended paths fadIs to some fraction p of its original value, where p is a fixed constant that depends on d.
|
From page 169... ...
~ order to prevent placeholders from multiplying too rapidly and clogging the system because if the fraction of inputs'of a splitter that are trying to extend rises above cr. the path extension algorithm ceases to work-we need to ensure that as stalled paths get extended, they send cancellation signals to the placeholding nodes ahead of them to tell them they are not needed anymore.
|
From page 170... ...
Next, working from level log N back to level 0, each switch is examined in the fault propagation stage to see if at least half of its upper outputs lead to faulty switches that have not been erased or if at least half of its lower outputs lead to faulty switches that have not been erased. If so, then the switch is declared faulty (but not erased)
|
From page 171... ...
As shown in Figure 11.6, a multi-Banes network is essentially a reversed multibutterfly followed by a multi butterfly. As in the circuit-switching algorithm, the network must be lightly loaded by some fixed constant factor I;, where ~ > 1/c.
|
From page 172... ...
The basic idea is to treat the switches through which paths have already been established as if they were faulty and to apply the fault propagation techniques from §11.4 to the network. In particular, we define a node to be busy if there is a path currently routing through it, and we recursively define a node to be "blocked" according to the following rule.
|
From page 173... ...
29th Annual Symposium on Foundations of Computer Science, {EKE Computer Society Press, [os Alamitos, Cadif., 221-230. Kruskal, C.P., and M
|
From page 174... ...
Slst Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 264-274. Leighton, T., C.~.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.