Advanced Computer Architecture CSE 8383ContentsMessage Passing MechanismsMessage, Packets, FlitsStore and Forward RoutingWormhole RoutingLatency AnalysisStore and Forward LatencyWH LatencySlide 10Communication PatternsRouting potential problemsSlide 13Slide 14Slide 15Routing EfficiencyMulticast on a mesh (5 unicasts)Multicast on a mesh (multicast pattern 1)Multicast on a mesh (multicast pattern 2)Broadcast (tree structure)Message Passing in PVM (Revisit)Client/Server SystemsA Client Server Framework for Parallel ApplicationsClustersInterconnection Networks in ClustersSource-Path versus Table BasedComputer Science and EngineeringCopyright by Hesham El-RewiniAdvanced Computer Advanced Computer ArchitectureArchitectureCSE 8383CSE 8383April 4, 2006April 4, 2006Session 21Session 21Computer Science and EngineeringCopyright by Hesham El-RewiniContentsMessage Passing Systems (Chapters 5 & 7)Communication PatternsClient/Server SystemsClustersComputer Science and EngineeringCopyright by Hesham El-RewiniMessage Passing MechanismsMessage FormatMessage  arbitrary number of fixed length packetsPacket  basic unit containing destination address. Sequence number is neededA packet can further be divided into flits (flow control digits)Routing and sequence occupy header flitComputer Science and EngineeringCopyright by Hesham El-RewiniMessage, Packets, FlitsMessagePacketData flitDestinationSequenceComputer Science and EngineeringCopyright by Hesham El-RewiniStore and Forward RoutingPackets are the basic units of information flowEach node uses a packet bufferA packet is transferred from S to D through a sequence of intermediate nodesChannel and buffer must be availableComputer Science and EngineeringCopyright by Hesham El-RewiniWormhole RoutingFlits are the basic units of information flowEach node uses a flit bufferFlits are transferred from S to D through a sequence of intermediate routers in order (Pipeline)Can be visualized as a railroad trainFlits from different packets cannot be mixed upComputer Science and EngineeringCopyright by Hesham El-RewiniLatency AnalysisL  packet length (in bits)W  Channel bandwidth (bits/sec)D  Distance (number of hops)F  flit length (in bits)Computer Science and EngineeringCopyright by Hesham El-RewiniStore and Forward Latency WLWLWLSFTDComputer Science and EngineeringCopyright by Hesham El-RewiniWH LatencyWLWTDComputer Science and EngineeringCopyright by Hesham El-RewiniLatency AnalysisL  packet length (in bits)W  Channel bandwidth (bits/sec)D  Distance (number of hops)F  flit length (in bits)TSF = D * L/WTWH = L/W + D* F/W  L/W if L>>F(independent of D)Computer Science and EngineeringCopyright by Hesham El-RewiniCommunication PatternsPoint to Point  1 - 1Multicast  1 - nBroadcast  1 - allConference  n - nComputer Science and EngineeringCopyright by Hesham El-RewiniRouting potential problemsDeadlock:When 2 messages, each is holding the resources required by the other in order to move, both messages will be blocked (cyclic dependency for resources)Straightforward solution (but inefficient) is reroutingAnother solution is avoidance of occurrence of deadlock using a strict monotonic order of network resourcesChannel dependency graph (CDG) is a technique for developing a deadlock-free routing algorithm.Computer Science and EngineeringCopyright by Hesham El-Rewini03 21c1c2c8c5c6c4c7c3c1c2c3c5c4c6c7c8c8c7c6c5c1c2c3c4 (a) A 4-node network (b) Channel dependency graph (CDG) (c) CDG for a deadlock-free version of the networkA 4-node network and its CDGsComputer Science and EngineeringCopyright by Hesham El-RewiniLivelock: A message goes around the network and never reaches its destinationIt results from using adaptive routing algorithms with dynamic injection, where nodes inject their messages in the network at arbitrary timesPolicies to avoid livelock are based on assigning a priority to a message injected to the network:Messages are routed according to their prioritiesOnce a message is injected, only a finite number of messages will be injected with higher or equal priority.Computer Science and EngineeringCopyright by Hesham El-RewiniStarvation: A node suffers from starvation if it has a message to inject into the network but is never allowed to do so.The simplest policy to avoid starvation is to allow each node to have an injection queue that competes with the queues of the incoming links to the same node.The main disadvantage is that a node with a high message injection rate can slow down all the other nodes in the network.Computer Science and EngineeringCopyright by Hesham El-RewiniRouting EfficiencyTwo ParametersChannel Traffic (number of channels used to deliver the message involved)Communication Latency (distance)Computer Science and EngineeringCopyright by Hesham El-RewiniMulticast on a mesh (5 unicasts)Traffic ?Latency ?Computer Science and EngineeringCopyright by Hesham El-RewiniMulticast on a mesh (multicast pattern 1)Traffic ?Latency ?Computer Science and EngineeringCopyright by Hesham El-RewiniMulticast on a mesh (multicast pattern 2)Traffic ?Latency ?Computer Science and EngineeringCopyright by Hesham El-RewiniBroadcast (tree structure)32 3421 23112Computer Science and EngineeringCopyright by Hesham El-RewiniMessage Passing in PVM (Revisit)User applicationLibraryDaemon12 34User applicationLibraryDaemon5678Sending Task Receiving TaskComputer Science and EngineeringCopyright by Hesham El-RewiniClient/Server SystemsInterconnectionNetworkInterconnectionNetworkServer ThreadsClientServer ClientComputer Science and EngineeringCopyright by Hesham El-RewiniA Client Server Framework for Parallel Applications InterconnectionNetworkInterconnectionNetworkMaster (Supervisor)Server 1Server 2Server 3 Server nClientSlaves (Workers)Computer Science and EngineeringCopyright by Hesham El-RewiniClustersProgramming Environment and ToolsInterconnectionNetworkInterconnectionNetworkMiddlewareOSMCPI/OOSMCPI/OOSMCPI/OComputer Science and EngineeringCopyright by Hesham El-RewiniInterconnection Networks in ClustersInterconnection NetworkData Rate Switching RoutingEthernet 10 Mbit/sec Packet Table-basedFast Ethernet 100 Mbit/sec Packet Table-basedGigabit Ethernet 1 Gbit/sec Packet Table-basedMyrinet 1.28 Gbit/sec wormhole Source-pathQuadrics 7.2 Gbyte/sec wormhole Source-pathComputer Science