CSCI 8150 Advanced Computer ArchitectureSystem Interconnect ArchitecturesGoals and AnalysisNetwork Properties and RoutingTerminology - 1Terminology - 2Data Routing FunctionsPermutationsPerfect Shuffle and ExchangeHypercube Routing FunctionsFactors Affecting PerformanceStatic NetworksStatic Networks – Linear ArrayStatic Networks – Ring, Chordal RingStatic Networks – Barrel ShifterStatic Networks – Tree and StarStatic Networks – Fat TreeStatic Networks – Mesh and TorusStatic Networks – Systolic ArrayStatic Networks – HypercubesStatic Networks – Cube-connected CyclesStatic Networks – k-ary n-CubesSlide 23Network ThroughputMinimizing LatencyDynamic Connection NetworksDynamic Networks – Bus SystemsDynamic Networks – Switch ModulesMultistage NetworksOmega NetworkBaseline Network4  4 Baseline NetworkCrossbar NetworksSummary: NotesSummary: Minimum LatencySummary: Bandwidth per ProcessorSummary: Wiring ComplexitySummary: Switching ComplexitySummary: Connectivity and RoutingCSCI 8150Advanced Computer ArchitectureHwang, Chapter 2Program and Network Properties2.4 System Interconnect ArchitecturesSystem Interconnect ArchitecturesDirect networks for static connectionsIndirect networks for dynamic connectionsNetworks are used forinternal connections in a centralized system among •processors•memory modules•I/O disk arraysdistributed networking of multicomputer nodesGoals and AnalysisThe goals of an interconnection network are to providelow-latencyhigh data transfer ratewide communication bandwidthAnalysis includeslatencybisection bandwidthdata-routing functionsscalability of parallel architectureNetwork Properties and RoutingStatic networks: point-to-point direct connections that will not change during program executionDynamic networks:switched channels dynamically configured to match user program communication demandsinclude buses, crossbar switches, and multistage networksBoth network types also used for inter-PE data routing in SIMD computersTerminology - 1Network usually represented by a graph with a finite number of nodes linked by directed or undirected edges.Number of nodes in graph = network size .Number of edges (links or channels) incident on a node = node degree d (also note in and out degrees when edges are directed). Node degree reflects number of I/O ports associated with a node, and should ideally be small and constant.Diameter D of a network is the maximum shortest path between any two nodes, measured by the number of links traversed; this should be as small as possible (from a communication point of view).Terminology - 2Channel bisection width b = minimum number of edges cut to split a network into two parts each having the same number of nodes. Since each channel has w bit wires, the wire bisection width B = bw. Bisection width provides good indication of maximum communication bandwidth along the bisection of a network, and all other cross sections should be bounded by the bisection width.Wire (or channel) length = length (e.g. weight) of edges between nodes.Network is symmetric if the topology is the same looking from any node; these are easier to implement or to program.Other useful characterizing properties: homogeneous nodes? buffered channels? nodes are switches?Data Routing FunctionsShiftingRotatingPermutation (one to one)Broadcast (one to all)Multicast (many to many)Personalized broadcast (one to many)ShuffleExchangeEtc.PermutationsGiven n objects, there are n ! ways in which they can be reordered (one of which is no reordering).A permutation can be specified by giving the rule fo reordering a group of objects.Permutations can be implemented using crossbar switches, multistage networks, shifting, and broadcast operations. The time required to perform permutations of the connections between nodes often dominates the network performance when n is large.Perfect Shuffle and ExchangeStone suggested the special permutation that entries according to the mapping of the k-bit binary number a b … k to b c … k a (that is, shifting 1 bit to the left and wrapping it around to the least significant bit position).The inverse perfect shuffle reverses the effect of the perfect shuffle.Hypercube Routing FunctionsIf the vertices of a n-dimensional cube are labeled with n-bit numbers so that only one bit differs between each pair of adjacent vertices, then n routing functions are defined by the bits in the node (vertex) address.For example, with a 3-dimensional cube, we can easily identify routing functions that exchange data between nodes with addresses that differ in the least significant, most significant, or middle bit.Factors Affecting PerformanceFunctionality – how the network supports data routing, interrupt handling, synchronization, request/message combining, and coherenceNetwork latency – worst-case time for a unit message to be transferredBandwidth – maximum data rateHardware complexity – implementation costs for wire, logic, switches, connectors, etc.Scalability – how easily does the scheme adapt to an increasing number of processors, memories, etc.?Static NetworksLinear ArrayRing and Chordal RingBarrel ShifterTree and StarFat TreeMesh and TorusStatic Networks – Linear ArrayN nodes connected by n-1 links (not a bus); segments between different pairs of nodes can be used in parallel.Internal nodes have degree 2; end nodes have degree 1.Diameter = n-1Bisection = 1For small n, this is economical, but for large n, it is obviously inappropriate.Static Networks – Ring, Chordal RingLike a linear array, but the two end nodes are connected by an n th link; the ring can be uni- or bi-directional. Diameter is n/2 for a bidirectional ring, or n for a unidirectional ring.By adding additional links (e.g. “chords” in a circle), the node degree is increased, and we obtain a chordal ring. This reduces the network diameter.In the limit, we obtain a fully-connected network, with a node degree of n -1 and a diameter of 1.Static Networks – Barrel ShifterLike a ring, but with additional links between all pairs of nodes that have a distance equal to a power of 2.With a network of size N = 2n, each node has degree d = 2n -1, and the network has diameter D = n /2.Barrel shifter connectivity is greater than any chordal ring of lower node degree.Barrel shifter much less complex than fully-interconnected network.Static Networks – Tree and StarA k-level completely balanced binary tree will have N = 2k – 1 nodes, with maximum node