数学高性能计算学习教案.pptx

《数学高性能计算学习教案.pptx》由会员分享，可在线阅读，更多相关《数学高性能计算学习教案.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学数学(shxu)高性能计算高性能计算第一页，共46页。啥叫粒度(l d)（非并行计算版）打个比方，100个学生要进行(jnxng)管理。细粒度：4个学生一个班25个班；粗粒度：50个学生一个班2个班。大学寝室八个人中午吃饭细粒度：每个人都要出寝室，去食堂打份饭回来。粗粒度：派个代表，或者(huzh)找个别的寝室的，把所有饭带回来。程序也是一样，事情定下来的功能就那么多细粒度细粒度：定义了100个类；粗粒度粗粒度：定义了2个类。第1页/共46页第二页，共46页。啥叫粒度(l d)（并行计算版）粒度（粒度（granularitygranularity）各个多处理机可独立各个多处理机可独立(dl

2、)(dl)并行执行的任务大小的度量。并行执行的任务大小的度量。粗粒度所含计算(j sun)任务有较大计算(j sun)量和较复杂计算(j sun)程序。任务级并行的粒度大于语句级的并行。细粒度所含计算任务有较小的计算量和较短的计算程序。向量机主要是对内层Do循环语句作向量化，所以向量化是一种小粒度（细粒度）并行。指令级并行等则是小粒度并行，亦称为细粒度。中粒度所含计算任务的大小和计算程序的长短在粗粒度和细粒度两种类型的算法之间第2页/共46页第三页，共46页。粒度(l d)细粒度的并行1）通信处理(chl)时只能完成很少量的可计算工作。2）低的计算通信率3）促进负载平衡意味着高通信开销，降低了

3、性能提升的可能性。如果粒度太小很可能任务间的通信和同步所须要的花费时间比用在计算上的还长。粗粒度并行1）在每次通信同步之间完成相当多的计算任务。2）高计算通信率意味着更加可能执行性能提升(tshng)。更难执行有效的负载平衡调度哪个更好？最高效的粒度是由算法和当前硬件平台决定的。通常情况下，通信和同步的开销很大程度上取决于执行速度，这样运用粗粒度较好。细粒度并行机制可以减少负载不平衡所带来的开销。第3页/共46页第四页，共46页。粒度(l d)（2）并行编程涉及不同的层次：指令层：非常细的粒度；数据层：细粒度；控制层：中粒度；任务(rn wu)层：大粒度。前两层大都由硬件和编译器负责处理，程序

4、员通常处理后两层的并行。第4页/共46页第五页，共46页。第七章 并行算法的一般设计(shj)过程 7.1 PCAM设计(shj)方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结第5页/共46页第六页，共46页。设计(shj)目标从给定问题的描述出发(chf)，通过一系列步骤，最终设计出一个能展示并发性可扩放性局部性和模块性的并行算法第6页/共46页第七页，共46页。设计(shj)原则PCAM设计方法学设计方法学首先尽量开拓算法的并发性和首先尽量开拓算法的并发性和满足算法的可扩放性满足算法的可扩放性(与算法相与算法相关的特性关的特性)；然后着重优化算法的通信成本然后

5、着重优化算法的通信成本和全局执行时间和全局执行时间(与机器相关的与机器相关的特性特性)；同时通过必要的整个过程的反同时通过必要的整个过程的反复回溯，以期望复回溯，以期望(qwng)达到达到一个满意的设计选择；一个满意的设计选择；第7页/共46页第八页，共46页。PCAM设计(shj)方法学设计设计(shj)(shj)并行算法并行算法(PCAM)(PCAM)的四个阶段的四个阶段划分划分(Partitioning)(Partitioning)通信通信(Communication)(Communication)组合组合(Agglomeration)(Agglomeration)映射映射(Mappin

6、g)(Mapping)设计的前期(第1,2步)：考虑与机器特性无关的特性：并行性和可扩放性，寻求具有这些(zhxi)特性的算法；设计的后期(第3,4步)：考虑与机器特性相关的特性：局部性等与性能有关的问题；第8页/共46页第九页，共46页。PCAM设计(shj)过程划分(hu fn)通信(tng xn)组合映射划分：分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。第9页/共46页第十页，共46页。第七章 并行算法的一般(ybn)设计过程 7.1 PCAM设计方法学 7.2 划分

