Great Deals on Used Textbooks & New Textbooks!               
My Account | Help Desk | Market Place Shopping Cart
Free shipping. Click here for details.
No items in cart.
Total: $0.00
Textbooks Sell Textbooks Books Supplies Medical Books College Apparel Movies Clearance
Search  Advanced >>
Principles and Practices of Interconnection Networks,9780122007514
Other versions by this Author
We Buy This Book Back!
Details>>

Principles and Practices of Interconnection Networks


Author(s): Dally; Towles
ISBN10:  0122007514
ISBN13:  9780122007514
Format:  Hardcover
Pub. Date:  12/18/2003
Publisher(s): Elsevier Science & Technology

Buy in Bulk
Send to a friend
New Price  $60.80
List Price $77.95
eVIP Price  $57.76
New Copy:  Usually Ships in 3-4 Business Days
add remove
eBook Price $78.15
What is an eBook? 		Add eBook to Cart
Electronic Copy: Will be Delivered Electronically
Marketplace Price $61.33
List Price $77.95 Available in the eCampus Marketplace
Take 90 Days to Pay on $250 or more
with Quick, Easy, Secure
Subject to credit approval.
SummaryTable of Contents
One of the greatest challenges faced by designers of digital systems is optimizing the communication and interconnection between system components. Interconnection networks offer an attractive and economical solution to this communication crisis and are fast becoming pervasive in digital systems. Current trends suggest that this communication bottleneck will be even more problematic when designing future generations of machines. Consequently, the anatomy of an interconnection network router and science of interconnection network design will only grow in importance in the coming years.

This book offers a detailed and comprehensive presentation of the basic principles of interconnection network design, clearly illustrating them with numerous examples, chapter exercises, and case studies. It incorporates hardware-level descriptions of concepts, allowing a designer to see all the steps of the process from abstract design to concrete implementation.

·Case studies throughout the book draw on extensive author experience in designing interconnection networks over a period of more than twenty years, providing real world examples of what works, and what doesn't.

·Tightly couples concepts with implementation costs to facilitate a deeper understanding of the tradeoffs in the design of a practical network.

