Advanced Computer Architecture CSE 8383ContentsMessage Passing SystemsSwitching TechniquesMessage Passing MechanismsMessage, Packets, FlitsStore and Forward RoutingWormhole RoutingLatency AnalysisStore and Forward LatencyWH LatencySlide 12Communication PatternsRouting 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 8383March 30, 2006March 30, 2006Session 20Session 20Computer 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 SystemsInterconnection NetworkPMComputer Science and EngineeringCopyright by Hesham El-RewiniSwitching TechniquesSwitching MechanismAdvantages DisadvantagesCircuit Switching Suitable for long messagesDeadlock-freeWasting of Bandwidth Packet Switching SimpleSuitable for interactive trafficBandwidth on demandBuffer for every packetPotential long latencyPotential deadlockVirtual Cut-ThroughGood for long messagesPossible deadlock avoidanceElimination of data-link protocolNeed for multiple message buffersWasting of bandwidthMainly used with profitable routingWormhole Good for long messagesReduced need for bufferingReduced effect of path lengthPossibility for deadlockInability to support backtrackingComputer 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 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 and EngineeringCopyright by Hesham El-RewiniSource-Path versus Table BasedPort 0Port 1Port 2Port 3Port 4Port 5Port 6Port 7605Port 0Port 1Port 2Port 3Port 4Port 5Port 6Port 7Dest-id6idRouting