7、 7.3 通信 7.4 组合 7.5 映射(yngsh)7.6 小结 第10页/共46页第十一页，共46页。划分方法(fngf)描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；先集中(jzhng)数据的分解（域分解），然后是计算功能的分解（功能分解），两者互为补充使数据集和计算集互补相交，以避免数据和计算的复制；第11页/共46页第十二页，共46页。划分方法(fngf)描述划分阶段忽略处理器数目(shm)和目标机器的体系结构；能分为两类划分：域分解(domain decomposition)功能分解(functional decomposit

8、ion)第12页/共46页第十三页，共46页。域分解(fnji)划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应(xingyng)操作；如果一个任务需要别的任务中的数据，则会产生任务间的通信；第13页/共46页第十四页，共46页。域分解(fnji)示例：三维网格的域分解(fnji)，各格点上计算都是重复的。下图是三种分解(fnji)方法：第14页/共46页第十五页，共46页。域分解(fnji)不规则区域(qy)的分解示例：第15页/共46页第十六页，共46页。功能(gngnng)分解 划分的对象是计算，将计算划分为不同的任务

9、，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功(chnggng)的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。第16页/共46页第十七页，共46页。示例1：搜索(su su)树示例2：气候模型功能(gngnng)分解 第17页/共46页第十八页，共46页。划分(hu fn)判据 划分是否具有灵活性？划分是否避免了冗余(rn y)计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？第18页/共46页第十九页，共46页。划分(hu fn)的标准划分的任务数，

10、是否至少高于目标机上处理器数的一个量级。划分的任务数，是否至少高于目标机上处理器数的一个量级。（灵活性）（灵活性）若否，则后继的设计步骤缺少灵活性若否，则后继的设计步骤缺少灵活性是否避免冗于的计算和存储要求。（可扩放性）是否避免冗于的计算和存储要求。（可扩放性）若否，则产生的算法对大型问题可能是不可扩放的若否，则产生的算法对大型问题可能是不可扩放的划分的任务尺寸是否大致相当。（均衡）划分的任务尺寸是否大致相当。（均衡）若否，分配处理器时很难做到工作量均衡若否，分配处理器时很难做到工作量均衡任务数是否与问题尺寸成比例。任务数是否与问题尺寸成比例。理想情况下，问题尺寸的增加应引起理想情况下，问题尺

11、寸的增加应引起(ynq)(ynq)任务数的增加而不任务数的增加而不是任务尺寸的增加是任务尺寸的增加是否采用了几种不同的划分法，是否采用了几种不同的划分法，多考虑几种选择可提高灵活性，同时既考虑域分解，又要考虑功多考虑几种选择可提高灵活性，同时既考虑域分解，又要考虑功能分解。能分解。第19页/共46页第二十页，共46页。第七章 并行算法的一般(ybn)设计过程 7.1 PCAM设计方法学 7.2 划分(hu fn)7.3 通信 7.4 组合 7.5 映射 7.6 小结 第20页/共46页第二十一页，共46页。通信(tng xn)方法描述通信是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能

12、完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解(fnji)确定了诸任务之间的数据流；诸任务是并发执行的，通信则限制了这种并发性；第21页/共46页第二十二页，共46页。四种(s zhn)通信模式局部/全局(qunj)通信结构化/非结构化通信静态/动态通信同步/异步通信第22页/共46页第二十三页，共46页。局部(jb)通信通信限制在一个邻域(ln y)内，只与较少的几个近邻的通信第23页/共46页第二十四页，共46页。全局(qunj)通信通信非局部的，与很多任务(rn wu)通信例如：All to AllMaster-Worker53721第24页/共46页第二十五页，共46

13、页。结构化通信(tng xn)每个任务的通信模式是相同的；下面(xi mian)是否存在一个相同通信模式？第25页/共46页第二十六页，共46页。非结构化通信(tng xn)没有一个统一的通信模式(msh)例如：无结构化网格第26页/共46页第二十七页，共46页。静态通信(tng xn)vs.动态通信(tng xn)静态通信伙伴的身份(shn fen)不随时间改变动态通信伙伴的身份(shn fen)可能由运行时所计算的数据决定且是可变的第27页/共46页第二十八页，共46页。同步(tngb)通信vs.异步通信同步双方知道何时进行通信(tng xn)，发送方显示的发给接收方异步不确定，接收的方明

