Appendix E - Interconnection Networks.pdf - Computer Architecture A Quantitative Approach (Dodatki) - Kowalski2015

E.1

Introduction

E-2

E.2

Interconnecting Two Devices

E-5

E.3

Connecting More than Two Devices

E-20

E.4

Network Topology

E-29

E.5

Network Routing, Arbitration, and Switching

E-45

E.6

Switch Microarchitecture

E-55

E.7

Practical Issues for Commercial Interconnection Networks

E-62

E.8

Examples of Interconnection Networks

E-70

E.9

Internetworking

E-80

E.10

Crosscutting Issues for Interconnection Networks

E-85

E.11

Fallacies and Pitfalls

E-88

E.12

Concluding Remarks

E-96

E.13

Historical Perspective and References

E-97

Exercises

E-107

Interconnection Networks

Revised by Timothy M. Pinkston, University of Southern California,

and José Duato, Universitat Politècnica de València, and Simula

“The Medium is the Message” because it is the medium that shapes and

controls the search and form of human associations and actions.

Marshall McLuhan

Understanding Media

(1964)

The marvels—of ﬁlm, radio, and television—are marvels of one-way

communication, which is not communication at all.

Milton Mayer

On the Remote Possibility of

Communication

(1967)

The interconnection network is the heart of parallel architecture.

Chuan-Lin Wu and Tse-Yun Feng

Interconnection Networks for Parallel

and Distributed Processing

(1984)

Indeed, as system complexity and integration continues to increase,

many designers are ﬁnding it more efﬁcient to route packets, not wires.

Bill Dally

Principles and Practices of

Interconnection Networks

(2004)

E-2

Appendix E

Interconnection Networks

E.1

Introduction

is generically used to signify anything from a

component or set of components within a computer to a single computer to a sys-

tem of computers. Figure E.1 shows the various elements comprising this com-

munity: end nodes consisting of devices and their associated hardware and

software interfaces, links from end nodes to the interconnection network, and the

interconnection network. Interconnection networks are also called

device

networks,

communication subnets,

communication subsystems

. The interconnection of

This relies on communication stan-

dards to convert information from one kind of network to another, such as with

the Internet.

There are several reasons why computer architects should devote attention to

interconnection networks. In addition to providing external connectivity, net-

works are commonly used to interconnect the components within a single com-

puter at many levels, including the processor microarchitecture. Networks have

long been used in mainframes, but today such designs can be found in personal

computers as well, given the high demand on communication bandwidth needed

to enable increased computing power and storage capacity. Switched networks

are replacing buses as the normal means of communication between computers,

between I/O devices, between boards, between chips, and even between modules

inside chips. Computer architects must understand interconnect problems and

solutions in order to more effectively design and evaluate computer systems.

Interconnection networks cover a wide range of application domains, very

much like memory hierarchy covers a wide range of speeds and sizes. Networks

implemented within processor chips and systems tend to share characteristics

much in common with processors and memory, relying more on high-speed hard-

ware solutions and less on a ﬂexible software stack. Networks implemented

across systems tend to share much in common with storage and I/O, relying more

on the operating system and software protocols than high-speed hardware—

though we are seeing a convergence these days. Across the domains, performance

includes latency and effective bandwidth, and queuing theory is a valuable ana-

lytical tool in evaluating performance, along with simulation techniques.

This topic is vast—portions of Figure E.1 are the subject of entire books and

college courses. The goal of this appendix is to provide for the computer architect

an overview of network problems and solutions. This appendix gives introduc-

tory explanations of key concepts and ideas, presents architectural implications

of interconnection network technology and techniques, and provides useful refer-

ences to more detailed descriptions. It also gives a common framework for evalu-

ating all types of interconnection networks, using a single set of terms to describe

internetworking.

Previous chapters and appendices cover the components of a single computer but

give little consideration to the interconnection of those components and how mul-

tiple computer systems are interconnected. These aspects of computer architec-

ture have gained signiﬁcant importance in recent years. In this appendix we see

