资源描述:
《西安交大并行计算理论赵银亮课件第五章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、AnalyticalModelingofParallelSystemsAnanthGrama,AnshulGupta,GeorgeKarypis,andVipinKumarToaccompanythetext``IntroductiontoParallelComputing'',AddisonWesley,2003.TopicOverviewSourcesofOverheadinParallelProgramsPerformanceMetricsforParallelSystemsEffectofGra
2、nularityonPerformanceScalabilityofParallelSystemsMinimumExecutionTimeandMinimumCost-OptimalExecutionTimeAsymptoticAnalysisofParallelProgramsOtherScalabilityMetricsAnalyticalModeling-BasicsAsequentialalgorithmisevaluatedbyitsruntime(ingeneral,asymptoticru
3、ntimeasafunctionofinputsize).Theasymptoticruntimeofasequentialprogramisidenticalonanyserialplatform.Theparallelruntimeofaprogramdependsontheinputsize,thenumberofprocessors,andthecommunicationparametersofthemachine.Analgorithmmustthereforebeanalyzedinthec
4、ontextoftheunderlyingplatform.Aparallelsystemisacombinationofaparallelalgorithmandanunderlyingplatform.AnalyticalModeling-BasicsAnumberofperformancemeasuresareintuitive.Wallclocktime-thetimefromthestartofthefirstprocessortothestoppingtimeofthelastprocess
5、orinaparallelensemble.Buthowdoesthisscalewhenthenumberofprocessorsischangedoftheprogramisportedtoanothermachinealtogether?Howmuchfasteristheparallelversion?Thisbegstheobviousfollowupquestion-whatsthebaselineserialversionwithwhichwecompare?Canweuseasubopt
6、imalserialprogramtomakeourparallelprogramlookRawFLOPcount-WhatgoodareFLOPcountswhentheydontsolveaproblem?SourcesofOverheadinParallelProgramsIfIusetwoprocessors,shouldntmyprogramruntwiceasfast?No-anumberofoverheads,includingwastedcomputation,communication
7、,idling,andcontentioncausedegradationinperformance.Theexecutionprofileofahypotheticalparallelprogramexecutingoneightprocessingelements.Profileindicatestimesspentperformingcomputation(bothessentialandexcess),communication,andidling.SourcesofOverheadsinPar
8、allelProgramsInterprocessinteractions:Processorsworkingonanynon-trivialparallelproblemwillneedtotalktoeachother.Idling:Processesmayidlebecauseofloadimbalance,synchronization,orserialcomponents.ExcessComputation:Thisiscompu