`

`I
`
`Sponsoring EdifQr Bruce M. Spatt
`Prot/uction Mallager Yallie Ovenon
`Production Editor
`Julie Pabst
`Text Design Gary Head, with second edition
`modifications by Ross Carron Design
`Cover An Direction David Lance Goines
`Cover Design Ross Carron Design
`
`lJJustrious, Inc.
`1IIustrolion
`CQpyeditors Ken DellaPenl8, Gary Morris,
`Sharilyn Hovind, Jessie Wood
`Proofreader
`Jeff Van Sucren
`Composition Nancy Logan
`Printer Courier Corporation
`
`Morgan Kaufmann Publishers, Inc.
`Editorial and Sales Office
`340 Pine Street. Sixth P100r
`San Francisco. CA 94104-3205 USA
`Telephone: 415/392-2665. Facsimile: 415 1982-2665, Intunet: mkp@mkp.com
`Order toJ! free: 800 1745*7323
`
`e 1990. 1996 by Morgan Kaufmann Publishers, Inc.
`All rights reserved
`
`Published 1990. Second Edition 1996
`Prinled in the United States of America
`030201
`10987
`
`No part of this publication may be reproduced, stored in a retrieval syStem. or transmiued in any form or by any
`means--electronic. mechanical, recording. or OIberwise-withoul the prior wriuen permission of the publisher.
`
`All instruction sets and orner design infommtion of the DLX computer syslem cOnlained herein is copyrighted by the
`publisher and may not be incorporated in other publications or distributed by media without formal acknowledgment
`and wrincn consenl from me publisher. Use of the DLX in Other publications for educational purposes is encouraged
`and application for permission is welcomed.
`
`ADVICE, PRAISE. & ERRORS: Any correspondence related to this publication or intended for the authors should
`be addressed to the Editorial and Sales Office of Morgan Kaufmann Publishers. Inc., DepL P&H APE. Infonnation
`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 of $1.00 (U.S.) per correction upon availability of the new priming.
`Electronic mail can be sent to arc2bugs@mkp.rom. (Please include your full name and permanent mailing address.)
`
`LNSTRUCTOR SUPPORT: For infonnation on classroom software and OIher instructor materials available to
`adopters. please contact the Editorial and Sales Office of Morgan Kaufmann Publishers. Inc. (415/392·2665) or
`visit our web sile at http://www.mkp.com.
`
`Library of Congress Cataloging-in"Publication Data
`Patterson, David A.
`Computer architecture: a quamitative approach 1 David A. Patterson. John L. Hennessy; with a contribution by
`David Goldberg.
`-2nde<!.
`p.cm.
`Includes bibliographical references and index..
`ISBN 1-55860-329-8 (cloth). ~ISBN 1-55860-372·7 (paper)
`I. Hennessy. John L.
`I. Computer architecture.
`II. Goldberg, David.
`QA76.9.A73P377
`1995
`004.2'2-<1c20
`
`ill. Title.
`
`95-37027
`erp
`
`Page 2
`
`

`

`7.5 Connecting More Than Two Computers
`
`585
`
`30
`
`0
`
`2
`
`10
`
`00
`
`0
`
`0
`
`10
`
`11
`
`01
`
`2
`
`1
`
`0
`
`2
`
`1
`
`3
`
`0
`
`3
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`FIGURE 7.14 A fat-tree topology for 16 nodes. The shaded circles are switches, and the squares at the bottom are pro-
`cessor-memory nodes. A simple 4-ary tree would only have the links at the front of the figure; that is, the tree with the root
`labeled 0,0. This three-dimensional view suggests the increase in bandwidth via extra links at each level over a simple tree,
`so bandwidth between each level of a fat tree is normally constant rather than being reduced by a factor of four as in a 4-
`ary tree. Multiple paths and random routing give it the ability to route common patterns well, which ensures no single pattern
`from a broad class of communication patterns will do badly. In the CM-5 fat-tree implementation, the switches have four
`downward connections and two or four upward connections; in this figure the switches have two upward connections.
`
`Given a distributed switch, the question is how to connect the switches together.
`Figure 7.15 shows that a low-cost alternative to full interconnection is a network
`that connects a sequence of nodes together. This topology is called a ring. Since
`some nodes are not directly connected, some messages will have to hop along
`intermediate nodes until they arrive at the final destination. Unlike shared lines, a
`ring is capable of many simultaneous transfers: the first node can send to the sec-
`ond at the same time as the third node can send to the fourth, for example. Rings
`are not quite as good as this sounds because the average message must travel
`through n/2 switches, where n is the number of nodes. To first order, a ring is like
`a pipelined bus: on the plus side are point-to-point links, and on the minus side
`are “bus repeater” delays.
`
`Page 3
`
`

`

`586
`
`Chapter 7 Interconnection Networks
`
`FIGURE 7.15 A ring network topology.
`
`One variation of rings used in local area networks is the token ring. To simplify
`arbitration, a single slot, or token, is passed around the ring to determine which
`node is allowed to send a message; a node can send only when it gets the token. (A
`token is simply a special bit pattern.) In this section we will evaluate the ring as a
`topology with more bandwidth rather than one that may be simpler to arbitrate
`than a long shared medium.
`A straightforward but expensive alternative to a ring is to have a dedicated
`communication link between every switch. The tremendous improvement in per-
`formance of fully connected switches is offset by the enormous increase in cost,
`typically going up with the square of the number of nodes. This cost inspires de-
`signers to invent new topologies that are between the cost of rings and the perfor-
`mance of fully connected networks. The evaluation of success depends in large
`part on the nature of the communication in the interconnection network. Real ma-
`chines frequently add extra links to these simple topologies to improve perfor-
`mance and reliability. Figure 7.16 illustrates three popular topologies for MPPs.
`One popular measure for MPP interconnections, in addition to the ones covered
`in section 7.2, is the bisection bandwidth. This measure is calculated by dividing
`the interconnect into two roughly equal parts, each with half the nodes. You then
`sum the bandwidth of the lines that cross that imaginary dividing line. For fully
`connected interconnections the bisection bandwidth is (n/2)2, where n is the num-
`ber of nodes.
`Since some interconnections are not symmetric, the question arises as to
`where to draw the imaginary line when bisecting the interconnect. Bisection
`bandwidth is a worst-case metric, so the answer is to choose the division that
`makes interconnection performance worst; stated alternatively, calculate all pos-
`sible bisection bandwidths and pick the smallest. Figure 7.17 summarizes these
`different topologies using bisection bandwidth and the number of links for 64
`nodes.
`
`Page 4
`
`