數(shù)值并行算法矩陣運算課件

2023/10/7

ParallelAlgorithms

Chapter

0

IntroductionSpring,20182023/7/29

ParallelAlgorithms

2023/10/7主要內(nèi)容0.1任課教師和課程主頁0.2課程介紹

課程內(nèi)容、特點和授課方式教材和主要參考書目課程在并行計算技術(shù)中的地位0.3課程考核和評分要求0.4并行計算介紹什么是并行計算?為什么需要并行計算?幾種實現(xiàn)方案并行計算的粒度并行計算的研究領(lǐng)域TOP500和ChinaTOP100問題示例2023/7/29主要內(nèi)容0.1任課教師和課程主頁2023/10/70.1任課教師和課程主頁任課教師徐云xuyun@我的研究方向大數(shù)據(jù)挖掘和生物信息學算法并行編程模型及性能優(yōu)化課程主頁/~xuyun/pa.htm2023/7/290.1任課教師和課程主頁任課教師2023/10/7主要內(nèi)容0.1任課教師和課程主頁0.2課程介紹

課程內(nèi)容、特點和授課方式教材和主要參考書目課程在并行計算技術(shù)中的地位0.3課程考核和評分要求0.4并行計算介紹什么是并行計算?為什么需要并行計算?幾種實現(xiàn)方案并行計算的粒度并行計算的研究領(lǐng)域TOP500和ChinaTOP50問題示例2023/7/29主要內(nèi)容0.1任課教師和課程主頁2023/10/70.2課程介紹:內(nèi)容、特點和學習方式課程內(nèi)容：基礎(chǔ)知識：并行機結(jié)構(gòu)模型、并行計算模型、并行算法基本知識等；非數(shù)值并行算法：排序、選擇、組合搜索、串匹配、圖論算法等；數(shù)值并行算法：矩陣運算、線性方程組求解、FFT算法等；GPU算法：GPU上并行算法、多核并行算法；熱點技術(shù)：區(qū)塊鏈、全文本索引等。課程特點：追求算法上界最優(yōu)(并行計算時間、并行成本、加速比)；強調(diào)嚴密的理論分析；展現(xiàn)優(yōu)秀的算法思想。學習方式：課程講授、大作業(yè)和課堂討論相結(jié)合2023/7/290.2課程介紹:內(nèi)容、特點和學習方式課2023/10/70.2課程簡介:教材和主要參考書目教材：陳國良,并行算法的設(shè)計與分析（第3版）,高等教育出版社,2009.8

主要參考書目：KaiHwang,ZhiweiXu”,ScalableParallelComputing”,McGraw-Hill,1998J.JaJa,”IntroductiontoParallelAlgorithms”,AddisonWesley,1992A.Grammaetal,”IntroductiontoParallelComputing”(SecondEdition),北京：機械工業(yè)出版社,2003陳國良,“并行計算：結(jié)構(gòu)·算法·編程”

北京：高等教育出版社，2011

Rajaraman,Ullman.大數(shù)據(jù)互聯(lián)網(wǎng)大規(guī)模挖掘與分布式處理(中譯本).人民郵電出版社,2015.72023/7/290.2課程簡介:教材和主要參考書目教材2023/10/70.2課程簡介:課程在并行計算技術(shù)中的地位2023/7/290.2課程簡介:課程在并行計算技術(shù)中的2023/10/7主要內(nèi)容0.1任課教師和課程主頁0.2課程介紹

課程內(nèi)容、特點和授課方式教材和主要參考書目課程在并行計算技術(shù)中的地位0.3課程考核和評分要求0.4并行計算介紹什么是并行計算?為什么需要并行計算?幾種實現(xiàn)方案并行計算的粒度并行計算的研究領(lǐng)域TOP500和ChinaTOP100問題示例2023/7/29主要內(nèi)容0.1任課教師和課程主頁2023/10/70.3課程考核和評分要求ExaminationandGrading-Lessons&Answer:10%-Paper:30%-Finalwrittenexam:60%2023/7/290.3課程考核和評分要求Examinat2023/10/7主要內(nèi)容0.1任課教師和課程主頁0.2課程內(nèi)容介紹

