EECC756 EECC756 --ShaabanShaaban#1 lec # 8 Spring2008 4-24-2008Generic Scalable Multiprocessor ArchitectureGeneric Scalable 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 performanceshould scale up as its size is increased.• Latency grows slowly with network size N. e.g O(log2N)• Total available bandwidth scales up with network size. e.g O(N)• Network cost/complexity should grow slowly in terms of network size.e.g. O(Nlog2N) as opposed to O(N2)Mem° ° °NetworkP$Communicationassist (CA)(PP Chapter 1.3, PCA Chapter 10)ScalableScalable Parallel Performance: Continue to achieve good parallel performance "speedup"as the sizes of the system/problem are increased.Scalability/characteristics of the parallel system network play an important role in determining performance scalability of the parallel architecture.i.e network performance scalability i.e network cost/complexity scalability Two Aspects of Network Scalability: Performance and ComplexityEECC756 EECC756 --ShaabanShaaban#2 lec # 8 Spring2008 4-24-2008Network Requirements For Parallel ComputingNetwork Requirements For Parallel Computing1. Low network latency even when approaching network capacity.2. High sustained bandwidth that matches or exceeds the communication requirements for given computational rate.3. High network throughput:Network should support as many concurrent transfers as possible.4. Low Protocol overhead.5. Cost/complexity and performance Scalable:– Cost/Complexity Scalability: Minimum network cost/complexity increase as network size increases.• In terms of number of links/switches, node degree etc.– Performance Scalability: Network performance should scale up with network size. - Latency grows slowly with network size.- Total available bandwidth scales up with network size.MPCAMPCAnetworkinterfaceScalableInterconnectionNetworkScalable networkNodesTo reduce communication overheadsEECC756 EECC756 --ShaabanShaaban#3 lec # 8 Spring2008 4-24-2008Cost 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 overlapnBFrom lecture 6Cost of a messageLatency of a messageCommunication Cost: Actual time added to parallel execution time as a result of communicationEECC756 EECC756 --ShaabanShaaban#4 lec # 8 Spring2008 4-24-2008Network Representation & CharacteristicsNetwork Representation & Characteristics• A parallel machine interconnection network is a graph V = {switches or processing 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 channels per node or switch 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 h on route from source to destination.• A network is generally characterized by:– Type of interconnection.– Topology.– Routing Algorithm.– Switching Strategy.– Flow Control Mechanism.WWW WWPhitFlit2S= SourceD= Destination13h = 3 hops in route from S to DStatic (point-to-point) or DynamicPacket or Circuit Switching Deterministic (static) or Adaptive (dynamic)Network node connectivity/ interconnection structure of the network graphStore & Forward (SF) or Cut-Through (CT)EECC756 EECC756 --ShaabanShaaban#5 lec # 8 Spring2008 4-24-2008Network CharacteristicsNetwork Characteristics• Type of interconnection:– Static, Direct (or point-to-point) Interconnects:• Nodes connected directly using static point-to-point links. • Such networks include: – Fully connected networks , Rings, Meshes, Hypercubes etc.– Dynamic or Indirect Interconnects:• Switches are usually used to realize dynamic links (paths or virtual circuits ) between nodes instead of fixed point-to-point connections. • Each node is connected to specific subset of switches. • Dynamic connections are established by configuring switches based on communication demands.• Such networks include: – Shared-, broadcast-, or bus-based connections. (e.g. Ethernet-based).– Single-stage Crossbar switch networks.– Multi-stage Interconnection Networks (MINs) including:• Omega Network, Baseline Network, Butterfly Network, etc.12or channelsOne large switchEECC756 EECC756 --ShaabanShaaban#6 lec # 8 Spring2008 4-24-2008Network CharacteristicsNetwork Characteristics• Network Topology:Physical interconnection structure of the network graph:– Node connectivity: Which nodes are directly connected– Total number of links needed:Impacts network cost/total bandwidth– Node Degree:Number of channels per node. – Network diameter:Minimum routing distance in links or hops between the the farthest two nodes .– Average Distancein hops between all pairs of nodes .– Bisection width:Minimum number of links whose removal disconnects the network graph and cuts it into approximately two equal halves.• Related: Bisection Bandwidth = Bisection width x link bandwidth– Symmetry: The property that the network looks the same from every node.– Homogeneity:Whether all the nodes and links are identical or not.Hop = link = channel in routeSimplifyMapping{nodes or switchesEECC756 EECC756 --ShaabanShaaban#7 lec # 8 Spring2008 4-24-2008Network Topology and Requirements for Parallel Processing• For Cost Scalability: The total number of