数值并行算法矩阵运算ppt课件

.,2020/5/23,ParallelAlgorithmsChapter0Introduction,Spring,2018,2020/5/23,.,主要内容,0.1任课教师和课程主页0.2课程介绍课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例,2020/5/23,.,0.1任课教师和课程主页,任课教师徐云xuyun我的研究方向大数据挖掘和生物信息学算法并行编程模型及性能优化课程主页,2020/5/23,.,主要内容,0.1任课教师和课程主页0.2课程介绍课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP50问题示例,2020/5/23,.,0.2课程介绍:内容、特点和学习方式,课程内容：基础知识：并行机结构模型、并行计算模型、并行算法基本知识等；非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等；数值并行算法：矩阵运算、线性方程组求解、FFT算法等；GPU算法：GPU上并行算法、多核并行算法；热点技术：区块链、全文本索引等。课程特点：追求算法上界最优(并行计算时间、并行成本、加速比)；强调严密的理论分析；展现优秀的算法思想。学习方式：课程讲授、大作业和课堂讨论相结合,2020/5/23,.,0.2课程简介:教材和主要参考书目,教材：陈国良,并行算法的设计与分析（第3版）,高等教育出版社,2009.8主要参考书目：KaiHwang,ZhiweiXu”,ScalableParallelComputing”,McGraw-Hill,1998J.JaJa,”IntroductiontoParallelAlgorithms”,AddisonWesley,1992A.Grammaetal,”IntroductiontoParallelComputing”(SecondEdition),北京：机械工业出版社,2003陈国良,“并行计算：结构算法编程”北京：高等教育出版社，2011Rajaraman,Ullman.大数据互联网大规模挖掘与分布式处理(中译本).人民邮电出版社,2015.7,2020/5/23,.,0.2课程简介:课程在并行计算技术中的地位,2020/5/23,.,主要内容,0.1任课教师和课程主页0.2课程介绍课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例,2020/5/23,.,0.3课程考核和评分要求,ExaminationandGrading-Lessons&Answer:10%-Paper:30%-Finalwrittenexam:60%,2020/5/23,.,主要内容,0.1任课教师和课程主页0.2课程内容介绍课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例,2020/5/23,.,0.4并行计算介绍:什么是并行计算？,Aparallelcomputerisa“collectionofprocessingelementsthatcommunicateandcooperatetosolvelargeproblemfast”.-DavidE.CullerOrallprocessorscooperatetosolveasingleproblemDailylifeexamples:Houseconstruction/综合：并发、分布、流水Carmanufacturing/流水线Grocerystoreoperation/分布,2020/5/23,.,0.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-intensiveapplicationMulticoreandmanycoreandcloudcomputing,2020/5/23,.,0.4并行计算介绍:为什么需要并行计算？(2),Grandchallenges:Sciencetoday:experimentation,theory,simulation(orcomputation)SimulationreliesheavilyonparallelprocessingMulticoreandManycoreInonewords:ParallelprocessingpromisesincreaseofPerformance(e.g.large,fast,cost)ReliabilityLargesetofcomputationalproblemsareinherentlyparallelinnature.Buttheirexistingapplicationsaredesignedforuniprocessorsystems.Theirparallelizationisrequired.,2020/5/23,.,0.4并行计算介绍:几种实现方案,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-2,2020/5/23,.,0.4并行计算介绍:并行计算的粒度,Coarse-grained(粗粒度)：LevelofjobsMiddle-grained(中等粒度)：LevelofprocessesFine-grained(细粒度)：Levelofmachineinstructions(orlower),2020/5/23,.,0.4并行计算介绍:研究领域,Designofparallelcomputers:Howtothenumberofprocessors,communicationthroughput,datasharing,etc.Designofparallelalgorithms:Parallelalgorithmsmaybequitedifferentfromtheirsequentialcounterparts.Designofparallelsoftware:OperatingsystemsCompilesLibrariesTools:debuggers,performanceanalyzersApplicationofparallelcomputing,.,2020/5/23,0.4并行计算介绍:TOP500,2020/5/23,.,0.4并行计算介绍:TOP500,2020/5/23,.,0.4并行计算介绍:TOP500,神威:太湖之光,国产处理器:40960SunwaySW26010260C1.45GHzprocessors，10,649,600cores组成:40个运算机柜和8个网络机柜，每个运算机柜中4组32块运算插件组成超节点，插件含4个运算结点（2个处理器）计算能力:理论值:125,435.9TFLOPS实际值:93,014.6TFLOPS主存:1,310,720GB,.,中国高性能计算机性能TOP100排行榜,.,中国高性能计算机性能TOP100排行榜,.,中国高性能计算机性能TOP100排行榜,2020/5/23,.,微处理器中的并行计算（1）,指令级并行(Instruction-levelParallelismILP)：乱序(outoforder)执行、分支预测、指令多发射、硬件预取等；抢占式或时间片轮转的多任务OS同时多线程技术(simultaneousMulti-Threading,SMT)：Intel公司实现的SMT技术就是超线程(Hyper-Threading,HT)技术，超线程技术实际上只有一个物理处理器，但从软件的角度来看，存在多个逻辑处理器。多核处理器技术：采用单芯片多处理器(ChipMultiprocessor,CMP)的设计，多核多线程(有别于单核上的超线程),2020/5/23,.,典型的多核处理器（2）,通用处理器：IntelXeon5300(四核)IBMPOWER5(双核)SUNNIAGARA(8核)、UltraSpac(双核)网络处理器IntelIXP2400MotorolaC-5嵌入式系统TIOMAP，DavinciARMARM11MP,图像处理NvdiaGF6800多媒体处理IBM，Sony和ToshibaCell处理器Stanford大学Imagine实验系统AmbricAM2045(360核）Intel80个核的实验处理器,多核时代软件的挑战：在于并行算法和程序的并行化,2020/5/23,.,虚拟化技术（3）,虚拟化技术：目前，计算的一个重要趋势就是虚拟化。创建一个虚拟计算环境，应用程序在该独立的环境或者虚拟机上执行，这些虚拟机能够运行完整、独立的OS并充分利用多线程技术。可分为两类：运行时虚拟化这类虚拟机可以看作是OS之上的一种容器或者执行程序。如，Java虚拟机和微软的通用语言运行时环境(CommonLanguageRuntime,CLR)。系统虚拟化这类虚拟机为应用软件重新创建了一个完整的执行环境，并且运行了一个属于自己的操