并行计算概述.pptx

并行计算Parallel Computing基本概念2024/10/26 周六2如何满足不断增长的计算力需求？n用速度更快的硬件，也就是减少每一条指令所需时间n优化算法（或者优化编译）n用多个处理机用多个处理机(器器)同时解决一个问题同时解决一个问题q并行计算并行计算2024/10/26 周六3串行计算与并行计算2024/10/26 周六4并行的层次n程序级并行程序级并行n子程序级并行子程序级并行n语句级并行n操作级并行n微操作级并行并行粒度粗细2024/10/26 周六5FLOPSnFloating point number Operations Per Second-每个时钟周期执行浮点运算的次数 n理论峰值CPU主频每时钟周期执行浮点运算数CPU数目n部分处理器每时钟周期执行浮点运算数：2024/10/26 周六6www.top500.org2024/10/26 周六7Top5002007年11月n高居榜首的依然是来自高居榜首的依然是来自IBM的的“蓝色基因蓝色基因/L”。自从2004年11月以来，该系统已经连续三年遥遥领先连续三年遥遥领先，而且计算能力不断提升，Linpack基准测试性能基准测试性能478.2 TFlop/s(每秒478.2万亿次运算)，而半年前还是280.6 TFlop/s n拿下亚军位置的还是IBM，不过换成了一台落成不久的“蓝色基因蓝色基因/P”。位于德国尤里希研究中心的这套新系统运算能力167.3 TFlop/s，不过按照IBM的设计规划，蓝色基因/P的性能将有望突破1 TFlop/s大关，即每秒一千万亿次运算。2024/10/26 周六8Top5002007年11月n第三名也是个新面孔，同时也是新墨西哥墨西哥计算应用中心(NMCAC)的第一套超级计算机，由SGI基于Altix ICE 8200打造，计算能力126.9 TFlop/s。n同时印度史上首次杀入了印度史上首次杀入了TOP10行列行列，印度计算研究实验室的HP Cluster Platform 3000 BL460c以117.9 TFlop/s的性能拿到了第四位 2024/10/26 周六9供应商系统数量2024/10/26 周六10供应商计算能力2024/10/26 周六11国家分布系统数量2024/10/26 周六12国家分布计算能力2024/10/26 周六13体系结构系统数量2024/10/26 周六14体系结构计算能力2024/10/26 周六15应用领域系统数量2024/10/26 周六16应用领域计算能力2024/10/26 周六17操作系统系统数量2024/10/26 周六18操作系统计算能力2024/10/26 周六19处理器家族系统数量2024/10/26 周六20处理器家族计算能力2024/10/26 周六21系统数量2024/10/26 周六22计算能力2024/10/26 周六232007年中国高性能计算机性能年中国高性能计算机性能TOP100 2024/10/26 周六24并行化方法n域分解（Domain decomposition）n任务分解（Task decomposition）n流水线（Pipelining）2024/10/26 周六25域分解nFirst,decide how data elements should be divided among processorsnSecond,decide which tasks each processor should be doingnExample:Vector addition2024/10/26 周六26域分解Find the largest element of an array2024/10/26 周六27域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六28域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六29域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六30域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六31域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六32域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六33域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六34域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六35域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六36域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六37域分解Find the largest element of an arrayCPU 0CPU 1CPU 2CPU 32024/10/26 周六38任务（功能）分解nFirst,divide tasks among processorsnSecond,decide which data elements are going to be accessed(read and/or written)by which processorsnExample:Event-handler for GUI2024/10/26 周六39任务分解f()s()r()q()h()g()2024/10/26 周六40任务分解f()s()r()q()h()g()CPU 0CPU 2CPU 12024/10/26 周六41任务分解f()s()r()q()h()g()CPU 0CPU 2CPU 12024/10/26 周六42任务分解f()s()r()q()h()g()CPU 0CPU 2CPU 12024/10/26 周六43任务分解f()s()r()q()h()g()CPU 0CPU 2CPU 12024/10/26 周六44任务分解f()s()r()q()h()g()CPU 0CPU 2CPU 12024/10/26 周六45流水线nSpecial kind of task decompositionn“Assembly line”parallelismnExample:3D rendering in computer graphicsRasterizeClipProjectModelInputOutput2024/10/26 周六46Processing One Data Set(Step 1)RasterizeClipProjectModel2024/10/26 周六47Processing One Data Set(Step 2)RasterizeClipProjectModel2024/10/26 周六48Processing One Data Set(Step 3)RasterizeClipProjectModel2024/10/26 周六49Processing One Data Set(Step 4)RasterizeClipProjectModelThe pipeline processes 1 data set in 4 steps2024/10/26 周六50Processing Two Data Sets(Step 1)RasterizeClipProjectModel2024/10/26 周六51Processing Two Data Sets(Time 2)RasterizeClipProjectModel2024/10/26 周六52Processing Two Data Sets(Step 3)RasterizeClipProjectModel2024/10/26 周六53Processing Two Data SetsStep 4)RasterizeClipProjectModel2024/10/26 周六54Processing Two Data Sets(Step 5)RasterizeClipProjectModelThe pipeline processes 2 data sets in 5 steps2024/10/26 周六55Pipelining Five Data Sets(Step 1)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六56Pipelining Five Data Sets(Step 2)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六57Pipelining Five Data Sets(Step 3)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六58Pipelining Five Data Sets(Step 4)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六59Pipelining Five Data Sets(Step 5)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六60Pipelining Five Data Sets(Step 6)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六61Pipelining Five Data Sets(Step 7)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32024/10/26 周六62Pipelining Five Data Sets(Step 8)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3