14、确地从发送者请求数据第28页/共46页第二十九页，共46页。通信(tng xn)判据 所有任务是否执行大致相当的通信(tng xn)?是否尽可能的局部通信(tng xn)？通信(tng xn)操作是否能并行执行?同步任务的计算能否并行执行？第29页/共46页第三十页，共46页。通信(tng xn)标准所有任务是否执行大致同样多的通信。所有任务是否执行大致同样多的通信。(可扩放可扩放性性)若否，则可扩放性可能不好若否，则可扩放性可能不好每个任务是否只与少许近邻通信每个任务是否只与少许近邻通信若否，则可能导致全局通信；应设法将全局通若否，则可能导致全局通信；应设法将全局通信结构化为局部通信结构信结

15、构化为局部通信结构诸通信操作是否能并行执行诸通信操作是否能并行执行若否，则可能是低效的和不可扩放的若否，则可能是低效的和不可扩放的不同不同(b tn)(b tn)任务的计算能否并行执行任务的计算能否并行执行若否，则可能是低效的和不可扩放的若否，则可能是低效的和不可扩放的可重新安排通信可重新安排通信/计算次序计算次序第30页/共46页第三十一页，共46页。第七章 并行算法的一般设计(shj)过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合(zh)7.5 映射 7.6 小结第31页/共46页第三十二页，共46页。方法(fngf)描述 组合(zh)是由抽象到具体的过程，是将

16、组合(zh)的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通信成本；保持映射和扩展的灵活性，降低软件工程成本；第32页/共46页第三十三页，共46页。方法(fngf)描述（2）增加粒度：增加粒度：在划分阶段，致力于尽可能多的任务以增大并行在划分阶段，致力于尽可能多的任务以增大并行执行的机会。但定义大量的细粒度任务不一定产执行的机会。但定义大量的细粒度任务不一定产生一个有效的算法，因为这有可能增加通信的代生一个有效的算法，因为这有可能增加通信的代价和任务创建的代价价和任务创建的代价表面表面-容积

17、效应：通信量比例于子域的表面积，而容积效应：通信量比例于子域的表面积，而计算比例于容积；计算比例于容积；通信通信/计算之比随任务的尺寸计算之比随任务的尺寸(ch cun)(ch cun)的增加而减的增加而减少少 增加粒度增加粒度重复计算重复计算(Replication Computation),(Replication Computation),也叫冗余计也叫冗余计算，有时可用冗余计算来减少通信。算，有时可用冗余计算来减少通信。同时也要保持灵活性和减少软件成本、降低软件同时也要保持灵活性和减少软件成本、降低软件工程代价工程代价第33页/共46页第三十四页，共46页。表面(biomin)-容积效

18、应通信量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少(jinsho)通讯量；第34页/共46页第三十五页，共46页。重复(chngf)计算重复计算减少通讯(tngxn)量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；第35页/共46页第三十六页，共46页。示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持(boch)全和。二叉树上求和，共需2logN步重复(chngf)计算第36页/共46页第三十七页，共46页。重复(chngf)计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。蝶式结构求和，使用了重复(

19、chngf)计算，共需logN步第37页/共46页第三十八页，共46页。组合(zh)判据 增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题(wnt)尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？第38页/共46页第三十九页，共46页。组合(zh)的标准组合造成的重复计算，是否平衡了其收益(shuy)？造成重复数据，是否已证实不会因限制问题尺寸和处理机数目而影响可扩放性？组合产生的任务是否具有类似的计算、通信代价？任务数目是否仍与问题尺寸成比例？第39页/共46页第四十页，共46页。第七章 并行算法的一般设计(shj)

20、过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合(zh)7.5 映射 7.6 小结第40页/共46页第四十一页，共46页。方法(fngf)描述 每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少(jinsho)算法的执行时间并发的任务 不同的处理器任务之间存在高通讯的 同一处理器映射实际是一种权衡，属于NP完全问题；第41页/共46页第四十二页，共46页。负载平衡算法(sun f)静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；基于域分解的：递归对剖局部算法概率方法循环(xnhun)映射第4

21、2页/共46页第四十三页，共46页。任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式(msh)：经理/雇员模式(msh)非集中模式(msh)任务调度算法(sun f)第43页/共46页第四十四页，共46页。映射(yngsh)判据 采用集中式负载平衡方案(fng n)，是否存在通信瓶颈？采用动态负载平衡方案(fng n)，调度策略的成本如何？第44页/共46页第四十五页，共46页。小 结 划分域分解和功能分解通信任务间的数据交换组合任务的合并使得算法(sun f)更有效映射将任务分配到处理器，并保持负载平衡第45页/共46页第四十六页，共46页。