Network Topologies, Models, and Applications | p. 1 |
Parallel Systems | p. 1 |
Programming Paradigms | p. 8 |
Parallelizing Compilers | p. 10 |
General Run Time Optimizations | p. 10 |
Message Passing Model | p. 12 |
Data Parallel Model | p. 13 |
Shared Memory Model | p. 14 |
Theoretical Models | p. 23 |
Parallel Communication Models | p. 23 |
Parallel Computation Models | p. 27 |
Program Locality and Latency Hiding | p. 28 |
Customization of Interconnection Networks | p. 31 |
Network Partitioning | p. 33 |
Amdahl's Law | p. 34 |
Superlinear Speedup | p. 35 |
Parallel Benchmarks | p. 35 |
Network Communications | p. 37 |
Routing Strategies | p. 37 |
What is a Packet? | p. 37 |
Virtual Circuits - Flow Control | p. 39 |
Routing Strategies | p. 41 |
Routing Functions | p. 42 |
Deadlock, Livelock, and Starvation | p. 45 |
Fault Tolerance, Reliability, and Diagnosis Models | p. 50 |
Communication Patterns | p. 59 |
General Routing | p. 60 |
Permutation Routing | p. 61 |
Isotonic Routing | p. 65 |
Other Communication Patterns | p. 65 |
Embedding Relations | p. 66 |
Reduction of Communication Problems | p. 69 |
Routing in General Graphs | p. 70 |
Performance of Routing Algorithms | p. 70 |
Fault Tolerant Routing | p. 77 |
PRAM Emulation on Distributed Memory | p. 78 |
Optimality and Lower Bounds | p. 79 |
Performance of Packet Routers | p. 80 |
Continuous Routing Models | p. 82 |
Input Buffered Switch | p. 83 |
Split Input Buffered Switch | p. 84 |
Output Buffered Switch | p. 86 |
Central Buffered Switch | p. 87 |
Performance Comparisons for Generic Switches | p. 88 |
Large Routers and Networks | p. 92 |
Technological Constraints - Cost vs. Performance | p. 94 |
Multistage Interconnection Networks | p. 95 |
Definitions | p. 95 |
Representation and Functionalities of Multistage Networks | p. 97 |
Design and Classification of MINs | p. 100 |
Blocking Networks | p. 106 |
Shuffle-Exchange and Omega Network | p. 106 |
Butterfly Network | p. 109 |
Inverse Omega, Baseline, Indirect Cube, etc. | p. 110 |
MIN Performance - Static and Dynamic Patterns | p. 115 |
Permutation Capability - Static Traffic | p. 115 |
Bandwidth and Latency - Dynamic Traffic | p. 117 |
Permutation and Nonblocking Networks | p. 121 |
Benes Permutation Network | p. 121 |
Other Permutation Networks | p. 125 |
The Clos Family of Networks | p. 125 |
Other Nonblocking Networks | p. 129 |
Generalized Connectors | p. 130 |
Fault Tolerance, Reliability, and Diagnosis | p. 135 |
Fault Tolerance and Reliability | p. 135 |
Fault Diagnosis Models | p. 140 |
Special Purpose Networks | p. 142 |
Sorting Networks | p. 142 |
Combining Networks | p. 148 |
Prefix Circuits | p. 152 |
Balancing and Counting Networks | p. 152 |
Interconnection Networks in Cryptology | p. 154 |
Shared Memory Algorithms | p. 154 |
VLSI Layout and Customization | p. 155 |
Commercial Multistage Systems | p. 155 |
Hypercube Networks | p. 159 |
Topological Properties | p. 159 |
Hypercube Communication and Sorting | p. 164 |
Online Permutation Routing | p. 164 |
Offline Permutation Routing | p. 169 |
Sorting Algorithms | p. 171 |
Global Communications | p. 174 |
Global Communications with Linear Model | p. 177 |
Dynamic Routing Problems | p. 181 |
Fault Tolerant Routing | p. 182 |
Cut-Through, Wormhole, Circuit Switching, and Hot-Potato Routing | p. 190 |
Hypercube Embeddings and Algorithms | p. 191 |
Allocation and Scheduling Strategies | p. 196 |
VLSI Layout and Customization | p. 202 |
Commercial Hypercube Systems | p. 204 |
Mesh Networks | p. 207 |
Topological Properties | p. 207 |
Meshes and Tori | p. 209 |
Indexings | p. 211 |
Communication Models | p. 212 |
Connection Conflicts | p. 214 |
Remarks | p. 214 |
One-Dimensional Arrays | p. 215 |
Lower Bounds for Routing and Sorting on Arrays | p. 216 |
Basic Lemmas | p. 217 |
Routing Randomizations | p. 221 |
k-k Routing | p. 222 |
Sorting | p. 228 |
Two-Dimensional Arrays | p. 230 |
Online Routing | p. 230 |
Offline Routing | p. 246 |
Dynamic Routing Problems | p. 247 |
Fault Tolerant Routing | p. 248 |
Cut-Through - Wormhole - Hot-Potato Routing | p. 250 |
1-1 and k-k Sorting Algorithms | p. 252 |
Global Communications and Algorithms | p. 267 |
Mesh-Like Networks | p. 268 |
Higher Dimensional Arrays | p. 268 |
Bus-Based Meshes | p. 269 |
Meshes with Diagonals | p. 273 |
Coated Mesh | p. 273 |
Allocation and Scheduling Strategies | p. 274 |
VLSI Layout and Customization | p. 276 |
Commercial Mesh Systems | p. 276 |
Other Parallel Networks | p. 281 |
De Bruijn Networks | p. 282 |
Shuffle-Exchange Digraphs | p. 297 |
Circulant Networks | p. 302 |
Cayley Graphs | p. 308 |
Fat-Tree Networks | p. 317 |
Future Trends in Parallel Communication | p. 319 |
Bibliography | p. 325 |
Index | p. 383 |
Table of Contents provided by Syndetics. All Rights Reserved. |