Modeling Adaptive Routing

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

DepartmentofComputerScienceAnalyticalModelsofAdaptiveRoutingStrategiesW.A.Najjar,A.Lagman,S.SurandP.K.SrimaniTechnicalReportCS-94-105(ReplacesCS-92-138)March3,1994ColoradoStateUniversityAnalyticalModelsofAdaptiveRoutingStrategiesW.A.Najjar,A.Lagman,andS.SurandP.K.SrimaniDepartmentofComputerScienceColoradoStateUniversityFt.Collins,CO80523USAThisworkisinpartsupportedbyNSFGrantsCCR-9010240,CCR-9148225andMIP-91132681ModelingAdaptiveRoutingW.A.Najjar,A.Lagman,S.SurandP.K.SrimaniAbstractAdaptiveroutingalgorithmshavebeenfrequentlysuggestedasameansofimprovingcom-municationperformanceinmulticomputers.Thesealgorithms,unlikedeterministicrouting,canutilizenetworkstateinformationtoexploitthepresenceofmultiplepaths.Adaptiverouting,however,iscomplexandexpensive.Beforesuchschemescanbesuccessfullyin-corporatedinmultiprocessorsystems,itisnecessarytohaveaclearunderstandingofthefactorswhichaecttheirperformancepotential.Inthispaperwepresentasimpleandecientschemetomodeltheperformanceofidealizedadaptiverouting.Weevaluateabasic,high-performanceadaptivesystemusingananalyticqueueingmodelwhichapproxi-matesitsbehavior.Thisanalyticmodelpredictstheperformanceofnetworkswithvaryingparameters,andprovidesinsightintothenatureofmessagetrac.Wehavealsoconductedextensivesimulationexperiments,theresultsofwhichareusedtovalidatetheanalyticmodelandtoidentifysomeoftheconditionswhichpromotehighperformanceofadaptiveroutinginacommunicationnetwork.Keywords:Multicomputers,Interconnectionnetworks,Performanceevaluation,AdaptiveRouting,Modeling,k-aryn-cubes.AddressforCorrespondence:WalidA.NajjarDepartmentofComputerScienceColoradoStateUniversityFt.Collins,CO80525Tel:(303)491-7026Fax:(303)491-2466Email:najjar@CS.ColoState.Edu21IntroductionThesuccessoflargescalemessage-passingmulticomputersishighlydependentontheeciencyoftheirunderlyinginterconnectionnetworks.Inthepastfewyearstherehavebeentremendousimprovementsintheperformanceofmulticomputersystems,butthesehavecomeprimarilyfromadvancesinprocessortechnology.Communicationsystemshavenotkeptup,andtheincreasingdis-paritybetweenprocessorandnetworkspeedshasbecomeamajorhindrancetofurtherperformancegains.Oneapproachthathasoftenbeensuggestedasasolutiontothecommunicationlatencyproblemistheuseofadaptiveroutingtechniques.Atpresentmostcommercialmachinesusedeterministicrouting,inwhichamessagepathisfullydeterminedbytheaddressesofitssourceanddestination.Thus,messageswiththesamesourceanddestinationwoulduseexactlythesamepaths.Whiletheseschemesaresimpleandeasilyimplemented,theyaresusceptibletounnecessaryblockingofmessagesanddonotrespondtochangingconditionswithinthenetwork.Adaptiveroutingalgorithms,ontheotherhand,allowmessagepathstobedeterminedinresponsetovariationsinnetworkstate.Thisprovidesgreaterfreedominchoosingmessagepaths,whichcanpotentiallyleadtoreducedcommunicationoverhead.Thereare,however,anumberofproblemsassociatedwithadaptiverouting.First,theincreasedexibilityofadaptivealgorithmsmakethemmoresusceptibletodeadlockthandeter-ministicschemes.Inordertoavoidthecircularresourcedependencieswhichleadtodeadlock,itisnecessarytoeitherrestrictthechoiceofpathsortoincludeextrahardwareinthesystem.Thesecondproblemassociatedwithadaptiveroutingisthatitmaybediculttoimplement,andmayeitherrequireexpensivehardwareorsuerfromhighnodeswitchdelay.Inordertoaccuratelyassessthetradeoandbenetsofadaptiverouting,wemustbeabletoevaluatetheperformancepotentialofthesesystems.Recentresearchstudieshavebeguntoaddressthisissue,butasyettheproblemhasnotbeenfullyexplored.In[GN92a],GlassandNicomparedpartiallyadaptivedeadlockfreeroutingschemestodimensionorderedschemesinmeshnetworks.In[LDT93],Liuetalevaluatedexpectedchannelutilizationforaclassofdeadlock-freealgorithms,againinmeshnetworks.KimandChien[KC93]assessedtheeectsofpacketizationonadaptiveroutingperformance,Nowatzyk[Now89]hasinvestigatedacommunicationarchitectureusinganadaptivealgorithm,andrecentlyBoppanaandChalasani[BC93]presentedacomparativestudyofseveraldeadlockfreeadaptiveroutingschemes.Almostalloftheperformanceevaluation3studiesofdirectnetworks,however,havemadeusesolelyofsimulationexperiments.Incontrasttostudiesofdeterministicrouting,verylittleanalyticworkhasbeendone.Moreover,moststudieshavelookedatadaptiveroutinginisolation,withoutconsideringtherelationshipofothernetworkparameterstoroutingperformance.Thestudypresentedinthispaperisaperformanceevaluation,bothanalyticandexperi-mental,ofabasicadaptiveroutingsystemonk-aryn-cubenetworks.Preliminaryversionsofthisresearchwerepresentedin[LNSS93,NLSS94].Thegoalsofthestudyaretoevaluatetheperfor-mancepotentialofadaptiveroutingandtounderstandtheeectsofvariousnetworkparametersonroutingperformance.Thus,wehavechosentoinvestigateanidealizedsystemwithageneralroutingstrategywhichcanachievenear-optimalperformance.Thebasicmodelisexible,however,andcanbemodiedforfutureresearchonspecicnetworkdesignparametersaswellasoncostratherthanperformance.ThedetailsofthesystemaredescribedinSections2and3.Wehavederivedageneralanalyticqueueingmodelwhichapproximatesthebehaviorofadapt

1 / 31
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功