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-