課程內(nèi)容、特點和授課方式教材和主要參考書目課程在并行計算技術(shù)中的地位0.3課程考核和評分要求0.4并行計算介紹什么是并行計算?為什么需要并行計算?幾種實現(xiàn)方案并行計算的粒度并行計算的研究領(lǐng)域TOP500和ChinaTOP100問題示例2023/7/29主要內(nèi)容0.1任課教師和課程主頁2023/10/70.4并行計算介紹:什么是并行計算？Aparallelcomputerisa“collectionofprocessingelementsthatcommunicateandcooperatetosolvelargeproblemfast”.–-DavidE.CullerOrallprocessorscooperatetosolveasingleproblemDailylifeexamples:Houseconstruction//綜合：并發(fā)、分布、流水Carmanufacturing//流水線Grocerystoreoperation//分布2023/7/290.4并行計算介紹:什么是并行計算？A2023/10/70.4并行計算介紹:為什么需要并行計算？(1)Interestinparallelismsincetheveryancienteraofcomputers(e.g.ILLIACIVof1967had64processors)ParallelProcessingisaneffectiveanswerforthetremendousfuturecomputingrequirements.applicationsimpulses:Data-intensiveapplications:videoconferencing,virtualreality,largedatabaseanddatamining,speechrecognition,biology,imageandsignalprocessing,etcComputing-intensiveapplications:numericalsimulation(e.g.forecasting,manufacturing,chemistry,aerodynamics)Network-intensiveapplicationMulticoreandmanycoreandcloudcomputing2023/7/290.4并行計算介紹:為什么需要并行計算2023/10/70.4并行計算介紹:為什么需要并行計算？(2)Grandchallenges:Sciencetoday:experimentation,theory,simulation(orcomputation)SimulationreliesheavilyonparallelprocessingMulticoreandManycoreInonewords:ParallelprocessingpromisesincreaseofPerformance(e.g.large,fast,cost)ReliabilityLargesetofcomputationalproblemsareinherentlyparallelinnature.Buttheirexistingapplicationsaredesignedforuniprocessorsystems.Theirparallelizationisrequired.2023/7/290.4并行計算介紹:為什么需要并行計算2023/10/70.4并行計算介紹:幾種實現(xiàn)方案Multi-CorePC,GPU(lowestcost)Clusterofworkstations(lowercost)Multiprocessorworkstations($60,000)DECFirefly,ApolloDN10000,SUNSPARCstation20Sharedmemorymultiprocessors($200,000-400,000)SequentSymmetry,EncoreMultimax,SGIChallenge,SUNSPARCserver2000Distributedmemorymulticomputers($200,000-400,000)InteliPSC/860,NCUBE/2,MeikoMassivelyparallelprocessors($5,000,000)IntelParagon,TMCCM-5,CRAYT3D,IBMSP-22023/7/290.4并行計算介紹:幾種實現(xiàn)方案Mul2023/10/70.4并行計算介紹:并行計算的粒度Coarse-grained(粗粒度)：LevelofjobsMiddle-grained(中等粒度)：LevelofprocessesFine-grained(細粒度)：Levelofmachineinstructions(orlower)2023/7/290.4并行計算介紹:并行計算的粒度Co2023/10/70.4并行計算介紹:研究領(lǐng)域Designofparallelcomputers:Howtothenumberofprocessors,communicationthroughput,datasharing,etc.Designofparallelalgorithms:Parallelalgorithmsmaybequitedifferentfromtheirsequentialcounterparts.Designofparallelsoftware:OperatingsystemsCompilesLibrariesTools:debuggers,performanceanalyzersApplicationofparallelcomputing2023/7/290.4并行計算介紹:研究領(lǐng)域Desig2023/10/70.4并行計算介紹:TOP500

2023/7/290.4并行計算介紹:TOP500ht2023/10/70.4并行計算介紹:TOP500

2023/7/290.4并行計算介紹:TOP500ht2023/10/70.4并行計算介紹:TOP500

神威:太湖之光國產(chǎn)處理器:40960

SunwaySW26010260C1.45GHzprocessors，10,649,600

cores組成:40個運算機柜和8個網(wǎng)絡(luò)機柜，每個運算機柜中4組32塊運算插件組成超節(jié)點，插件含4個運算結(jié)點（2個處理器）計算能力:理論值:125,435.9TFLOPS實際值:93,014.6TFLOPS主存:1,310,720GB2023/7/290.4并行計算介紹:TOP500ht中國高性能計算機性能TOP100排行榜

中國高性能計算機性能TOP100排行榜

中國高性能計算機性能TOP100排行榜

中國高性能計算機性能TOP100排行榜

中國高性能計算機性能TOP100排行榜

中國高性能計算機性能TOP100排行榜

2023/10/7微處理器中的并行計算（1）指令級并行(Instruction-levelParallelismILP)：亂序(outoforder)執(zhí)行、分支預測、指令多發(fā)射、硬件預取等；搶占式或時間片輪轉(zhuǎn)的多任務(wù)OS同時多線程技術(shù)(simultaneousMulti-Threading,SMT)：Intel公司實現(xiàn)的SMT技術(shù)就是超線程(Hyper-Threading,HT)技術(shù)，超線程技術(shù)實際上只有一個物理處理器，但從軟件的角度來看，存在多個邏輯處理器。多核處理器技術(shù)：采用單芯片多處理器(ChipMultiprocessor,CMP)的設(shè)計，多核多線程(有別于單核上的超線程)2023/7/29微處理器中的并行計算（1）指令級并行(In2023/10/7典型的多核處理器（2）通用處理器：Intel——Xeon5300(四核)IBM——POWER5(雙核)SUN——NIAGARA(8核)、UltraSpac(雙核)網(wǎng)絡(luò)處理器Intel——IXP2400Motorola——C-5嵌入式系統(tǒng)TI——OMAP，DavinciARM——ARM11MP圖像處理Nvdia——GF6800多媒體處理IBM，Sony和Toshiba——Cell處理器Stanford大學——Imagine實驗系統(tǒng)Ambric——AM2045(360核）Intel——80個核的實驗處理器多核時代軟件的挑戰(zhàn)：在于并行算法和程序的并行化2023/7/29典型的多核處理