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

2023/10/7

ParallelAlgorithms

Chapter

0

IntroductionSpring,20182023/7/29

ParallelAlgorithms

2023/10/7主要内容0.1任课教师和课程主页0.2课程介绍

课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例2023/7/29主要内容0.1任课教师和课程主页2023/10/70.1任课教师和课程主页任课教师徐云xuyun@我的研究方向大数据挖掘和生物信息学算法并行编程模型及性能优化课程主页/~xuyun/pa.htm2023/7/290.1任课教师和课程主页任课教师2023/10/7主要内容0.1任课教师和课程主页0.2课程介绍

课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP50问题示例2023/7/29主要内容0.1任课教师和课程主页2023/10/70.2课程介绍:内容、特点和学习方式课程内容：基础知识：并行机结构模型、并行计算模型、并行算法基本知识等；非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等；数值并行算法：矩阵运算、线性方程组求解、FFT算法等；GPU算法：GPU上并行算法、多核并行算法；热点技术：区块链、全文本索引等。课程特点：追求算法上界最优(并行计算时间、并行成本、加速比)；强调严密的理论分析；展现优秀的算法思想。学习方式：课程讲授、大作业和课堂讨论相结合2023/7/290.2课程介绍:内容、特点和学习方式课2023/10/70.2课程简介:教材和主要参考书目教材：陈国良,并行算法的设计与分析（第3版）,高等教育出版社,2009.8

主要参考书目：KaiHwang,ZhiweiXu”,ScalableParallelComputing”,McGraw-Hill,1998J.JaJa,”IntroductiontoParallelAlgorithms”,AddisonWesley,1992A.Grammaetal,”IntroductiontoParallelComputing”(SecondEdition),北京：机械工业出版社,2003陈国良,“并行计算：结构·算法·编程”

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

Rajaraman,Ullman.大数据互联网大规模挖掘与分布式处理(中译本).人民邮电出版社,2015.72023/7/290.2课程简介:教材和主要参考书目教材2023/10/70.2课程简介:课程在并行计算技术中的地位2023/7/290.2课程简介:课程在并行计算技术中的2023/10/7主要内容0.1任课教师和课程主页0.2课程介绍

课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例2023/7/29主要内容0.1任课教师和课程主页2023/10/70.3课程考核和评分要求ExaminationandGrading-Lessons&Answer:10%-Paper:30%-Finalwrittenexam:60%2023/7/290.3课程考核和评分要求Examinat2023/10/7主要内容0.1任课教师和课程主页0.2课程内容介绍

课程内容、特点和授课方式教材和主要参考书目课程在并行计算技术中的地位0.3课程考核和评分要求0.4并行计算介绍什么是并行计算?为什么需要并行计算?几种实现方案并行计算的粒度并行计算的研究领域TOP500和ChinaTOP100问题示例2023/7/29主要内容0.1任课教师和课程主页2023/10/70.4并行计算介绍:什么是并行计算？Aparallelcomputerisa“collectionofprocessingelementsthatcommunicateandcooperatetosolvelargeproblemfast”.–-DavidE.CullerOrallprocessorscooperatetosolveasingleproblemDailylifeexamples:Houseconstruction//综合：并发、分布、流水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并行计算介绍:几种实现方案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并行计算介绍:几种实现方案Mul2023/10/70.4并行计算介绍:并行计算的粒度Coarse-grained(粗粒度)：LevelofjobsMiddle-grained(中等粒度)：LevelofprocessesFine-grained(细粒度)：Levelofmachineinstructions(orlower)2023/7/290.4并行计算介绍:并行计算的粒度Co2023/10/70.4并行计算介绍:研究领域Designofparallelcomputers:Howtothenumberofprocessors,communicationthroughput,datasharing,etc.Designofparallelalgorithms:Parallelalgorithmsmaybequitedifferentfromtheirsequentialcounterparts.Designofparallelsoftware:OperatingsystemsCompilesLibrariesTools:debuggers,performanceanalyzersApplicationofparallelcomputing2023/7/290.4并行计算介绍:研究领域Desig2023/10/70.4并行计算介绍:TOP500

2023/7/290.4并行计算介绍:TOP500ht2023/10/70.4并行计算介绍:TOP500

2023/7/290.4并行计算介绍:TOP500ht2023/10/70.4并行计算介绍:TOP500

神威:太湖之光国产处理器:40960

SunwaySW26010260C1.45GHzprocessors，10,649,600

cores组成:40个运算机柜和8个网络机柜，每个运算机柜中4组32块运算插件组成超节点，插件含4个运算结点（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)执行、分支预测、指令多发射、硬件预取等；抢占式或时间片轮转的多任务OS同时多线程技术(simultaneousMulti-Threading,SMT)：Intel公司实现的SMT技术就是超线程(Hyper-Threading,HT)技术，超线程技术实际上只有一个物理处理器，但从软件的角度来看，存在多个逻辑处理器。多核处理器技术：采用单芯片多处理器(ChipMultiprocessor,CMP)的设计，多核多线程(有别于单核上的超线程)2023/7/29微处理器中的并行计算（1）指令级并行(In2023/10/7典型的多核处理器（2）通用处理器：Intel——Xeon5300(四核)IBM——POWER5(双核)SUN——NIAGARA(8核)、UltraSpac(双核)网络处理器Intel——IXP2400Motorola——C-5嵌入式系统TI——OMAP，DavinciARM——ARM11MP图像处理Nvdia——GF6800多媒体处理IBM，Sony和Toshiba——Cell处理器Stanford大学——Imagine实验系统Ambric——AM2045(360核）Intel——80个核的实验处理器多核时代软件的挑战：在于并行算法和程序的并行化2023/7/29典型的多核处理