并行程序設計導論課件

Copyright?2010,ElsevierInc.AllrightsReservedChapter1WhyParallelComputing?AnIntroductiontoParallelProgrammingPeterPachecoCopyright?2010,ElsevierIncCopyright?2010,ElsevierInc.AllrightsReservedRoadmapWhyweneedever-increasingperformance.Whywe’rebuildingparallelsystems.Whyweneedtowriteparallelprograms.Howdowewriteparallelprograms?Whatwe’llbedoing.Concurrent,parallel,distributed!#ChapterSubtitleCopyright?2010,ElsevierIncChangingtimesCopyright?2010,ElsevierInc.AllrightsReservedFrom1986–2002,microprocessorswerespeedinglikearocket,increasinginperformanceanaverageof50%peryear.

Sincethen,it’sdroppedtoabout20%increaseperyear.ChangingtimesCopyright?2010AnintelligentsolutionCopyright?2010,ElsevierInc.AllrightsReservedInsteadofdesigningandbuildingfastermicroprocessors,putmultipleprocessorsonasingleintegratedcircuit.

AnintelligentsolutionCopyrigNowit’suptotheprogrammersAddingmoreprocessorsdoesn’thelpmuchifprogrammersaren’tawareofthem……ordon’tknowhowtousethem.

Serialprogramsdon’tbenefitfromthisapproach(inmostcases).Copyright?2010,ElsevierInc.AllrightsReservedNowit’suptotheprogrammersWhyweneedever-increasingperformanceComputationalpowerisincreasing,butsoareourcomputationproblemsandneeds.Problemsweneverdreamedofhavebeensolvedbecauseofpastincreases,suchasdecodingthehumangenome.Morecomplexproblemsarestillwaitingtobesolved.Copyright?2010,ElsevierInc.AllrightsReservedWhyweneedever-increasingpeClimatemodelingCopyright?2010,ElsevierInc.AllrightsReservedClimatemodelingCopyright?20ProteinfoldingCopyright?2010,ElsevierInc.AllrightsReservedProteinfoldingCopyright?201DrugdiscoveryCopyright?2010,ElsevierInc.AllrightsReservedDrugdiscoveryCopyright?2010EnergyresearchCopyright?2010,ElsevierInc.AllrightsReservedEnergyresearchCopyright?201DataanalysisCopyright?2010,ElsevierInc.AllrightsReservedDataanalysisCopyright?2010,Whywe’rebuildingparallelsystemsUptonow,performanceincreaseshavebeenattributabletoincreasingdensityoftransistors.

Butthereare

inherent

problems.Copyright?2010,ElsevierInc.AllrightsReservedWhywe’rebuildingparallelsyAlittlephysicslessonSmallertransistors=fasterprocessors.Fasterprocessors=increasedpowerconsumption.Increasedpowerconsumption=increasedheat.Increasedheat=unreliableprocessors.Copyright?2010,ElsevierInc.AllrightsReservedAlittlephysicslessonSmallerSolutionMoveawayfromsingle-coresystemstomulticoreprocessors.“core”=centralprocessingunit(CPU)

Copyright?2010,ElsevierInc.AllrightsReservedIntroducingparallelism!!!SolutionMoveawayfromsingleWhyweneedtowriteparallelprogramsRunningmultipleinstancesofaserialprogramoftenisn’tveryuseful.Thinkofrunningmultipleinstancesofyourfavoritegame.Whatyoureallywantisfor

ittorunfaster.Copyright?2010,ElsevierInc.AllrightsReservedWhyweneedtowriteparallelApproachestotheserialproblemRewriteserialprogramssothatthey’reparallel.

Writetranslationprogramsthatautomaticallyconvertserialprogramsintoparallelprograms.Thisisverydifficulttodo.Successhasbeenlimited.Copyright?2010,ElsevierInc.AllrightsReservedApproachestotheserialproblMoreproblemsSomecodingconstructscanberecognizedbyanautomaticprogramgenerator,andconvertedtoaparallelconstruct.However,it’slikelythattheresultwillbeaveryinefficientprogram.Sometimesthebestparallelsolutionistostepbackanddeviseanentirelynewalgorithm.Copyright?2010,ElsevierInc.AllrightsReservedMoreproblemsSomecodingconstExampleComputenvaluesandaddthemtogether.Serialsolution:Copyright?2010,ElsevierInc.AllrightsReservedExampleComputenvaluesandadExample(cont.)Wehavepcores,pmuchsmallerthann.Eachcoreperformsapartialsumofapproximatelyn/pvalues.Copyright?2010,ElsevierInc.AllrightsReservedEachcoreusesit’sownprivatevariablesandexecutesthisblockofcode

