Generic Multiprocessor ArchitectureCost of CommunicationNetwork Representation & CharacteristicsNetwork CharacteristicsSlide 5Slide 6Network Requirements For Parallel ComputingCommunication Network Performance : Network LatencyFlow Control Mechanisms: Store&Forward Vs. Cut-Through RoutingCommunication Network Performance : Network LatencyReducing Network LatencyAvailable BandwidthNetwork Performance Factors: ContentionNetwork SaturationDeadlock In Store & Forward NetworksSample Static Network TopologiesStatic Point-to-point Connection Network TopologiesStatic Network Topologies Examples: Multidimensional Meshes and ToriMultidimensional Meshes and Tori PropertiesStatic Connection Networks Examples: 2D Mesh (2-dimensional k-ary mesh)Static Connection Networks Examples: HypercubesMessage Routing Functions Example Dimension-order RoutingStatic Connection Networks Examples: TreesStatic Connection Networks Examples: Fat-TreesEmbedding k-ary d-cubes In Two DimensionsEmbedding A Binary Tree Onto A 2D MeshEmbedding A Ring Onto A 2D TorusDynamic Connection NetworksDynamic Networks DefinitionsDynamic Network Building Blocks: Crossbar-Based SwitchesSwitch ComponentsSwitch Size And Legitimate StatesPermutationsPerfect ShuffleMulti-Stage Networks: The Omega NetworkSlide 36MINs Example: Baseline NetworkMINs Example: Butterfly NetworkRelationship Between Butterfly Network & HypercubesTraditional Network Scaling: Latency(P)Unloaded Latency with Equal Bisection WidthSummary of Static Network CharacteristicsSummary of Dynamic Network CharacteristicsExample Networks: Cray MPPsParallel Machine ExamplesEECC756 - ShaabanEECC756 - Shaaban#1 lec # 10 Spring2002 4-23-2002 Generic Multiprocessor ArchitectureGeneric Multiprocessor ArchitectureNode: processor(s), memory system, plus communication assist:•Network interface and communication controller.•Scalable network.•Function of a parallel machine network is to efficiently transfer information from source node to destination node in support of network transactions that realize the programming model.•Network performance should scale up as its size is increased.MemNetworkP$Communicationassist (CA)EECC756 - ShaabanEECC756 - Shaaban#2 lec # 10 Spring2002 4-23-2002Cost of CommunicationCost of CommunicationGiven amount of comm (inherent or artifactual), goal is to reduce cost•Cost of communication as seen by process: C = f * ( o + l + + tc - overlap)•f = frequency of messages•o = overhead per message (at both ends)•l = network delay per message•n = data sent for per message•B = bandwidth along path (determined by network, NI, assist)•tc = cost induced by contention per message•overlap = amount of latency hidden by overlap with comp. or comm.– Portion in parentheses is cost of a message (as seen by processor)–That portion, ignoring overlap, is latency of a message–Goal: reduce terms in latency and increase overlapnBEECC756 - ShaabanEECC756 - Shaaban#3 lec # 10 Spring2002 4-23-2002Network Representation & CharacteristicsNetwork Representation & Characteristics•A parallel machine interconnection network is a graph V = {switches and nodes} connected by communication channels or links C  V  V•Each channel has width w bits and signaling rate f = 1/is clock cycle time)–Channel bandwidth b = wf bits/sec–Phit (physical unit) data transferred per cycle (usually channel width w).–Flit - basic unit of flow-control (minimum data unit transferred across a link).•Number of input (output) channels is switch or node degree.•Sequence of switches and links followed by a message in the network is a route. •Routing Distance - number of links or hops on route.•A network is generally characterized by:–Topology.–Flow Control Mechanism.–Routing Algorithm.–Switching Strategy.EECC756 - ShaabanEECC756 - Shaaban#4 lec # 10 Spring2002 4-23-2002Network CharacteristicsNetwork Characteristics•Topology: –Physical interconnection structure of the network graph:•Node Degree: Number of channels per node. •Network diameter: Longest minimum routing distance between any two nodes in hops.•Average Distance between all pairs of nodes .•Bisection width: Minimum number of links whose removal disconnects the graph and cuts it in half.•Symmetry: The property that the network looks the same from every node.•Homogeneity: Whether all the nodes and links are identical or not.–Type of interconnection:•Static or Direct Interconnects: Nodes connected directly using static point-to-point links.•Dynamic or Indirect Interconnects: Switches are usually used to realize dynamic links between nodes: –Each node is connected to specific subset of switches. (e.g Multistage Interconnection Networks, MINs).–Blocking or non-blocking, permutations realized.•Shared-, broadcast-, or bus-based connections. (e.g. Ethernet-based).EECC756 - ShaabanEECC756 - Shaaban#5 lec # 10 Spring2002 4-23-2002Network CharacteristicsNetwork Characteristics•Routing Algorithm and Functions:–The set of paths that messages may follow.–Request/message combining capabilities. •Switching Strategy:–Circuit switching vs. packet switching.•Flow Control Mechanism:–When a message or portions of it moves along its route:•Store & Forward Routing,•Cut-Through or Worm-Hole Routing.–What happens when traffic is encountered at a node:•Link/Node Contention handling.•Deadlock prevention. •Broadcast and Multicast Capabilities.•Communication Latency.•Link bandwidth.EECC756 - ShaabanEECC756 - Shaaban#6 lec # 10 Spring2002 4-23-2002Network CharacteristicsNetwork Characteristics•Hardware/software implementation complexity/cost.•Network throughput: Total number of messages handled by network per unit time.•Aggregate Network bandwidth: Similar to network throughput but given in total bits/sec.•Network hot spots: Form in a network when a small number of network nodes/links handle a very large percentage of total network traffic and become saturated.•Network scalability: –The feasibility of increasing network size, determined by:•Performance scalability: Relationship between network size in terms of number of nodes and the resulting network performance. •Cost scalability: Relationship between network size in terms of number of nodes/links and network cost/complexity.EECC756 - ShaabanEECC756 -