分布式計(jì)算機(jī)并行處理技術(shù)英文文獻(xiàn)

AMODERNCOURSEONPARALLELANDDISTRIBUTEDPROCESSINGLubomirIvanovDepartmentofComputerScienceIonaCollege715NorthAvenueNewRochelleNY10801tel.:914-633-2342ABSTRACTTherapidadvancesinboththedevelopmentandtheuseofparallelcomputingsystemshasledtotheneedforhighlytrainedprofessionalswithaknowledgeofboththehardwareandthesoftwareaspectsofparallelanddistributedcomputing.Wepresentacourseaimedatpreparingstudentsforthedemandsoftheworkplacebygivingthemhands-onexperienceworkingwithparallelcomputersandsoftwareAdditionallythiscourseemphasizestheessentialconnectionsbetweenComputerScienceandotherdisciplinessuchasBiologyBiochemistryPhysicsandAstronomywheretheuseofparallelcomputingiscommonplace.IINTRODUCTIONParallelcomputingwhichformanyyearswasconsideredapurelyacademicendeavorisgraduallybecominganecessityofmodernmainstreamcomputingTherearemanyreasonsforthis:ThecurrentlevelofmicroprocessortechnologyseemstobefinallyreachingthelimitoftheclockspeedatwhichCPUscanbeoperatedwithreasonablecoolingClassicalparallelcomputingtechniquessuchasSIMDhavebeenreintroducedinthecontextofgeneral-purposemicroprocessorsOntheotherhandtherapidadvancesinBiologyChemistryPhysicsandAstronomyhavedramaticallyincreasedtheneedforever-morepowerfulcomputationalplatformsformodelingandsimulatingcomplexrealworldphenomenaandprocessesImmergingnewfieldssuchasBiocomputinghavespannedtheboundariesbetweenComputerScienceandotherdisciplinesdemandinggreaterbreadthanddepthofknowledgeandskillsfromthepractitionersTheseskillsincludeanin-depthunderstandingofparallelcomputingbothfromahardwareandsoftwarepointofviewandcanonlybeacquiredthroughextensivehands-onexperienceworkingonparallelsystemsandprojects.TopreparesuchhighlytrainedprofessionalscapableofdesigningimplementingandoperatingparallelsystemsatthesoftwareandhardwarelevelComputerScienceprogramsmustincludeawidercoverageofparallelcomputingintheircurriculaTraditionallycoursesonparallelcomputingaretaughtaselectivestoseniorsorgraduatestudentsAtypicalcourseonparallelcomputingusuallyincludesahistoricaloverviewofthemajorarchitecturalapproachesandhistoricallysignificantmachinescoupledwithabriefintroductiontovariousparallelprogrammingparadigmsInthecontextofmodernparallelarchitecturesandparallelprogrammingneedssuchatreatmentofthesubjectisinsufficientWhilelearningabouttheILLIACIVandtheCrayYMPmaybeinterestingfromthepointofviewofstudyingthediversityofdesigndecisionsemployedintheseearlyarchitecturesitdoeslittletopreparestudentsforthedemandsofmodernparallelprocessingInthispaperweoutlinethestructureandcontentsofaupper-levelundergraduatecourseonParallelandDistributedComputingwhichplacestheemphasisprimarilyonmoderntechniquesforparallelandthreadprogrammingbackedupbyasufficientexposuretomodernparallelarchitecturesandtheoryThecoursecentersaroundseveralrelativelylarge-scaleprojectsbasedonproblemsofcurrentinteresttothescientificcommunityTheseprojectsaretobeimplementedbystudentsusinglanguagesthatsupportthreads(e.gJavaandparallelprogramminglibrariessuchastheMessagePassingInterface(MPIInadditiontodevelopingparallelalgorithmicthinkingandprogrammingskillsstudentslearntoestimatetheexpectedperformanceoftheirsoftwarebyanalyzingtherunningtimeoftheiralgorithmsasafunctionofthenumberandtypeofprocessesphysicalCPUsandthecommunicationcapabilityoftheinterconnectionnetworkStudentsbecomefamiliarwithanumberofkeymodernparallelarchitecturesstudycertainaspectsofdistributedoperatingsystemsdevelopmentandunderstandtheissuesofmappingvirtualprocessestotheunderlyingphysicalhardwareofthemachineinordertomaximizeperformance.Intheremainderofthispaper,weoutlinetheneedforparallelanddistributedcomputingdiscussabasicclassificationofparallelarchitecturesandsoftwareconsidersomemoderntrendsinparallelcomputingandpresentthespecificsofourParallelandDistributedComputingcourse.IITHENEEDFORAPARALLELANDDISTRIBUTEDCOMPUTINGCOURSEThecurrentlevelofmicroprocessorimplementationtechnologyhasreachedsub-100nmrangeTheever-increasingcircuitcomplexitypackedintoanever-smallerspaceinvariablyleadstoproblemssuchasquantummechanicaleffectsandheatthatatthecurrentleveloftechnologyaredifficultorimpossibletoovercomeWhilecompaniesareactivelyresearchingalternateimplementationtechnologiesandmaterials(e.g“quantumwell”transistorsbasedonInSb[1]thecurrentmicroprocessorimplementationtechnologyseemstohavereachedthepeakclockspeedatwhichconventionalcoolingcanstillbeemployedInfactthatispreciselythereasonwhythelatestIntelPentium-Dchipsrunatalower(upto3.4GHzclockspeedcomparedtotheirpredecessors(max3.8GHzTheydohoweverofferdualcoretechnologywhichwhenproperlyusedbythesoftwarepromisestosignificantlyimproveperformanceOthertraditionalparallelprocessingconceptshavefoundtheirwayintotheinstructionsetsofmodernCPUssuchastheMMXandSSE(StreamingSIMDExtensionsintheIntelandAMDprocessors’instructionssetsNon-traditionalhighlyparallelarchitecturessuchasNeuralNetworksandCellularAutomatahavehelpeddealwithproblemsforwhichalgorithmsareeitherdifficultorimpossibletodesignAtthesoftwarelevelthreads-theabilitytosplitaprocessintoindependentandconcurrenttasks–havebeenwidelyacceptedandthreadsupporthasbeenincorporatedintomostpowerfulprogramminglanguagessuchasC++andJavaThemajorityofmoderngeneral-purposeaswellasembeddedapplicationsaremultithreadedwhichcontributesgreatlytotheirefficiencyOntheotherhandparallelprocessinglibrariessuchasPVM(ParallelVirtualMachineandMPI(MessagePassingInterfacehavebecomethebackbonefordevelopinghighlycomplexapplicationsfordealingwithavarietyofcomputationallydemandingproblemsfromAstronomyPhysicsChemistryBiologyandEconomicsTherecentadvancesinBio-ChemistryDNA-analysisatmosphericresearchetcaredueprimarilytotheavailabilityofhigh-performanceparallelarchitecturesandsupportingsoftwareIngeneralwithtraditionalmicroprocessortechnologyfacingfundamentallimitationsandwithnovelcomputingapproaches(quantumcomputingetc.stillverymuchinanearlyresearchphaseparallelprocessingofferstheonlyrealopportunityforcontinuedincreaseoftheperformanceofcomputingsystemsThecomputerindustrybothsoftwareandhardware-hasembracedparallelprocessinganditisnolongerconsideredapurelyacademicendeavorIronicallyitisintheacademiccirclesthatparallelcomputingisstillregardedwithskepticismMostengineering-typeuniversitiesofferseniorlevelelectivesonParallelProcessingwhichmoreoftenthannotprovideabroadhistoricaloverviewofthefieldwithoutemphasisonthemodernaspectsofparallelprocessingSomesuchcoursestakethe“hardware”approachtoparallelcomputingandtracetheevolutionofparallelarchitecturesfromitsoriginsinthe1960’sthroughtherecentpastbyexamininganumberofmachinesrepresentingtypicalarchitecturalapproachese.gtheILLIACIVastherepresentativeofSIMDmachinestheCRAYYPMasatypicalvectorprocessorarchitecturetheCRAYT3Dasaclassicshared-memoryMIMDdesignetcSmallsnippetsofcodeareusedtoillustratespecificissuesinprogrammingthemachinesinquestionOtherParallelProcessingcoursesignorethearchitecturalaspectsofparallelprocessingcompletelyandconcentrateinsteadonexploringanumberofdifferentprogrammingparadigmsAtmostliberal-artscollegescoursesonParallelProcessingareusuallynotofferedTheonlyaspectsofparallelcomputingthatstudentsareexposedtoarepipeliningandsuperscalarprocessorswhicharebrieflycoveredinmostComputerOrganizationandArchitecturecoursesTheconceptofathreadisusuallymentionedintheOperatingSystemscoursebutfewcoursesofferstudentshands-onexperienceworkingwiththreadsIIIPARALLELANDDISTRIBUTEDCOMPUTINGInthispaperwetakealookatthecurrentstateofparallelanddistributedcomputingandoutlineacoursewhichstrivestostrikeabalanceamongthetheoreticalhardwareandsoftwareaspectsofmodernparallelanddistributedcomputingWebelievethatitisimpossibletocoverinasinglecoursethemultitudeofarchitecturalandsoftwareapproachesaswellastheextensivetheorythathasbeendevelopedoverthepastfewdecadesThuswesacrificesomeofthebreadthofthesubjectforamoredetailedtreatmentofspecificareaswhichareessentialinpresent-dayparallelcomputing.1TheCurrentStateofParallelandDistributedComputingBeforeweconsiderthecontentsofthecourseweneedtotakeabrieflookatthestateofmodernparallelanddistributedcomputingModernparallelarchitecturescanbelooselyclassifiedasdata-parallelorcode-parallelDataparallelarchitecturesarethosewhichapplythesameoperationtomultiplestreamsofdataconcurrentlyThetwomaincategoriesofdata-parallelmachinesarevectorandSIMD(SingleInstruction/MultipleDataStreamarchitecturesInadditionsomemicroprocessorssuchastheIntelPentiumandtheAMDAthlonprovidethesocalledStreamingSIMDExtensions(SSEoftheirrespectiveinstructionsetswhichallowsimultaneousoperationonseveralintegersorfloatingpointnumbersSomenon-traditionalmodelsofcomputationsuchasArtificialNeuralNetworksandCellularAutomataalsobelongtothisclassThecode-parallelarchitecturesarethosewhichexecutecodeinparallelDependingonthegrainofparallelismthesearchitecturesfallintothefollowinggroups:Instruction-levelparallelarchitectures:theseexecutemultipleinstructionsconcurrentlyand/orinanoverlappedfashionThisclassincludesthepipelinedsuperscalarandVLIWarchitectures.Thread/Process-levelparallelarchitectures:theseexecutemultipleprocesses/threadsconcurrentlyandincludetheso-calleddistributed-andshared-memoryMIMD(MultipleInstruction/MultipleDataStreammachines.MostmodernarchitecturesoftenspantheboundariesofthesecategoriesandoffercombinationsofapproachestoparallelismForexampletheIntelPentiumprocessorsareessentiallyinstruction-levelparallelarchitecturesthatemploybothpipeliningandsuperscalarprocessingbutalsoallowstreamingSIMDoperationsforspecificmultimediatypesofdataaswellasdual-corecapabilitywhichallowsatrulyparallelthreadexecutiontobescheduledbytheoperatingsystemInrecentyearsanumberofsignificanthardwareandsoftwaretrendshaveemergedandestablishedthemselvesasthepredominantwaytoemployparallelanddistributedprocessing:Clustercomputing:Thisapproachbelongstothethread/process-levelparallelarchitecturecategory(usuallydistributedmemoryMIMDOriginallyknownas“poorman’ssupercomputing”theideaistousearelativelylargecollectionofinexpensiveoff-the-shelfmicroprocessorssuchasIntelPentiumsorDECAlphasandinterconnectthemusingregularEthernetTheperformancegainisnotassignificantaswithatruesupercomputerwhichusesspecializedprocessorsandoptimizedinterconnectionnetworksandroutingalgorithmsbutthecostofaclusterismanytimeslowerthanthatofatypicalsupercomputerInrecentyearsclustercomputinghasbecomethepredominantwayofimplementinghigh-performancesystemsMostcomputermanufacturerssuchasDellHPIBMandIntelnowofferrelativelyinexpensiveclustersranginginpricefrom$20,000toabout$100,000Takentoahigherleveltheideaofclustercomputinghasbecomethebasisforthedesignandimplementationofmanyoftoday’smostpowerfulmachinessuchasBlueGene/L[2]ASCPurple[3]andASCIRed[4]TheMessagePassingInterface(MP[5]:Messagepassingisapowerfulmethodforprocesses/threadstoexchangedatawhencollaboratingonsolvingalargeproblemMPIisalibraryspecificationformessagepassingwhichhasestablisheditselfasthede-factostandardintheparallelprocessing(inparticularMIMDcommunitypushingasidealltheoldermessagepassingmethodssuchasPVMTheMPIspecificationhasbeenimplementedintoCC++andFortranlibrariesJavaisnotdirectlysupportedbuttherecentlydevelopedmpiJava[6]interfaceprovidestheabilitytointerfaceJavaprogramstothestandardMPITheuseofMPIallowsthecreationofextremelycomplexandpowerfulparallelprogramsMPIisuniversallyusedwhenwritinglarge-scalecomputingsimulationsofbiologicalprocessessuchasprotein-foldingorastrophysicalprocessessuchasN-bodyinteractionsOtherapplicationsthatrelyheavilyontheuseofMPIareweather-predictionsoftwarefluid-dynamicalcomputationpackagesandevenseismicresearchtools.Threads:Theabilitytosplitaprocessintoanumberoflightweightindependentandconcurrentsub-processes-threads-hasrevolutionizedsoftwaredevelopment-onallplatformsDevelopingmultithreadedapplicationsrequiresanewsetofskillsandanewtypeofalgorithmicthinkingOntheonehandthreadsoffertheprogrammerstheconvenienceofconcentratingonimplementingaparticulartaskwithoutworryingabouthowtointegrateitinthelargercontextofanapplication-iftwotasksneedtobeperformedconcurrentlytheneachisdesignedasaseparatethreadandstartedindependentlyoftheotherOntheotherhandthreadprogrammingisnotwithoutitsownsetofchallengesThreadsoftenrequiresynchronization:MultiplethreadsmustnotbeallowedtosimultaneouslyupdateanobjectAlternatelyonethreadmaycomputearesultneededbyanotherthreadandtheinteractionbetweenthetwomustbecarefullyorchestratedReal-timeapplicationsofthreadsinembeddedsystemsraiseanumberofadditionalchallengessuchastimingconstraintsdeadlockavoidanceandgeneralsoftwarequalitycontroltonameafewNewstandardsandlanguagesubsetssuchastheJava2:MicroEditionarespecificallydesignedtoservetheneedforthreadprocessinginembeddedsystems.High-PerformanceFortran:Whilecode-parallelarchitecturesrelyprimarilyonthreadprocessingandmessagepassingdata-parallelarchitecturesrequireadifferentsetofstandardsandlanguageswhichincludeconvenientprimitivesfordistributingdata(vectorsmatricesetc.amongprocessorssothatitcanbemanipulatedinparallelTheHighPerformanceFortranForum[7]hasdevelopedanumberofextensionsofFortran90knowncollectivelyasHighPerformanceFortran(HPFtohelpprogrammerswritedata-parallelprogramsSomecomplexfluid-dynamicandastrophysicalsimulationshavebeenimplementedusingHPFbutconsideringtheoverallpredominanceofMIMDarchitecturesandmessagepassinginmodernsupercomputingthesignificanceofHPFissomewhatreducedInviewofthesetrendsourParallelandDistributedComputingcourseconcentratesonclustercomputingthreadprocessingandmessagepassingWeaimtogiveourstudentsafundamentalunderstandingofthebasicconceptsandchallengesintheseareasandprovidehands-onexperiencebyengagingthestudentsinprojectsthatusetheaforementionedlanguageslibrariesandtechniques2.TheParallelandDistributedComputingCourseThecourseincorporatesalecture-alab-andaprojectcomponentThelecturescoverthebasictheoryofparallelcomputingaswellasdetailsofspecificarchitecturesdesigndecisionsandtradeoffssoftwareparadigmsetcThelabsallowstudentstogainhands-onexperiencewiththematerialpresentedduringlecturesbyapplyingitinthecontextofsmallcase-studiesandprogrammingassignmentsThecoursealsoincludesseverallargerprojectswhichstudentshavetocompleteindependentlyoringroups2.1TheLectureComponentThefirstfewlecturesconcentrateonperformanceissues:estimatingexecutiontimespeedupofaparallelprogramcomparedtoaserialimplementationusingAmdalh’slawforparallelprocessingexploringtheparallelcomplexityclassesstudyingtheeffectsofcommunicationandIOontheperformanceofaparallelprogrametcTheideaistogivestudentsthetoolsforevaluatingprogramperformanceasearlyaspossibleandtogetthemusedtoconsideringfactorssuchasthenumberofprocessorstheIObottlenecketcwhendecidinghowtobestparallelizetheirprogramsNextFlynn’staxonomyisintroducedandthemaincategoriesofparallelanddistributedarchitecturesarediscussedHeretheemphasisismostlyonunderstandingtheconceptualdifferencesamongthevarioustypesofarchitecturesAtthispointthenotionsofvectorprocessingandmessagepassingareintroducedandillustratedwithafewsimpleHPFandMPIprogramswhoseexecutionistracedindetailTheroleofthecompilerandtheoperatingsysteminhandlingparallelismisalsodiscussedThisleadnaturallytothediscussionofthreadsThreadsaredefinedasindividualsequentialcontrolflowswithinanexecutingprogramUser-levelvskernellevelthreadsarestudiedandtheadvantagesanddisadvantagesofeacharediscussedfromthepointofviewofcontextswitchingoverheadcooperativemultitaskingissuesetcThreadsynchronizationisstudiedinthecontextoftheclassicalproducer-consumerproblem:AhandshakingprotocolfordataexchangebetweenaproducerandaconsumerprocessandpossibleproblemsthatmayariseareexaminedindetailandillustratedwithspecificcodeexamplesOtherissuessuchaspreventingsimultaneouswriteaccesstoasharedresourceandthreaddeadlockavoidanceareconsideredTheusesofthreadsinweb-basedapplicationsaswellasinvariousembeddedsystemsarestudiedNextthediscussioncentersonclustercomputingThearchitecturesandinterconnectionnetworkpatternsofatypicalclusterareconsideredandvariousdesigndecisionspotentialproblemsandbottlenecksarediscussedAspecificMPIprogramisusedtodemonstratetheextentoftheeffectofIOandinter-processcommunicationonthespeedofprogramexecutionThisontheonehandrelatesthetheoreticalmaterialdiscussedinthebeginningofthecoursetoaverypracticalreal-worldexampleandatthesametimeleadstoadiscussionofoptimalnetworkstructuresforparallelprocessingSomerealclusterarchitecturesareexaminedaswellThediscussionofclustercomputingintroducesstudentstotheMessagePassingInterface(MPIAbriefcomparisonwiththeParallelVirtualMachine(PVMlibraryismadeandthenthevariousaspectsofMPIareintroducedinthecontextofspecificscientificproblemsInparticulartheclassicalN-bodyproblemispresentedandvarioussolutionsareconsideredandcomparedbasedontheefficiencyoftheirparallelimplementationIftimepermitstheinstructormaychoosetopresentothertopicsofcurrentscientificinterestsuchastheprotein-foldingprobleminbiochemistryanddiscussstrategiesfordesigningparallelsimulationalgorithms-fromamathematicalspecificationtoaparallelimplementationanddebugging.Thelastpartofthecoursedealswithnon-traditionalmassively-parallelmodelsofcomputationArtificialNeuralNetworksarecomparedandcontrastedwithCellularAutomataDependingontheavailabletimeanumberofdifferentNeuralNetworkmodelscanbediscussedsuchasPerceptronsBackpropagationNetworksHopfieldNetworksetcAgeneraltheoreticaldiscussionofCellularAutomatacanleadtoaprojectonimplementingConway’sGame-of-Life2-dimensionalCellularAutomaton2.2TheLabComponentThelabcomponentissynchronizedwiththelecturematerialbutconcentratesmoreonhands-onactivitiesandassignmentsThefirstlabgivesstudentsanopportunitytoevaluatetheperformanceofseveralsimpleparallelprogramsThenextfewlabsconcentrateonthreadsandofferstudentsasetofincreasinglymorechallengingassignmentsimplementingsynchronizingpausingandrestartingthreadsetcInadditiontolearningaboutthreadsthestudents’knowledgeofJavaandtheSwingAPIisreinforcedasthecomplexityofthelaterassignmentsbecomessignificantandknowledgeacquiredinpreviousprogrammingcoursesbecomesessentialFromjustbeforethemiddleofthesemesterstudentsareformallyintroducedtoMPIVariousaspectsofMPI-point-to-pointvsbroadcastmessaginggroupingdataforcommunicationderivedtypesadvancedIOandfileIOissues-arecoveredinsuccessivelabsbyrequiringstudentstocompleteduringthecourseofthelabportionsofinstructor-preparedMPIprogramsortowritecompleteprogramsindependentlyLabassignmentswhichcannotbecompletedduringtheallocatedlabperiodareexpectedbythenextlabperiod2.3TheProjectsTheprojectsareanessentialpartoftheParallelandDistributedComputingcourseTheynotonlyprovidestudentswithadditionalhands-onexperiencebeyondthatacquiredinthelabbutallowthemtoseethe“bigpicture”-theapplicationparallelcomputingtolarge-scalecomputationallyintensiveproblemsforwhichsequentialsolutionsaretootime-consumingAdditionallytheconnectionstootherareasofresearchsuchasBiologyChemistryandPhysicsareemphasizedandtheroleofComputerScienceintheoverallcontextofScienceishighlightedTypicallythreetofourprojectsaregivenduringthecourseThefirstprojectisamultithreadedimplementationofthehandshakingcommunicationprotocoldiscussedearlierTheprotocolspecifiesasetofrulesfordataexchangebetweenasenderandareceiverthroughasharedbufferThebuffercapacitymaybeasinglebyteoracircularqueueInthecaseofasingle-bytedatabufferthestatusofthebufferisgivenbyadataflag:0forbufferempty1forbufferfullInthecaseofthebufferimplementedasacircularqueueashared“count”variableisusedtomonitortheactualnumberofitemsinthebufferThesenderandthereceiverareimplementedasseparatethreadsandtheirpropersynchronizationisemphasizedThesecondprojectisanMPIimplementationofhost/guestalgorithmforsolvingtheN-bodyproblemfromPhysicsAstronomyandBiochemistryTheN-bodyproblemdescribestheinteractionofasetofNobjects(planetsparticlesatomsormoleculesetc.throughtheforcestheyexertoneachotherThesumoftheseforcesactsoneachoftheobjectsbychangingtheobject’saccelerationandthereforeitsspatialpositionrelativetootherobjectsAsaresultofthatchangethestrengthoftheinteractionforcesischangedetcSolvingtheN-bodyproblemforlargecollectionsofobjectsisanextremelycomputationally-intensivetaskandmanydifferentalgorithmshavebeendesignedtodealwiththeproblemThehost/guestalgorithmisarelativelysimple(butnotparticularlyefficientalgorithmwhichisdiscussedduringlectureandassignedtostudentsasaMPI-basedprojectThethirdprojectisanMPI-basedimplementationofConway’sGame-of-Life2DCellularAutomatonThisprojectisparticularlyfunforstudentsandmanyofthemchoosetoimplementagraphicalinterfacewhichallowsthemtodisplaytheevolutionoftheCAcoloniesunderiteration3.Course-RelatedChallengesandObstaclesInthecontextofthepresent-dayneedforparallelanddistributedcomputingtheParallelandDistributedComputingcourseisvitalt