independentlyoftheothercores.Example(cont.)WehavepcoresExample(cont.)Aftereachcorecompletesexecutionofthecode,isaprivatevariablemy_sumcontainsthesumofthevaluescomputedbyitscallstoCompute_next_value.Ex.,8cores,n=24,thenthecallstoCompute_next_valuereturn:Copyright?2010,ElsevierInc.AllrightsReserved1,4,3,9,2,8,5,1,1,5,2,7,2,5,0,4,1,8,6,5,1,2,3,9Example(cont.)AftereachcoreExample(cont.)Onceallthecoresaredonecomputingtheirprivatemy_sum,theyformaglobalsumbysendingresultstoadesignated“master”corewhichaddsthefinalresult.Copyright?2010,ElsevierInc.AllrightsReservedExample(cont.)OnceallthecoExample(cont.)Copyright?2010,ElsevierInc.AllrightsReservedExample(cont.)Copyright?201Example(cont.)Copyright?2010,ElsevierInc.AllrightsReservedCore01234567my_sum8197157131214Globalsum8+19+7+15+7+13+12+14=95Core01234567my_sum95197157131214Example(cont.)Copyright?201Copyright?2010,ElsevierInc.AllrightsReservedButwait!There’samuchbetterway

tocomputetheglobalsum.Copyright?2010,ElsevierIncBetterparallelalgorithmDon’tmakethemastercoredoallthework.Shareitamongtheothercores.Pairthecoressothatcore0addsitsresultwithcore1’sresult.Core2addsitsresultwithcore3’sresult,etc.Workwithoddandevennumberedpairsofcores.Copyright?2010,ElsevierInc.AllrightsReservedBetterparallelalgorithmDon’tBetterparallelalgorithm(cont.)Repeattheprocessnowwithonlytheevenlyrankedcores.Core0addsresultfromcore2.Core4addstheresultfromcore6,etc.Nowcoresdivisibleby4repeattheprocess,andsoforth,untilcore0hasthefinalresult.Copyright?2010,ElsevierInc.AllrightsReservedBetterparallelalgorithm(conMultiplecoresformingaglobalsumCopyright?2010,ElsevierInc.AllrightsReservedMultiplecoresformingaglobaAnalysisInthefirstexample,themastercoreperforms7receivesand7additions.Inthesecondexample,themastercoreperforms3receivesand3additions.Theimprovementismorethanafactorof2!Copyright?2010,ElsevierInc.AllrightsReservedAnalysisInthefirstexample,Analysis(cont.)Thedifferenceismoredramaticwithalargernumberofcores.Ifwehave1000cores:Thefirstexamplewouldrequirethemastertoperform999receivesand999additions.Thesecondexamplewouldonlyrequire10receivesand10additions.

That’sanimprovementofalmostafactorof100!Copyright?2010,ElsevierInc.AllrightsReservedAnalysis(cont.)ThedifferenceHowdowewriteparallelprograms?TaskparallelismPartitionvarioustaskscarriedoutsolvingtheproblemamongthecores.

DataparallelismPartitionthedatausedinsolvingtheproblemamongthecores.Eachcorecarriesoutsimilaroperationsonit’spartofthedata.Copyright?2010,ElsevierInc.AllrightsReservedHowdowewriteparallelprogrProfessorPCopyright?2010,ElsevierInc.AllrightsReserved15questions300examsProfessorPCopyright?2010,EProfessorP’sgradingassistantsCopyright?2010,ElsevierInc.AllrightsReservedTA#1TA#2TA#3ProfessorP’sgradingassistanDivisionofwork–

dataparallelismCopyright?2010,ElsevierInc.AllrightsReservedTA#1TA#2TA#3100exams100exams100examsDivisionofwork–

dataparalDivisionofwork–

taskparallelismCopyright?2010,ElsevierInc.AllrightsReservedTA#1TA#2TA#3Questions1-5Questions6-10Questions11-15Divisionofwork–

taskparalDivisionofwork–

dataparallelismCopyright?2010,ElsevierInc.AllrightsReservedDivisionofwork–

dataparalDivisionofwork–

taskparallelismCopyright?2010,ElsevierInc.AllrightsReservedTasksReceivingAdditionDivisionofwork–

taskparalCoordinationCoresusuallyneedtocoordinatetheirwork.Communication–oneormorecoressendtheircurrentpartialsumstoanothercore.Loadbalancing–sharetheworkevenlyamongthecoressothatoneisnotheavilyloaded.Synchronization–becauseeachcoreworksatitsownpace,makesurecoresdonotgettoofaraheadoftherest.Copyright?2010,ElsevierInc.AllrightsReservedCoordinationCoresusuallyneedWhatwe’llbedoingLearningtowriteprogramsthatareexplicitlyparallel.UsingtheClanguage.UsingthreedifferentextensionstoC.Message-PassingInterface(MPI)PosixThreads(Pthreads)OpenMPCopyright?2010,ElsevierInc.AllrightsReservedWhatwe’llbedoingLearningtoTypeofparallelsystemsShared-memoryThecorescanshareaccesstothecomputer’smemory.Coordinatethecoresbyhavingthemexamineandupdatesharedmemorylocations.Distributed-memoryEachcorehasitsown,privatememory.Thecoresmustcommunicateexplicitlybysendingmessagesacrossanetwork.Copyright?2010,ElsevierInc.AllrightsReservedTypeofparallelsystemsSharedTypeofparallelsystemsCopyright?2010,ElsevierInc.AllrightsReservedShared-memoryDistributed-memoryTypeofparallelsystemsCopyriTerminologyConcurrentcomputin