[数学]高性能计算教案-第七讲-last课件

1、第 七 讲第七章啥叫粒度（非并行计算版）打个比方，100个学生要进行管理。细粒度：4个学生一个班25个班；粗粒度：50个学生一个班2个班。大学寝室八个人中午吃饭细粒度：每个人都要出寝室，去食堂打份饭回来。 粗粒度：派个代表，或者找个别的寝室的，把所有饭带回来。程序也是一样，事情定下来的功能就那么多细粒度：定义了100个类；粗粒度：定义了2个类。啥叫粒度（并行计算版）粒度（granularity）各个多处理机可独立并行执行的任务大小的度量。粗粒度所含计算任务有较大计算量和较复杂计算程序。任务级并行的粒度大于语句级的并行。细粒度所含计算任务有较小的计算量和较短的计算程序。向量机主要是对内层Do循环

2、语句作向量化，所以向量化是一种小粒度（细粒度）并行。指令级并行等则是小粒度并行，亦称为细粒度。中粒度所含计算任务的大小和计算程序的长短在粗粒度和细粒度两种类型的算法之间粒度细粒度的并行1）通信处理时只能完成很少量的可计算工作。2）低的计算通信率3）促进负载平衡意味着高通信开销，降低了性能提升的可能性。如果粒度太小很可能任务间的通信和同步所须要的花费时间比用在计算上的还长。粗粒度并行1）在每次通信同步之间完成相当多的计算任务。2）高计算通信率意味着更加可能执行性能提升。更难执行有效的负载平衡调度哪个更好？最高效的粒度是由算法和当前硬件平台决定的。通常情况下，通信和同步的开销很大程度上取决于执行速

3、度，这样运用粗粒度较好。 细粒度并行机制可以减少负载不平衡所带来的开销。粒度（2）并行编程涉及不同的层次：指令层：非常细的粒度；数据层：细粒度；控制层：中粒度；任务层：大粒度。前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行。第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结设计目标从给定问题的描述出发，通过一系列步骤，最终设计出一个能展示并发性可扩放性局部性和模块性的并行算法设计原则PCAM设计方法学首先尽量开拓算法的并发性和满足算法的可扩放性(与算法相关的特性)；然后着重优化算法的通信成本和全局执行时

4、间(与机器相关的特性)；同时通过必要的整个过程的反复回溯，以期望达到一个满意的设计选择； PCAM设计方法学设计并行算法(PCAM)的四个阶段划分(Partitioning)通信(Communication)组合(Agglomeration)映射(Mapping)设计的前期(第1,2步)：考虑与机器特性无关的特性：并行性和可扩放性，寻求具有这些特性的算法；设计的后期(第3,4步) ：考虑与机器特性相关的特性：局部性等与性能有关的问题； PCAM设计过程划分通信组合映射划分：分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射

5、：将每个任务分配到处理器上，提高算法的性能。第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结 划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；先集中数据的分解（域分解），然后是计算功能的分解（功能分解），两者互为补充使数据集和计算集互补相交，以避免数据和计算的复制；划分方法描述划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(domain decomposition)功能分解(functional decomposition)域分解 划分

6、的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通信；域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：域分解 不规则区域的分解示例：功能分解 划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。示例1：搜索树示例2：气候模型功能分解 划分判据 划分是否具有灵活性？划分是否避免了冗

7、余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？划分的标准划分的任务数，是否至少高于目标机上处理器数的一个量级。（灵活性）若否，则后继的设计步骤缺少灵活性是否避免冗于的计算和存储要求。（可扩放性）若否，则产生的算法对大型问题可能是不可扩放的划分的任务尺寸是否大致相当。（均衡）若否，分配处理器时很难做到工作量均衡任务数是否与问题尺寸成比例。理想情况下，问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加是否采用了几种不同的划分法，多考虑几种选择可提高灵活性，同时既考虑域分解，又要考虑功能分解。第七章 并行算法的一般设计过程 7.1 PC

8、AM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结 通信方法描述通信是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通信则限制了这种并发性； 四种通信模式局部/全局通信结构化/非结构化通信静态/动态通信同步/异步通信局部通信通信限制在一个邻域内，只与较少的几个近邻的通信全局通信通信非局部的，与很多任务通信例如：All to AllMaster-Worker53721结构化通信每个任务的通信模式是相同的；下面是否存在一个相同通信模式？非结构化通信

9、没有一个统一的通信模式例如：无结构化网格静态通信vs.动态通信静态通信伙伴的身份不随时间改变动态通信伙伴的身份可能由运行时所计算的数据决定且是可变的同步通信vs.异步通信同步双方知道何时进行通信，发送方显示的发给接收方异步不确定，接收的方明确地从发送者请求数据通信判据 所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行?同步任务的计算能否并行执行？通信标准所有任务是否执行大致同样多的通信。(可扩放性)若否，则可扩放性可能不好每个任务是否只与少许近邻通信若否，则可能导致全局通信；应设法将全局通信结构化为局部通信结构诸通信操作是否能并行执行若否，则可能是低效的和不可扩放的

10、不同任务的计算能否并行执行若否，则可能是低效的和不可扩放的可重新安排通信/计算次序第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结方法描述 组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通信成本；保持映射和扩展的灵活性，降低软件工程成本；方法描述 （2）增加粒度：在划分阶段，致力于尽可能多的任务以增大并行执行的机会。但定义大量的细粒度任务不一定产生一个有效的算法，因为这有可能增加通

11、信的代价和任务创建的代价表面-容积效应：通信量比例于子域的表面积，而计算比例于容积；通信/计算之比随任务的尺寸的增加而减少增加粒度重复计算(Replication Computation),也叫冗余计算，有时可用冗余计算来减少通信。同时也要保持灵活性和减少软件成本、降低软件工程代价表面-容积效应通信量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通讯量；重复计算重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 二叉树上求和，共需2logN步重复计算重复计算

12、示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 蝶式结构求和，使用了重复计算，共需logN步组合判据 增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？组合的标准组合造成的重复计算，是否平衡了其收益？造成重复数据，是否已证实不会因限制问题尺寸和处理机数目而影响可扩放性？组合产生的任务是否具有类似的计算、通信代价？任务数目是否仍与问题尺寸成比例？第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结方法描述 每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务 不同的处理器任务之间存在高通讯的 同一处理器映射实际是一种权衡，属于NP完全问题；负载平衡算法 静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；