·A set of examples and exercises in every chapter help the reader to fully understand all the implications of every design decision.
Acknowledgments xvii
Preface xix
About the Authors xxv
Chapter 1 Introduction to Interconnection Networks 1(24)
1.1 Three Questions About Interconnection Networks
2(2)
1.2 Uses of Interconnection Networks
4(9)
1.2.1 Processor-Memory Interconnect
5(3)
12.2 I/O Interconnect
8(3)
1.2.3 Packet switching Fabric
11(2)
1.3 Network Basics
13(8)
1.3.1 Topology
13(3)
1.3.2 Routing
16(1)
1.3.3 Flow Control
17(2)
1.3.4 Router Architecture
19(1)
1.3.5 Performance of Interconnection Networks
19(2)
1.4 History
21(2)
1.5 Organization of this Book
23(2)
Chapter 2 A simple Interconnection Network 25(20)
2.1 Network Specifications and Constraints
25(2)
2.2 Topology
27(4)
2.3 Routing
31(1)
2.4 Flow Control
32(1)
2.5 Router Design
33(3)
2.6 Performance Analysis
36(6)
2.7 Exercises
42(3)
Chapter 3 Topology Basics 45(30)
3.1 Nomenclature
46(4)
3.1.1 Channels and Nodes
46(1)
3.1.2 Direct and Indirect Networks
47(1)
3.1.3 Cuts and Bisections
48(1)
3.1.4 Paths
48(1)
3.1.5 Symmetry
49(1)
3.2 Traffic Patterns
50(1)
3.3 Performance
51(9)
3.3.1 Throughput and Maximum Channel Load
51(4)
3.3.2 Latency
55(2)
3.3.3 Path Diversity
57(3)
3.4 Packaging Cost
60(4)
3.5 Case Study: The SGI Origin 2000
64(5)
3.6 Bibliographic Notes
69(1)
3.7 Exercises
69(6)
Chapter 4 Butterfly Networks 75(14)
4.1 The Structure of Butterfly Networks
75(2)
4.2 Isomorphic Butterflies
77(1)
4.3 Performance and Packaging Cost
78(3)
4.4 Path Diversity and Extra stages
81(3)
4.5 Case Study: The BBN Butterfly
84(2)
4.6 Bibliographic Notes
86(1)
4.7 Exercises
86(3)
Chapter 5 Torus Networks 89(22)
5.1 The Structure of Torus Networks
90(2)
5.2 Performance
92(6)
5.2.1 Throughput
92(3)
5.2.2 Latency
95(1)
5.2.3 Path Diversity
96(2)
5.3 Building Mesh and Torus Networks
98(2)
5.4 Express Cubes
100(2)
5.5 Case Study: The MIT J-Machine
102(4)
5.6 Bibliographic Notes
106(1)
5.7 Exercises
107(4)
Chapter 6 Non-Blocking Networks 111(34)
6.1 Non-Blocking vs. Non-Interfering Networks
112(1)
6.2 Crossbar Networks
112(4)
6.3 Clos Networks
116(18)
6.3.1 structure and Properties of Clos Networks
116(2)
6.3.2 Unicast Routing on strictly Non-Blocking Clos Networks
118(4)
6.3.3 Unicast Routing on Rearrangeable Clos Networks
122(4)
6.3.4 Routing Clos Networks Using Matrix Decomposition
126(2)
6.3.5 Multicast Routing on Clos Networks
128(5)
6.3.6 Clos Networks with More Than Three stages
133(1)
6.4 Benes Networks
134(1)
6.5 Sorting Networks
135(2)
6.6 Case Study: The Velio VC2002 (Zeus) Grooming switch
137(5)
6.7 Bibliographic Notes
142(1)
6.8 Exercises
142(3)
Chapter 7 Slicing and Dicing 145(14)
7.1 Concentrators and Distributors
146(3)
7.1.1 Concentrators
146(2)
7.1.2 Distributors
148(1)
7.2 Slicing and Dicing
149(4)
7.2.1 Bit slicing
149(2)
7.2.2 Dimension slicing
151(1)
7.2.3 Channel slicing
152(1)
7.3 Slicing Multistage Networks
153(2)
7.4 Case Study: Bit Slicing in the Tiny Tera
155(2)
7.5 Bibliographic Notes
157(1)
7.6 Exercises
157(2)
Chapter 8 Routing Basics 159(14)
8.1 A Routing Example
160(2)
8.2 Taxonomy of Routing Algorithms
162(1)
8.3 The Routing Relation
163(1)
8.4 Deterministic Routing
164(4)
8.4.1 Destination-Tag Routing in Butterfly Networks
165(1)
8.4.2 Dimension-Order Routing in Cube Networks
166(2)
8.5 Case Study: Dimension-Order Routing in the Cray T3D
168(2)
8.6 Bibliographic Notes
170(1)
8.7 Exercises
171(2)
Chapter 9 Oblivious Routing 173(16)
9.1 Valiant's Randomized Routing Algorithm
174(2)
9.1.1 Valiant's Algorithm on Torus Topologies
174(1)
9.1.2 Valiant's Algorithm on Indirect Networks
175(1)
9.2 Minimal Oblivious Routing
176(4)
9.2.1 Minimal Oblivious Routing on a Folded Clos (Fat Tree)
176(2)
9.2.2 Minimal Oblivious Routing on a Torus
178(2)
9.3 Load-Balanced Oblivious Routing
180(1)
9.4 Analysis of Oblivious Routing
180(3)
9.5 Case Study: Oblivious Routing in the Avici Terabit Switch Router(TSR)
183(3)
9.6 Bibliographic Notes
186(1)
9.7 Exercises
187(2)
Chapter 10 Adaptive Routing 189(14)
10.1 Adaptive Routing Basics
189(3)
10.2 Minimal Adaptive Routing
192(1)
10.3 Fully Adaptive Routing
193(2)
10.4 Load-Balanced Adaptive Routing
195(1)
10.5 Search-Based Routing
196(1)
10.6 Case Study: Adaptive Routing in the Thinking Machines CM-5
196(5)
10.7 Bibliographic Notes
201(1)
10.8 Exercises
201(2)
Chapter 11 Routing Mechanics 203(18)
11.1 Table-Based Routing
203(8)
11.1.1 Source Routing
204(4)
11.1.2 Node-Table Routing
208(3)
11.2 Algorithmic Routing
211(1)
11.3 Case Study: Oblivious Source Routing in the IBM Vulcan Network
212(5)
11.4 Bibliographic Notes
217(1)
11.5 Exercises
217(4)
Chapter 12 Flow Control Basics 221(12)
12.1 Resources and Allocation Units
222(3)
12.2 Bufferless Flow Control
225(3)
12.3 Circuit switching
228(2)
12.4 Bibliographic Notes
230(1)
12.5 Exercises
230(3)
Chapter 1 3 Buffered Flow Control 233(24)
13.1 Packet-Buffer Flow Control
234(3)
13.2 Flit-Buffer Flow Control
237(8)
13.2.1 Wormhole Flow Control
237(2)
13.2.2 Virtual-Channel Flow Control
239(6)
13.3 Buffer Management and Backpressure
245(6)
13.3.1 Credit-Based Flow Control
245(2)
13.3.2 On/Off Flow Control
247(2)
13.3.3 Ack/Nack Flow Control
249(2)
13.4 Flit-Reservation Flow Control
251(5)
13.4.1 A Flit-Reservation Router
252(1)
13.4.2 Output scheduling
253(2)
13.4.3 Input scheduling
255(1)
13.5 Bibliographic Notes
256(1)
13.6 Exercises
256(1)
Chapter 14 Deadlock and Livelock 257(28)
14.1 Deadlock
258(5)
14.1.1 Agents and Resources
258(1)
14.1.2 Wait-For and Holds Relations
259(1)
14.1.3 Resource Dependences
260(1)
14.1.4 Some Examples
260(2)
14.1.5 High-Level (Protocol) Deadlock
262(1)
14.2 Deadlock Avoidance
263(9)
14.2.1 Resource Classes
263(4)
14.2.2 Restricted Physical Routes
267(3)
14.2.3 Hybrid Deadlock Avoidance
270(2)
14.3 Adaptive Routing
272(5)
14.3.1 Routing Subfunctions and Extended Dependences
272(4)
14.3.2 Duato's Protocol for Deadlock-Free Adaptive Algorithms
276(1)
14.4 Deadlock Recovery
277(2)
14.4.1 Regressive Recovery
278(1)
14.4.2 Progressive Recovery
278(1)
14.5 Livelock
279(1)
14.6 Case Study: Deadlock Avoidance in the Cray T3E
279(2)
14.7 Bibliographic Notes
281(1)
14.8 Exercises
282(3)
Chapter 15 Quality of service 285(20)
15.1 Service Classes and Service Contracts
285(2)
15.2 Burstiness and Network Delays
287(3)
15.2.1 (sigma,rho) Regulated Flows
287(1)
15.2.2 Calculating Delays
288(2)
15.3 Implementation of Guaranteed services
290(4)
15.3.1 Aggregate Resource Allocation
291(1)
15.3.2 Resource Reservation
292(2)
15.4 Implementation of Best-Effort services
294(3)
15.4.1 Latency Fairness
294(2)
15.4.2 Throughput Fairness
296(1)
15.5 Separation of Resources
297(2)
15.5.1 Tree saturation
297(2)
15.5.2 Non-interfering Networks
299(1)
15.6 Case Study: ATM Service Classes
299(1)
15.7 Case Study: Virtual Networks in the Avici TSR
300(2)
15.8 Bibliographic Notes
302(1)
15.9 Exercises
303(2)
Chapter 16 Router Architecture 305(20)
16.1 Basic Router Architecture
305(5)
16.1.1 Block Diagram
305(3)
16.1.2 The Router Pipeline
308(2)
16.2 Stalls
310(2)
16.3 Closing the Loop with Credits
312(1)
16.4 Reallocating a Channel
313(3)
16.5 Speculation and Lookahead
316(3)
16.6 Flit and Credit Encoding
319(2)
16.7 Case study: The Alpha 21364 Router
321(3)
16.8 Bibliographic Notes
324(1)
16.9 Exercises
324(1)
Chapter 17 Router Datapath Components 325(24)
17.1 Input Buffer Organization
325(9)
17.1.1 Buffer Partitioning
326(2)
17.1.2 Input Buffer Data structures
328(5)
17.1.3 Input Buffer Allocation
333(1)
17.2 Switches
334(9)
17.2.1 Bus Switches
335(3)
17.2.2 Crossbar Switches
338(4)
17.2.3 Network switches
342(1)
17.3 Output Organization
343(1)
17.4 Case Study: The Datapath of the IBM Colony Router
344(3)
17.5 Bibliographic Notes
347(1)
17.6 Exercises
348(1)
Chapter 18 Arbitration 349(14)
18.1 Arbitration Timing
349(2)
18.2 Fairness
351(1)
18.3 Fixed Priority Arbiter
352(2)
18.4 Variable Priority Iterative Arbiters
354(4)
18.4.1 Oblivious Arbiters
354(1)
18.4.2 Round-Robin Arbiter
355(1)
18.4.3 Grant-Hold Circuit
355(2)
18.4.4 Weighted Round-Robin Arbiter
357(1)
18.5 Matrix Arbiter
358(2)
18.6 Queuing Arbiter
360(2)
18.7 Exercises
362(1)
Chapter 19 Allocation 363(26)
19.1 Representations
363(3)
19.2 Exact Algorithms
366(1)
19.3 Separable Allocators
367(6)
19.3.1 Parallel Iterative Matching
371(1)
19.3.2 iSLIP
371(1)
19.3.3 Lonely Output Allocator
372(1)
19.4 Wavefront Allocator
373(3)
19.5 Incremental vs. Batch Allocation
376(2)
19.6 Multistage Allocation
378(2)
19.7 Performance of Allocators
380(3)
19.8 Case Study: The Tiny Tera Allocator
383(2)
19.9 Bibliographic Notes
385(1)
19.10 Exercises
386(3)
Chapter 20 Network Interfaces 389(22)
20.1 Processor-Network Interface
390(4)
20.1.1 Two-Register Interface
391(1)
20.1.2 Register-Mapped Interface
392(1)
20.1.3 Descriptor-Based Interface
393(1)
20.1.4 Message Reception
393(1)
20.2 Shared-Memory Interface
394(6)
20.2.1 Processor-Network Interface
395(2)
20.2.2 Cache Coherence
397(1)
20.2.3 Memory-Network Interface
398(2)
20.3 Line-Fabric Interface
400(3)
20.4 Case Study: The MIT M-Machine Network Interface
403(4)
20.5 Bibliographic Notes
407(1)
20.6 Exercises
408(3)
Chapter 21 Error Control 411(16)
21.1 Know Thy Enemy: Failure Modes and Fault Models
411(3)
21.2 The Error Control Process: Detection, Containment, and Recovery
414(1)
21.3 Link Level Error Control
415(6)
21.3.1 Link Monitoring
415(1)
21.3.2 Link-Level Retransmission
416(3)
21.3.3 Channel Reconfiguration, Degradation, and shutdown
419(2)
21.4 Router Error Control
421(1)
21.5 Network-Level Error Control
422(1)
21.6 End-to-end Error Control
423(1)
21.7 Bibliographic Notes
423(1)
21.8 Exercises
424(3)
Chapter 22 Buses 427(22)
22.1 Bus Basics
428(4)
22.2 Bus Arbitration
432(4)
22.3 High Performance Bus Protocol
436(5)
223.1 Bus Pipelining
436(2)
22.3.2 Split-Transaction Buses
438(1)
22.3.3 Burst Messages
439(2)
22.4 From Buses to Networks
441(2)
22.5 Case Study: The PCI Bus
443(3)
22.6 Bibliographic Notes
446(1)
22.7 Exercises
446(3)
Chapter 23 Performance Analysis 449(24)
23.1 Measures of Interconnection Network Performance
449(11)
23.1.1 Throughput
452(3)
23.1.2 Latency
455(1)
23.1.3 Fault Tolerance
456(1)
23.1.4 Common Measurement Pitfalls
456(4)
23.2 Analysis
460(7)
23.2.1 Queuing Theory
461(4)
23.2.2 Probabilistic Analysis
465(2)
23.3 Validation
467(1)
23.4 Case Study: Efficiency and Loss in the BBN Monarch Network
468(2)
23.5 Bibliographic Notes
470(1)
23.6 Exercises
471(2)
Chapter 24 Simulation 473(22)
24.1 Levels of Detail
473(2)
24.2 Network Workloads
475(3)
24.2.1 Application-Driven Workloads
475(1)
24.2.2 Synthetic Workloads
476(2)
24.3 simulation Measurements
478(6)
24.3.1 Simulator Warm-Up
479(2)
24.3.2 Steady-State sampling
481(1)
24.3.3 Confidence Intervals
482(2)
24.4 simulator Design
484(7)
24.4.1 Simulation Approaches
485(3)
24.4.2 Modeling Source Queues
488(2)
24.4.3 Random Number Generation
490(1)
24.4.4 Troubleshooting
491(1)
24.5 Bibliographic Notes
491(1)
24.6 Exercises
492(3)
Chapter 25 Simulation Examples 495(16)
25.1 Routing
495(5)
25.1.1 Latency
496(3)
25.1.2 Throughput Distributions
499(1)
25.2 Flow Control Performance
500(8)
25.2.1 Virtual Channels
500(2)
25.2.2 Network size
502(1)
25.2.3 Injection Processes
503(2)
25.2.4 Prioritization
505(2)
25.2.5 Stability
507(1)
25.3 Fault Tolerance
508(3)
Appendix A Nomenclature 511(4)
Appendix B Glossary 515(6)
Appendix C Network Simulator 521(2)
Bibliography 523(16)
Index 539

Check Out These Items!
eCampus.com Pink Backpack eCampus.com Pink Backpack
Retail Price $28.95
Our Price $10.00 		eCampus.com T-Shirt eCampus.com T-Shirt
Retail Price $14.99
Our Price $2.00 		eCampus.com 4GB USB Drive eCampus.com 4GB USB Drive
Retail Price $32.95
Our Price $25.00
  Buy Textbooks
  Sell Textbooks
  College Apparel
  Shop by School
  Virtual Bookstores
   Order Status
  Shipping Rates
  Return Policy
  Marketplace Info
  F.A.S.T.
   Contact Us
  Privacy Policy
  Legal Notices
  Site Security
  Employment
  Help Desk
  eCampus Blog
  Affiliate Program
  Bulk Orders
  College Marketing
 HACKER SAFE certified sites prevent over 99.9% of hacker crime.
eCampus.com blog follow eCampus.com on twitter find eCampus.com on facebook RSS Need Help? eService@ecampus.com   Copyright© 1999-2008     
.