Generic Scalable Multiprocessor Architecture Scalable 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 Scalable Network Communication assist CA Mem P Node processor s memory system plus communication assist Network interface and communication controller Scalable network Two Aspects of Network Scalability Performance and Complexity 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 i e network performance scalability Latency grows slowly with network size N e g O log2 N Total available bandwidth scales up with network size e g O N Network cost complexity should grow slowly in terms of network size i e network cost complexity scalability e g O Nlog2 N as opposed to O N2 PP Chapter 1 3 PCA Chapter 10 EECC756 Shaaban 1 lec 8 Spring2008 4 24 2008 Network Requirements For Parallel Computing 1 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 To reduce communication overheads 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 Scalable Interconnection Network Scalable network network interface CA M CA P Nodes M P EECC756 Shaaban 2 lec 8 Spring2008 4 24 2008 Cost of Communication Given amount of comm inherent or artifactual goal is to reduce cost Cost of communication as seen by process Cost of a message C f o l n B Communication Cost Actual time added to parallel execution time as a result of communication tc overlap Latency of a message 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 overlap From lecture 6 EECC756 Shaaban 3 lec 8 Spring2008 4 24 2008 Network 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 Phit W W W Flit W W 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 1 2 3 destination S Source D Destination A network is generally characterized by h 3 hops in route from S to D Type of interconnection Static point to point or Dynamic Topology Network node connectivity interconnection structure of the network graph Routing Algorithm Deterministic static or Adaptive dynamic Switching Strategy Packet or Circuit Switching Flow Control Mechanism Store Forward SF or Cut Through CT EECC756 Shaaban 4 lec 8 Spring2008 4 24 2008 Network Characteristics Type of interconnection 1 Static Direct or point to point Interconnects or channels Nodes connected directly using static point to point links Such networks include Fully connected networks Rings Meshes Hypercubes etc 2 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 One large switch Multi stage Interconnection Networks MINs including Omega Network Baseline Network Butterfly Network etc EECC756 Shaaban 5 lec 8 Spring2008 4 24 2008 Network Characteristics Network Topology Physical interconnection structure of the network graph Node connectivity Which nodes are directly connected nodes or switches 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 Distance in 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 Simplify Mapping Hop link channel in route EECC756 Shaaban 6 lec 8 Spring2008 4 24 2008 Network Topology and Requirements for Parallel Processing For Cost Scalability The total number of links node degree and size number of switches used should grow slowly as the size of the network is increased For Low network latency Small network diameter average distance are desirable For Latency Scalability The network diameter average distance should grow slowly as the size of the network is increased For Bandwidth Scalability The total number of links should increase in proportion to network size To support as many concurrent transfers as possible High network throughput A high bisection width is desirable and should increase proportional to network size Needed to reduce network contention and hot spots EECC756 Shaaban 7 lec 8 Spring2008 4 24 2008 Network Characteristics Routing Algorithm and Functions The set of paths that messages may follow 12 Deterministic static