Advanced Computer Architecture CSE 8383ContentsSlide 3Dynamic Network AnalysisBus Based INDynamic 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 networksComputer Science and EngineeringCopyright by Hesham El-RewiniAdvanced Computer Advanced Computer ArchitectureArchitectureCSE 8383CSE 8383February 16 2006February 16 2006Session 10Session 10Computer Science and EngineeringCopyright by Hesham El-RewiniContentsDynamic NetworksBus based systemsSwitch based systemsComputer Science and EngineeringCopyright by Hesham El-RewiniInterconnection NetworkStaticDynamicBus-based Switch-based1-D 2-D HCSingle MultipleSS MSCrossbarComputer Science and EngineeringCopyright by Hesham El-RewiniDynamic Network AnalysisParameters:CostDelay: latencyBlocking characteristicsFault toleranceComputer Science and EngineeringCopyright by Hesham El-RewiniBus Based INGlobal Memory PGlobal Memory P C P C P C P PComputer Science and EngineeringCopyright by Hesham El-RewiniDynamic Interconnection NetworksCommunication patterns are based on program demandsConnections are established on the fly during program executionMultistage Interconnection Network (MIN) and CrossbarComputer Science and EngineeringCopyright by Hesham El-RewiniSwitch 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 allowedComputer Science and EngineeringCopyright by Hesham El-RewiniBinary Switch2x2SwitchLegitimate States = 4Permutation Connections = 2Computer Science and EngineeringCopyright by Hesham El-RewiniLegitimate ConnectionsStraight ExchangeUpper-broadcastLower-broadcastThe different setting of the 2X2 SEComputer Science and EngineeringCopyright by Hesham El-RewiniGroup WorkGeneral Case ??Computer Science and EngineeringCopyright by Hesham El-RewiniMultistage Interconnection NetworksISC1ISC1ISC2ISC2ISCnISCnswitchesswitchesswitchesISC  Inter-stage Connection PatternsComputer Science and EngineeringCopyright by Hesham El-RewiniPerfect-Shuffle Routing FunctionGiven x = {an, an-1, …, a2, a1}P(x) = {an-1, …, a2, a1 , an}X = 110001P(x) = 100011Computer Science and EngineeringCopyright by Hesham El-RewiniPerfect Shuffle Example000  000001  010010  100011  110100  001101  011110  101111  111Computer Science and EngineeringCopyright by Hesham El-RewiniPerfect-Shuffle000001010011100101110111000001010011100101110111Computer Science and EngineeringCopyright by Hesham El-RewiniExchange Routing FunctionGiven x = {an, an-1, …, a2, a1}Ei(x) = {an, an-1, …, ai, …, a2, a1}X = 0000000E3(x) = 0000100Computer Science and EngineeringCopyright by Hesham El-RewiniExchange E1000  001001  000010  011011  010100  101101  100110  111111  110Computer Science and EngineeringCopyright by Hesham El-RewiniExchange E1000001010011100101110111000001010011100101110111Computer Science and EngineeringCopyright by Hesham El-RewiniButterfly Routing FunctionGiven x = {an, an-1, …, a2, a1}B(x) = {a1 , an-1, …, a2, an}X = 010001P(x) = 110000Computer Science and EngineeringCopyright by Hesham El-RewiniButterfly Example000  000001  100010  010011  110100  001101  101110  011111  111Computer Science and EngineeringCopyright by Hesham El-RewiniButterfly000001010011100101110111000001010011100101110111Computer Science and EngineeringCopyright by Hesham El-RewiniMulti-stage network000001010011100101110111000001010011100101110111Computer Science and EngineeringCopyright by Hesham El-RewiniMIN (cont.)123456789101112001010011100101110111000000001010011100101110111An 8X8 Banyan networkComputer Science and EngineeringCopyright by Hesham El-RewiniMin ImplementationControl (X)Source (S)Destination (D)X = f(S,D)Computer Science and EngineeringCopyright by Hesham El-RewiniExample X = 0 X = 1 (crossed) (straight) A B C D A B C DComputer Science and EngineeringCopyright by Hesham El-RewiniConsider this MINS1S2S3S4S5S6S7S8D1D2D3D4D5D6D7D8stage 1stage 2stage 3Computer Science and EngineeringCopyright by Hesham El-RewiniExample (Cont.)Let control variable be X1, X2, X3Find the values of X1, X2, X3 to connect:S1  D6S7  D5S4  D1Computer Science and EngineeringCopyright by Hesham El-RewiniThe 3 connectionsS1S2S3S4S5S6S7S8D1D2D3D4D5D6D7D8stage 1stage 2stage 3Computer Science and EngineeringCopyright by Hesham El-RewiniBoolean FunctionsX = x1, x2, x3S = s2, s2, s3D = d1, d2, d3Find X = f(S,D)Computer Science and EngineeringCopyright by Hesham El-RewiniCrossbar Switch M1 M2 M3 M4 M5 M6 M7 M8 P1P2P3P4P5P6P7P8Computer Science and EngineeringCopyright by Hesham El-RewiniAnalysis and performance metricsdynamic 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