1 Simulation of Modern Parallel Systems A CSIM-Bas

SimulationofModernParallelSystems:ACSIM-BasedApproachDhabaleswarK.Panda,DebashisBasak,DonglaiDai,RamKesavan,RajeevSivaram,MohammadBanikazemiandVijayMoorthyTechnicalReportOSU-CISRC-7/97-TR351SimulationofModernParallelSystems:ACSIM-BasedApproachDhabaleswarK.Panda,DebashisBasak,DonglaiDai,RamKesavan,RajeevSivaram,MohammadBanikazemiandVijayMoorthyDepartmentofComputerandInformationScienceTheOhioStateUniversityColumbus,OH-43210-1277July21,1997ABSTRACTComponentsofmodernparallelsystemsarebecomingquitecomplexwithmanyfeaturesandvariations.Anintegratedmodelingofthesecomponents(interconnectionnetwork,messaginglayer,programmingmodel,andcomputation-communicationcharacteristicsofapplications)isessentialtoderivedesignguidelinesfornextgenerationparallelsystems.Mostofthecur-rentsimulation-basedmodelingplatformsdonotsupportsuchintegratedmodeling.ThispaperpresentsoureortatTheOhioStateUniversitytowardsintegratedmodelingofparallelsystems.BasicfeaturesofourCSIM-basedWormhole-routedMultiprocessorSimulator(WORMulSim)areoutlined.Asetoftechniquesusedinoursimulatortomodeldierentnetworkcompo-nents(suchasswitches,links,wormhole/cut-throughswitchingtechniques,routingprotocols,networkinterfaces),messaginglayerwithbasiccommunicationprimitives,distributedsharedmemoryprogrammingmodel,andcomputation-communicationcharacteristicsofapplicationsarepresented.Somesampleperformancemeasuresofoursimulatoroncurrentgenerationworkstationsarereportedtodemonstratethefeasibilityofintegratedmodelingwithlowcom-putationaloverhead.CurrentlywithForeSystems,Inc.,Warrendale,PA,aftergraduation.2Contents1INTRODUCTION52OVERVIEWOFWORMulSim73MODELINGINTERCONNECTIONNETWORKS93.1NetworkResources...................................93.2SwitchingTechniques..................................103.3Routing.........................................133.4Topologies........................................134MODELINGMESSAGINGLAYER144.1AccountingforMessagingOverheads.........................154.2Packetization......................................155DISTRIBUTEDSHAREDMEMORYPROGRAMMINGMODELLAYER165.1NodeArchitecture...................................165.2Cache-CoherenceProtocol...............................176MODELINGAPPLICATIONLAYER187PERFORMANCEMEASURESOFWORMulSim188CONCLUSIONSANDFUTUREWORK2031INTRODUCTIONDesignofaparallelsysteminvolvestheintegrationofseveralhardwareandsoftwarecompo-nents.Theoverallperformanceofthesesystemsisdependentontheinteractionbetweenthesecomponentsaswellasonthecomputation-communicationcharacteristicsofapplications.Sincethesecomponentsinteractataninstructionlevel,modelingandevaluationofthesecomponentsbysimulationhasbeenastandardpracticebeforebuildingaparallelsystem.Forthepurposeofmodeling,aparallelsystemcanbedividedintofourmajorlayers:1)theinterconnectionnetworklayer,2)themessaginglayerwithbasiccommunicationprimitives,3)theprogrammingmodellayer,and4)theapplicationlayer.Traditionally,therehavebeentwoschoolsofthoughtonmodelingtheabovelayers.Undertherstschoolofthought,theinterconnectionnetworklayerismodeledingreatdetail(topology,switchingtechnique,owcontrol,buering,etc.).Thesemodelsarethenevaluatedinisolationusingsynthetictracsuchasuniformandhot-spottrac,whicharegeneratedbasedonprobabilisticmodels.Thesestudiesmodelnetworkcontention/congestionaccurately.Theperformanceoftheinterconnectionnetworkistypicallyevaluatedusingtwomeasures:latencyvs.throughputandsustainedloadvs.appliedload.However,thesestudiestypicallyignorelayers3and4.Thesestudiesalsoignorethecause-eectrelationshipbetweenmessagesinanetwork{animportantfactorintheexecutionofparallelprograms.Thus,thisapproachisnotsuitableforevaluatingtheoverallperformanceofanapplicationontheparallelsystembeingdesigned.Thesecondschoolofthoughtfocusesonmodelinglayers3and4ingreatdetail.However,thesemodelsuseverysimplisticassumptionsabouttheinterconnectionnetworkandmessaginglayers.Thesesimplisticassumptionsignorecontention/congestioninsidethenetworkaswellasatthenetworkinterfaces.Thus,theseevaluationsignoreimportantinteractionbetweencomputationandcommunicationsteps.Moderninterconnectionnetworksandnetworkinterfacesarebecomingverysophisticatedwithalotoffeaturesandexibilities.Designsofcurrentgenerationparallelsystemsshowthatlayers2and3needtobesupportedinanextremelyecientmanneronaparallelsystem(supportingeitherdistributedmemoryordistributedsharedmemoryparadigms)toachievelow-latencyandhigh-bandwidthcommunication.Thus,itiscriticalthatallfourlayersbemodeledinanintegratedmannertoaccuratelyestimatetheoverallexecutiontimeofanapplicationonaproposedparallelsystem.WeatOSUrealizedthisneedafewyearsagoandtookonthechallengeofmodelingparallelsystemsinanintegratedmanner.Inordertoimplementintegratedmodeling,asimulationenvironmentisneededwhereactualapplications(inuser-levellanguageslikeCorFortran)canbeexecutedonthesimulatedmodelofthesystemencompassinglayers1-4.Suchanenvironmentshouldbecapableofproducingapplicationresultsduringexecutionaswellasprovidinguser-levelandsystem-levelperformancenumbers(suchasoverallexecutiontimeofanapplication,timeelap