CSE 8383 - Advanced Computer ArchitectureContentsDynamic Network AnalysisMIMD Distributed Memory SystemsInterconnection Network TaxonomyDynamic Interconnection NetworksSwitch ModulesBinary SwitchLegitimate ConnectionsGroup WorkMultistage Interconnection NetworksPerfect-Shuffle Routing FunctionPerfect Shuffle ExamplePerfect-ShuffleExchange Routing FunctionExchange E1Slide 17Butterfly Routing FunctionButterfly ExampleButterflyMulti-stage networkMIN (cont.)Min ImplementationExampleConsider this MINExample (Cont.)The 3 connectionsBoolean FunctionsCrossbar SwitchAnalysis and performance metrics dynamic networksMessage Passing MechanismsMessage, Packets, FlitsStore and Forward RoutingWormhole RoutingLatency AnalysisCommunication PatternsRouting EfficiencyMulticast on a mesh (5 unicasts)Multicast on a mesh (multicast pattern 1Multicast on a mesh (multicast pattern 2)Broadcast (tree structure)Message Passing in PVMStandard PVM asynchronous communicationStandard PVM asynchronous communication (cont.)Send (3 steps)Receive (2 steps)Message BuffersMessage Buffers (cont.)Sending a messageReceiving a messageDifferent Receive in PVMData unpackingCSE 8383 - Advanced Computer ArchitectureWeek-12April 8, 2004engr.smu.edu/~rewini/8383ContentsDynamic NetworksMessage Passing MechanismsMessage Passing in PVMDynamic Network AnalysisParameters:Cost: number of switchesDelay: latencyBlocking characteristicsFault toleranceMIMD Distributed Memory SystemsInterconnection NetworksM M M MP P P PInterconnection Network TaxonomyInterconnection NetworkStaticDynamicBus-based Switch-based1-D 2-D HCSingle MultipleSS MSCrossbarDynamic Interconnection NetworksCommunication patterns are based on program demandsConnections are established on the fly during program executionMultistage Interconnection Network (MIN) and CrossbarSwitch ModulesA x B switch moduleA inputs and B outputsIn practice, A = B = power of 2Each input is connected to one or more outputs (conflicts must be avoided)One-to-one (permutation) and one-to-many are allowedBinary Switch2x2SwitchLegitimate States = 4Permutation Connections = 2Legitimate ConnectionsStraight ExchangeUpper-broadcastLower-broadcastThe different setting of the 2X2 SEGroup WorkGeneral Case ??Multistage Interconnection NetworksISC1ISC1ISC2ISC2ISCnISCnswitchesswitchesswitchesISC  Inter-stage Connection PatternsPerfect-Shuffle Routing FunctionGiven x = {an, an-1, …, a2, a1}P(x) = {an-1, …, a2, a1 , an}X = 110001P(x) = 100011Perfect Shuffle Example000  000001  010010  100011  110100  001101  011110  101111  111Perfect-Shuffle000001010011100101110111000001010011100101110111Exchange Routing FunctionGiven x = {an, an-1, …, a2, a1}Ei(x) = {an, an-1, …, ai, …, a2, a1}X = 0000000E3(x) = 0000100Exchange E1000  001001  000010  011011  010100  101101  100110  111111  110Exchange E1000001010011100101110111000001010011100101110111Butterfly Routing FunctionGiven x = {an, an-1, …, a2, a1}B(x) = {a1 , an-1, …, a2, an}X = 010001P(x) = 110000Butterfly Example000  000001  100010  010011  110100  001101  101110  011111  111Butterfly000001010011100101110111000001010011100101110111Multi-stage network000001010011100101110111000001010011100101110111MIN (cont.)123456789101112001010011100101110111000000001010011100101110111An 8X8 Banyan networkMin ImplementationControl (X)Source (S)Destination (D)X = f(S,D)Example X = 0 X = 1 (crossed) (straight) A B C D A B C DConsider this MINS1S2S3S4S5S6S7S8D1D2D3D4D5D6D7D8stage 1stage 2stage 3Example (Cont.)Let control variable be X1, X2, X3Find the values of X1, X2, X3 to connect:S1  D6S7  D5S4  D1The 3 connectionsS1S2S3S4S5S6S7S8D1D2D3D4D5D6D7D8stage 1stage 2stage 3Boolean FunctionsX = x1, x2, x3S = s2, s2, s3D = d1, d2, d3Find X = f(S,D)Crossbar Switch M1 M2 M3 M4 M5 M6 M7 M8 P1P2P3P4P5P6P7P8Analysis and performance metricsdynamic networksPerformance comparison of dynamic networksNetworks Delay Cost BlockingDegree of FTBus O(N) O(1) Yes 0Multiple-bus O(mN) O(m) Yes (m-1)MIN O(logN) O(NlogN) Yes 0Crossbar O(1) O(N2) No 0Message 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 flitMessage, Packets, FlitsMessagePacketData flitDestinationSequenceStore 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 availableWormhole 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 upLatency 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)Communication PatternsPoint to Point  1 - 1Multicast  1 - nBroadcast  1 - allConference  n - nRouting EfficiencyTwo ParametersChannel Traffic (number of channels used to deliver the message involved)Communication Latency (distance)Multicast on a mesh (5 unicasts)Traffic ?Latency ?Multicast on a mesh (multicast pattern 1Traffic ?Latency ?Multicast on a mesh (multicast pattern 2)Traffic ?Latency ?Broadcast (tree structure)32 3421 23112Message Passing in PVMUser applicationLibraryDaemon12 34User applicationLibraryDaemon5678Sending Task Receiving TaskStandard PVM asynchronous communicationA sending task issues a send command (point 1)The message is transferred to the daemon (point 2)Control is returned to the user application (points 3 & 4)The daemon will transmit the message on the physical wire sometime after returning control to the user application (point 3)Standard PVM asynchronous communication (cont.)The receiving task issues a receive command (point 5) at some other timeIn the case of a blocking receive, the receiving task blocks on the daemon waiting for a message (point 6). After the message arrives,