Computer
`Architecture
`
`A
`
`Quantitative
`
`Approach
`
`Second Edition
`
`David A. Patterson
`UNIVERSITY OF CALIFORNIA AT BERKELEY
`
`John L. Hennessy
`STANFORD UNIVERSITY
`
`With a Contribution by
`David Goldberg
`Xerox Palo Alto Research Center
`
`MU
`
`MORGAN KAUFMANN PUBLISHERS. INC.
`SAN FRANCISCO. CALIFORNIA
`
`l_—__
`
`EMC Exhibit 1034
`
`EMC V. Intellectual Ventures
`
`IPR2016-01 106
`
`

`

`Sponsoring Editor Bruce M. Spat;
`Production Manager Yonic Overturn
`Production Editor
`Julie Pabst
`Text Design Gary Head. with second edition
`modifications by Ross Carron Design
`Cover Art Direction David Lance Goines
`Cover Design Ross Carton Design
`
`liiusmtion Illusoiouanc.
`Copyedimnr Ken DellaPenta. Gary Monis.
`Sharilyn Hovind. Jessie Wood
`Proofreader
`Jeff Van Bueren
`Composition Nancy Logan
`Printer Courier Corporation
`
`Morgan Kaufmann Publishers. Inc.
`Editorial and Sales Ofiice
`340 Pine Street. Sixth Floor
`San Francisco. CA 94104-3205 USA
`Telephone: 415 1’ 3922665. Focsimiie: 415 l' 982-2665. Internet: mitp@ mkp.com
`Order roilfree: 300 3‘ 7454323
`
`© 1990. 1996 by Morgan Kaufmann Publishers. Inc.
`All rights reserved
`
`Published 1990. Second Edition 1996
`Printed in the United States of America
`03 02 01
`10 9 8 7
`
`No part of this publication may be reproduced. stored in a retrieval system. or u'ansmittcd in any form or by any
`means—electronic. mechanical. recording. or otbemiseHwithout the prior written permission of the publisher.
`
`All instruction sets and other design information of the DLX computer system contained herein is copyrighted by the
`publisher and may not be incorporated in other publications or distributed by media without Formal acknowledgment
`and written consent from the publisher. Use of the DLX in other publications for educational purpoaes is encouraged
`and application for permission is welcomed-
`
`ADVICE. PRAISE. St ERRORS: Any con-espondence related to this publication or intended for the authors should
`be addressed to the Editorial and Sales Office of Morgan Kaufmanu Publishers. Inc, Dept. P&H APE. Information
`regarding error sightings is encouraged. Any error sightings that are accepted for correction in subsequent printings
`will be rewarded by the authors With a payment 0131.00 (US) per correction upon availability of the new printing.
`Electronic mail can be sent to acmbugs @mkp.com. [ Please include your full name and permanent mailing address.)
`
`INSTRUCTOR SUPPORT: For information on classroom software and other instructor materials available to
`
`adopters, please contact the Editorial and Sales Office of Morgan Kaufmann Publishers. Inc. (415 f 392«2665) or
`visit our web site at http:ilwww.mkp.com.
`
`Library of Congress Cataloging—imPublication Data
`Patterson. David A.
`Computer architecture: a quantitative approach f David A. Patterson. John L. Hennessy: with a contribution by
`David Goldberg.
`“2nd ed.
`p. cm.
`includes bibliographical references and index.
`ISBN 1-55860-329-3 (cloth). ——ISBN 15586067247 (paper)
`1. Computer architecture.
`I. Hennessy. John L.
`[L Goldberg. David.
`QA76.9.A73P377
`1995
`004.2‘2—dc20
`
`111. Title.
`
`95-37027
`CIP
`
`

`

`
`
`7.5 Connecting More Than Two Computers
`
`583
`
`Switches allow communication to harvest the same rapid advance from silicon
`as have processors and main memory. Whereas the switches from telecommuni-
`cations companies were once the size of mainframe computers, today we see
`single-chip switches in MPPs. Just as single—chip processors led to processors re—
`placing logic in a surprising number of places, single-chip switches will increas-
`ingly replace buses and shared media interconnection networks.
`
`Switch Topology
`
`The number of different topologies that have been discussed in publications
`would be difficult to count, but the number that have been used commercially is
`just a handful, with MPP designers being the most visible and imaginative. MPPs
`have used regular topologies to simplify packaging and scalability. The topolo-
`gies of LANs and WANs are more haphazard, having more to do with the chal-
`lenges of long distance or simply the connection of equipment purchased over
`several years.
`Figure 7.13 illustrates two of the popular switch organizations, with the path
`from node P0 to node P6 highlighted in each topology. A fully connected, or
`crossbar; interconnection allows any node to communicate with any other node
`in one pass through the interconnection. An Omega interconnection uses less
`hardware than the crossbar interconnection (n/2 logz n vs. n2 switches), but con-
`tention is more likely to occur between messages, depending on the pattern of
`communication. The term blocking is used to describe this form of contention.
`For example, in the Omega interconnection in Figure 7.13 a message from P1 to
`P7 is blocked while waiting for a message from P0 to P6. Of course, if two nodes
`try to send to the same destination—both P0 and P1 send to P6-—there will be
`contention for that link, even in the crossbar.
`
`Another switch is based on a tree with bandwidth added higher in the tree to
`match the requirements of common communications patterns. This topology,
`commonly called afat tree, is shown in Figure 7.14. Interconnections are normally
`drawn as graphs, with each arc of the graph representing a link of the communica—
`tion interconnection, with nodes shown as black squares and switches shown as
`shaded circles. This figure shows that there are multiple paths between any two
`nodes; for example, between node 0 and node 8 there are four paths. If messages
`are randomly assigned to different paths, communication can take advantage of
`the full bandwidth of the fat—tree topology.
`Thus far the switch has been separate from the processor and memory and as-
`sumed to be located in a central location. Looking inside this switch we see many
`smaller switches. The term multistage switch is sometimes used to refer to cen-
`tralized units to reflect the multiple steps that a message may travel before it
`reaches a computer. Instead of centralizing these small switching elements, an al-
`ternative is to place one small switch at every computer, yielding a distributed
`switching unit.
`
`

`

`Chapter 7 Interconnection Networks
`584
`
`
`
`
`
`
`Hill-Ill-
`.nnnnnnr
`
`E-rreesrfi
`gzeeeeeee
`I .flflflflflflfl
`.flflflflflflfl
`H.nnnnnnn
`
`c. Omega network switch box
`
`a. Cross bar
`
`b. Omega network
`
`FIGURE 7.13 Popular switch topologies for eight nodes. The links are unidirectional; data come in at the left and exit
`out the right link. The switch box in (c) can pass A to C and B to D or B to C and A to D. The crossbar uses n2 switches,
`
`processors. The Omega network cannot.
`
`