how to connect individual devices together into a community of communicating

devices, where the term

multiple networks is called

E.1 Introduction

E-3

End node

Device

SW interface

HW interface

Link

Interconnection network

Figure E.1

A conceptual illustration of an interconnected community of devices.

the basic alternatives. As we will see, many types of networks have common pre-

ferred alternatives, but for others the best solutions are quite different. These dif-

ferences become very apparent when crossing between the networking domains.

Interconnection Network Domains

Interconnection networks are designed for use at different levels within and

across computer systems to meet the operational demands of various application

areas—high-performance computing, storage I/O, cluster/workgroup/enterprise

systems, internetworking, and so on. Depending on the number of devices to be

connected and their proximity, we can group interconnection networks into four

major networking domains:

(OCNs)—Also referred to as network-on-chip (NoC), this

type of network is used for interconnecting microarchitecture functional

units, register ﬁles, caches, compute tiles, and processor and IP cores within

chips or multichip modules. Currently, OCNs support the connection of up to

only a few tens of such devices with a maximum interconnection distance on

the order of centimeters. Most OCNs used in high-performance chips are cus-

tom designed to mitigate chip-crossing wire delay problems caused by

increased technology scaling and transistor integration, though some propri-

etary designs are gaining wider use (e.g., IBM’s CoreConnect, ARM’s

AMBA, and Sonic’s Smart Interconnect). An example custom OCN is the

used in the Cell Broadband Engine processor chip.

This network peaks at ~2400 Gbps (for a 3.2 GHz processor clock) for 12

elements on the chip.

This type of network is used for

interprocessor and processor-memory interconnections within multiprocessor

and multicomputer systems, and also for the connection of storage and I/O

components within server and data center environments. Typically, several

(SANs)

—

On-chip networks

Element Interconnect Bus

System/storage area networks

E-4

Appendix E

Interconnection Networks

hundreds of such devices can be connected, although some supercomputer

SANs support the interconnection of many thousands of devices, like the

IBM Blue Gene/L supercomputer. The maximum interconnection distance

covers a relatively small area

—

on the order of a few tens of meters usually

—

but some SANs have distances spanning a few hundred meters. For example,

, a popular SAN standard introduced in late 2000, supports system

and storage I/O interconnects at up to 120 Gbps over a distance of 300 m.

(LANs)—This type of network is used for interconnect-

ing autonomous computer systems distributed across a machine room or

throughout a building or campus environment. Interconnecting PCs in a clus-

ter is a prime example. Originally, LANs connected only up to a hundred

devices, but with bridging, LANs can now connect up to a few thousand

devices. The maximum interconnect distance covers an area of a few kilome-

ters usually, but some have distance spans of a few tens of kilometers. For

instance, the most popular and enduring LAN,

, has a 10 Gbps stan-

dard version that supports maximum performance over a distance of 40 km.

Ethernet

WANs con-

nect computer systems distributed across the globe, which requires internet-

working support. WANs connect many millions of computers over distance

scales of many thousands of kilometers. ATM is an example of a WAN.

(WANs)—Also called

long-haul networks,

Figure E.2 roughly shows the relationship of these networking domains in

terms of the number of devices interconnected and their distance scales. Overlap

exists for some of these networks in one or both dimensions, which leads to prod-

5 x 10

WAN

5 x 10

LAN

5 x 10

SAN

5 x 10

–3

OCN

100

1000

10,000

>100,000

Relationship of the four interconnection network domains in terms of

number of devices connected and their distance scales: on-chip network (OCN), sys-

tem/storage area network (SAN), local area network (LAN), and wide area network

(WAN).

Note that there are overlapping ranges where some of these networks com-

pete. Some supercomputer systems use proprietary custom networks to interconnect

several thousands of computers, while other systems, such as multicomputer clusters,

use standard commercial networks.

InﬁniBand

Local area networks

Wide area networks

Figure E.2

Appendix E - Interconnection Networks.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: