A study of an evaluation methodology for unbuffered multistage interconnection networks
- 格式:pdf
- 大小:122.55 KB
- 文档页数:8
AStudyofanEvaluationMethodologyforUnbufferedMultistageInterconnectionNetworks
AhmadChadiAljundi,Jean-LucDekeyserLaboratoired’InformatiqueFondamentaldeLilleUniversitedesSceincesetTechnologiesdeLille59650Villeneuved’AscqFrancealjundi,dekeyser@lifl.frM-TaharKechadiParallelComputationalResearchGroupUniversityCollegeDublinBelfield,Dublin4Irelandtahar.kechadi@ucd.ie
IsaacD.SchersonDept.ofInformationandComputerScienceUniversityofCalifornia,IrvineIrvine,CA92697USAisaac@uci.edu
AbstractInterconnectionnetworkperformanceisakeyfactorwhenconstructingparallelcomputers.Thechoiceofanin-terconnectionnetworkusedinaparallelcomputerdependsonalargenumberofperformancefactorswhichareveryoftenapplicationsdependent.Wetryinthispapertogivetheoutlinesofaperformanceevaluationandcomparisonmethodologyusingwhatwethinkofasthemostimportantparameterstobeconsideredwhensolvingsuchaproblem.Thismethodologyisappliedonanewinterconnectionnet-workcalledMCRBnetworkandonOmeganetwork.1
1IntroductionInaparallelcomputer,amediummustprovidethemeansofcommunicationbetweenthedifferentprocessingele-ments(PEs)themselvesand/orthesystem’smemorymod-ules.Interconnectionnetworks[21],andmorepreciselyMultistageInterconnectionNetworks(MINs)arewidelyusedinparallelsystemstoprovidethismeans.Infact,com-municationtimebetweenPEsand/ormemorymodulesisofagreatimportance,toalevelthattheoverallsystemperfor-mancedependonitsrapidity,somanystudiesweredevoted2AGeneralDefinitionofUnbufferedMINsAsimpledefinitionofMINscanbefoundin[23],whereaMINisanetworkused,generally,fortheinterconnectionofasetofinputterminalstooutputterminalsusingsetsoffixed-sizeswitchesarrangedinstages.IfwesaythattheMINisofsize.ThedegreeoftheMINisdefinedasthesizeofcrossbarsusedtobuildit[12].Moreformally,aMINisasuccessionofstagesofswitchingelements(SEs)andinterconnectionwires.SEsintheremostgeneralarchitecturearethemselvesintercon-nectionnetworksofsmallsizes.ThemostusedSEsarehyperbars[3]andmorespecificallycrossbars.Ifisthe
MIN’sdegreeandistheSE’sdegree,theminimumnum-berofswitchesinastagemustbeDefinition2InanunbufferedMIN,Wedefinethethrough-putasthenumberofmessagesdeliveredtotheirdestina-tionperunitoftimeknowingthatonlyonemessagegoesthroughwhenmorethanonemessageassignedthesameinterconnectionsource.Allothermessagesarediscraded.
3.2.2PermutationcapacityPermutationcapacity[1]referstotheMIN’scapacitytoroutepermutationmessages.Wemeanbypermutationmes-sagesgroupsofmessagesofwhichdestinationsarepermu-tationsofallinputs.InordertostudythepermutationcapacityofaMIN,onemighttrytorouteacertainnumberofrandompermutationsonthenetworkandcalculatethenumberofcyclesneededtorouteallpermutationmessagestotheirdestinations.An-alyticalstudies[14]aswellasourexperienceprovedthatroutingrandompermutationsisnotefficientforthepermu-tationcapacitystudy.Therefore,frequentlyusedpermuta-tions[14]mustbeusedforsuchananalysis.Toestablishthiscomparativestudy,acertainnumberofthesepermu-tationscanberoutedundertheassumptionthattheaccu-mulatednumberofpermutationsroutedpercyclecanbeacomparisonfactorbetweenthem.
Definition3PermutationcapacityofaMINisafactorthatmeasuresthenumberofpermutationmessagesthatcanar-rivetotallytotheirdestinationsinacertainnumberofin-terconnectioncycles.
TocalculatethepermutationcapacityofaMINwesim-ulateroutingpermutationsofonefamilyoffrequentlyusedpermutations,whichistheBPC(BitPermute/Complement)family.
Definition4[3]ABPCpermutationofasetofintegersisanothersetofintegerswhosebinaryrepresentationsarepermutationsofthebinaryrepresentationsofthefirstset.Somebitsofeachrepresentationoftheresultmightthenbe1’scomplemented.
3.2.3Network’sLatencyAnotherimportantperformanceparameteristhenetwork’slatency,whichisdefinedbelow.Thenetworklatencyanal-ysisdependsdirectlyonthemaximimnumberofcyclesneededtorouteacertainnumberofpermutationstotheirdistinations.Weusethesamepreviouslyexplainedsimula-tiontomeasuretheanalysedMINs’latency.
Definition5TheLatencyofaMINisdefinedbythenum-berofnetworkcyclesneededforallmessagesofapermu-tationtoarrivetotheirdestinations.Thisisreferredtoasthenetwork’suniversality[24].
4CaseStudiesInthissectionwegivetwoexamplesofMINsonwhichthepreviouslydefinedevaluationmethodogyistobeap-plied.ThechosenMINsaretheMCRBnetworkandtheOmeganetwork.Inthefollowingwegiveabriefdescrip-tionofeachofthem.
4.1TheMCRBNetworkNotethatforcomplexityreasons,whichwillbedis-cussedlaterinthispaper,thetopologythatwegiveofMCRBnetworkisabitdifferentfromtheoneproposedin[11].TheMCRBnetworkstructureisaring-basedtopol-ogy,referredtoaschordalrings,alsocalledloopnet-works.Chordalringshavebeenwidelyinvestigatedin[4,5,25,17].Achordalringisdefinedbyapair,de-