O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Publishing Director: Diane D. Cerra
Senior Editor: Denise E. M. Penrose
Publishing Services Manager: Simon Crump
Project Manager: Marcy Barnes-Henrie
Editorial Coordinator: Alyson Day
Editorial Assistant: Summer Block
Cover Design: Hannus Design Associates
Cover Image: Frank Stella, Takht-i-Sulayan-I (1967)
Text Design: Rebecca Evans & Associates
Composition: Integra Software Services Pvt., Ltd.
Copyeditor: Catherine Albano
Proofreader: Deborah Prato
Indexer: Sharon Hilgenberg
Interior printer The Maple-Vail Book Manufacturing Group
Cover printer Phoenix Color Corp.
Morgan Kaufmann Publishers is an imprint of Elsevier
500 Sansome Street, Suite 400, San Francisco, CA 94111
This book is printed on acid-free paper.
c
2004 by Elsevier, Inc. All rights reserved.
Figure 3.10
c
2003 Silicon Graphics, Inc. Used by permission. All rights reserved.
Figure 3.13 courtesy of the Association for Computing Machinery (ACM), from James Laudon and
Daniel Lenoski, “The SGI Origin: a ccNUMA highly scalable server, Proceedings of the International
Symposium on Computer Architecture (ISCA), pp. 241-251, 1997. (ISBN: 0897919017) Figure 10.
Figure 10.7 from Thinking Machines Corp.
Figure 11.5 courtesy of Ray Mains, Ray Mains Photography,
http://www.mauigateway.com/raymains/.
Designations used by companies to distinguish their products are often claimed as trademarks or
registered trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the
product names appear in initial capital or all capital letters. Readers, however, should contact the
appropriate companies for more complete information regarding trademarks and registration.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
or by any means—electronic, mechanical, photocopying, or otherwise—without written permission of
the publishers.
Permissions may be sought directly from Elsevier’s Science & Technology Rights
Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail:
permissions@elsevier.com.uk. You may also complete your request on-line via the Elsevier homepage
(http://elsevier.com) by selecting "Customer Support" and then "Obtaining Permissions."
Library of Congress Cataloging-in-Publication Data
Dally, William J.
Principles and practices of interconnection networks / William
Dally, Brian Towles.
p. cm.
Includes bibliographical references and index.
ISBN 0-12-200751-4 (alk. paper)
1. Computer networks-Design and construction.
2. Multiprocessors. I. Towles, Brian. II. Title.
TK5105.5.D3272003
004.6’5–dc22
ISBN: 0-12-200751-4 2003058915
For information on all Morgan Kaufmann publications,
visit our Web Site at www.mkp.com
Printed in the United States of America
0405060708 54321
Contents
Acknowledgments xvii
Preface xix
About the Authors xxv
Chapter 1 Introduction to Interconnection Networks 1
1.1 Three Questions About Interconnection Networks 2
1.2 Uses of Interconnection Networks 4
1.2.1 Processor-Memory Interconnect 5
1.2.2 I/O Interconnect 8
1.2.3 Packet Switching Fabric 11
1.3 Network Basics 13
1.3.1 Topology 13
1.3.2 Routing 16
1.3.3 Flow Control 17
1.3.4 Router Architecture 19
1.3.5 Performance of Interconnection Networks 19
1.4 History 21
1.5 Organization of this Book 23
Chapter 2 A Simple Interconnection Network 25
2.1 Network Specifications and Constraints 25
2.2 Topology 27
2.3 Routing 31
2.4 Flow Control 32
2.5 Router Design 33
2.6 Performance Analysis 36
2.7 Exercises 42
vii
viii Contents
Chapter 3 Topology Basics 45
3.1 Nomenclature 46
3.1.1 Channels and Nodes 46
3.1.2 Direct and Indirect Networks 47
3.1.3 Cuts and Bisections 48
3.1.4 Paths 48
3.1.5 Symmetry 49
3.2 Traffic Patterns 50
3.3 Performance 51
3.3.1 Throughput and Maximum Channel Load 51
3.3.2 Latency 55
3.3.3 Path Diversity 57
3.4 Packaging Cost 60
3.5 Case Study: The SGI Origin 2000 64
3.6 Bibliographic Notes 69
3.7 Exercises 69
Chapter 4 Butterfly Networks 75
4.1 The Structure of Butterfly Networks 75
4.2 Isomorphic Butterflies 77
4.3 Performance and Packaging Cost 78
4.4 Path Diversity and Extra Stages 81
4.5 Case Study: The BBN Butterfly 84
4.6 Bibliographic Notes 86
4.7 Exercises 86
Chapter 5 Torus Networks 89
5.1 The Structure of Torus Networks 90
5.2 Performance 92
5.2.1 Throughput 92
5.2.2 Latency 95
5.2.3 Path Diversity 96
5.3 Building Mesh and Torus Networks 98
5.4 Express Cubes 100
5.5 Case Study: The MIT J-Machine 102
5.6 Bibliographic Notes 106
5.7 Exercises 107
Contents ix
Chapter 6 Non-Blocking Networks 111
6.1 Non-Blocking vs. Non-Interfering Networks 112
6.2 Crossbar Networks 112
6.3 Clos Networks 116
6.3.1 Structure and Properties of Clos Networks 116
6.3.2 Unicast Routing on Strictly Non-Blocking
Clos Networks 118
6.3.3 Unicast Routing on Rearrangeable Clos Networks 122
6.3.4 Routing Clos Networks Using Matrix
Decomposition 126
6.3.5 Multicast Routing on Clos Networks 128
6.3.6 Clos Networks with More Than Three Stages 133
6.4 Beneˇs Networks 134
6.5 Sorting Networks 135
6.6 Case Study: The Velio VC2002 (Zeus) Grooming Switch 137
6.7 Bibliographic Notes 142
6.8 Exercises 142
Chapter 7 Slicing and Dicing 145
7.1 Concentrators and Distributors 146
7.1.1 Concentrators 146
7.1.2 Distributors 148
7.2 Slicing and Dicing 149
7.2.1 Bit Slicing 149
7.2.2 Dimension Slicing 151
7.2.3 Channel Slicing 152
7.3 Slicing Multistage Networks 153
7.4 Case Study: Bit Slicing in the Tiny Tera 155
7.5 Bibliographic Notes 157
7.6 Exercises 157
Chapter 8 Routing Basics 159
8.1 A Routing Example 160
8.2 Taxonomy of Routing Algorithms 162
8.3 The Routing Relation 163
8.4 Deterministic Routing 164
8.4.1 Destination-Tag Routing in Butterfly Networks 165
8.4.2 Dimension-Order Routing in Cube Networks 166

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required