并行计算-多媒体课件-并行程序设计-ch03并行程序设计简

《并行计算-多媒体课件-并行程序设计-ch03并行程序设计简》由会员分享，可在线阅读，更多相关《并行计算-多媒体课件-并行程序设计-ch03并行程序设计简（30页珍藏版）》请在装配图网上搜索。

1、并行计算,第一级,第二级,第三级,第一级,第二级,第三级,国家高性能计算中心（合肥）,*,数据划分与处理器指派,带状划分方法,:,又叫,行列划分,，就是将矩阵的整行或整列地分成若干组，各组指派给一个处理器。,四个处理器上,1616,矩阵带状划分,循环程序并行化的一般方法,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,例,3.1,设矩阵,A,有,n,行和,m,列，对其串行处理的程序段如下：,for,i=1,to,n,do,for,j=1,to,m,do,Process(ai,j,),endfor,endfor,其中，,Process(ai,j,),表示对矩阵元素,a

2、i,j,某种处理过程。设有,p,个处理器，令，。,行划分：,在采用行划分的情况下，例,3.1,串行程序段可转化为如下的并行程序段：,for,k=1,to,p,par-do,for,i1=1,to,r,do,for,j=1,to,m,do,Process(a(k-1)r+i1,j),endfor,endfor,endfor,其中“,par-do”,表示对循环体用,p,个处理器并行执行。,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,列划分：,在采用列划分的情况下，例,3.1,串行程序段可转化为如下的并行程序段：,for,k=1,to,p,par-do,for,j1=

3、1,to,s,do,for,i=1,to,n,do,Process(ai,(k-1)s+j1),endfor,endfor,endfor,行循环划分：,在采用行循环划分的情况下，例,3.1,串行程序段可转化为如下的并行程序段：,for,k=1,to,p,par-do,for,i1=1,to,r,do,for,j=1,to,m,do,Process(ai1-1p+k,j),endfor,endfor,endfor,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,列循环划分：,在采用列循环划分的情况下，例,3.1,串行程序段可转化为如下并行程序段：,for,k=1,to

4、,p,par-do,for,i=1,to,n,do,for,j1=1,to,s,do,Process(ai,(j1-1)p+k),endfor,endfor,endfor,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,2,、,块状划分方法,所谓块状划分又叫,棋盘划分,（,Checker Board Partitioning,），就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任一处理器均不包含整行或整列。,可分为图,3.11(a),所示的,块棋盘划分,（,Block-checker Board Partitioning,）和图,3.11(b),所示的

5、,循环棋盘划分,（,Cyclic-checker Board Partitioning,）。,国家高性能计算中心（合肥）,循环程序并行化的一般方法,四个处理器上,44,矩阵棋盘划分,棋盘划分比带状划分可开发更高的并行度。例如，对于一个的方阵，棋盘划分最多可使用,n2,个处理器；而带状划分可用的处理器数不能多于,n,个。,数据划分与处理器指派,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,3.,数据划分准则,:,并行粒度准则：,若多处理机系统有,p,台处理器，所有工作的处理器均经由一单独的全局信号灯同步，要是某一项给定的任务在其完成后要求同步时的最坏时间复杂度为,t

6、(m,),，那么最大可能加速比为 。,数据相关性准则,：,划分后的数据要指派给各处理器去执行一些操作，所以划分应该减少处理器间的通信，把那些彼此相关的数据尽可能分配到同一个处理器上，以使各处理器能独立地工作或只进行少量的通信。,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,4.,基于数据内部相关分析的划分,数据内部相关分析是指同一数据划分的相关分析。,例,3.2,设,A,为一个,n,阶方阵，有如下串行程序段：,for i=1 to n do,for j=1 to n do,ai,j,=ai-1,j,endfor,endfor,分析矩阵,A,的元素下标,i,和,j,

7、，则,i,和,j,的相关方向向量为，各列之间数据无任何相关关系。因此对矩阵,A,可按列划分。,串行程序段可转化为如下并行程序段：,for,k=1,to,P,Par-do,for,j1=1,to,m,do,for,i=1,to,n,do,ai,(k-1)m+j1=ai-1,(k-1)m+j1,endfor,endfor,endfor,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,4.,基于数据内部相关分析的划分,例,3.3,设,A,为矩阵，有如下串行程序段：,for i=1 to n do,for j=1 to n do,a3i,2j=a3i-2,2j-1,endf

8、or,endfor,其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和方块划分,.,在行划分的情况下令,例,3.3,的串行程序段可以转化为如下的并行程序段：,for,k=1,to,P,Par-do,for,i1=1,to,m,do,for,j=1,to,n,do,a3(k-1)m+3i1,2j=a 3(k-1)m+3i1-2,2j-1,endfor,endfor,endfor,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,所谓数据外部相关分析是指对不同数据划分的相关分析。,例,3.4,设,A,和,B,

9、均为,n,阶矩阵，有如形式的下串行程序段：,for i=1 to n do,for j=1 to n do,endfor,endfor,其中 、都是,i,，,j,的线性组合：,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,现在对 进行一种数据划分，也有一种数据划分与其对应，使它们被划分的数据块之间无数据相关关系，相应处理器之间不产生通信开销。划分方法如下：,对 数组，设其划分后某一子阵列的元素下标满足：,c,为某一常数，对 数组，划分后相应子阵列的元素下标有如下关系：,将式 代入 、式得：,对于,A,有,对于,B,有,国家高性能计

10、算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,经变换可写为：,划分结果要使得相关数据被划分至同一处理器中，各处理器间无通信开销，则必须满足以下条件：,对于固定值,c,，由此式可求得 、及 、。,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,例,3.5,.,设,A,为,n,阶矩阵，,B,为 矩阵，对如下二重循环计算：,for,i=2,to,n,do,for,j=2,to,n,do,endfor,endfor,存在如下数据相关关系：,即,满足上述关系的 有很多组，例如：取 即对常数,

11、c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,来划分，对于下标空间所允许的每一个,c,值，满足以上二式的,A,，,B,元素构成了一个独立执行的部分,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,满足上述关系的 有很多组，例如：取 即对常数,c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,来划分，对于下标空间所允许的每一个,c,值，满足以上二式的,A,，,B,元素构成了一个独立执行的部分。,迭代空间数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关

12、分析的划分,再如：取 即对常数,c,，,B,按,j,=,c,、,A,按,i,=,c,-1,来划分，对于下标空间所允许的每一个,c,值，满足以上二式的,A,，,B,元素构成了一个独立执行的部分。,按图中的虚线所示划分数据将保证对应的,A,，,B,元素被分配到相同的处理器中，计算时处理器之间不发生通信。由于斜线划分不利于并行计算，故采用第二种划分方法，进而可得出相应的并行程序：,for,i=2,to,n,par-do,for,j=2,to,n,do,endfor,endfor,迭代空间数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,1.,循环交换,通过交换内外循环的先后

13、次序对循环体结构进行调整，以实现划分后处理器内部数据的局部相关，从而减少通信开销，提高计算的并行性。对如下循环：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=ai-1,j,endfor,endfor,按数据相关性准则，的相关方向向量为 ，应该对矩阵,A,按列划分，按并行粒度准则，循环的最外层是,i,，应该对矩阵,A,按行划分，两条准则发生矛盾。现交换,I,j,循环的先后次序。通过重构得到如下并行程序：,for j=1 to n par-do,for i=1 to n do,ai,j,=ai-1,j,endfor,endfor,国家高性能计算中心（合肥）,循环程序

14、并行化的一般方法,循环重构,1.,循环交换,上例中，对,i,的循环具有相关性，对它应该串行执行，因此可利用循环交换，使无相关性的分量调换至最外层。在循环交换时，应该注意循环初值和终值的变化，对于如下循环：,for,i=1,to,n,do,for,j=i+1,to,n,do,Process(ai,j,),endfor,endfor,由于内层循环,j,的初值是外层循环,i,的函数，在循环交换后，这样的初值和终值也相应地变化为：,for,j=2,to,n,do,for,i=1,to,j-1,do,Process(ai,j,),endfor,endfor,国家高性能计算中心（合肥）,循环程序并行化的一

15、般方法,循环重构,2.,拉伸法,例,3.6.,在下列程序中：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=ai-1,j+ai,j-1,endfor,endfor,有两个相关向量：及 。,由于行列间皆存在相关关系，所以既不能进行行,列块划分、方块划分，也不能进行行列循环划分。,但如果我们对,j,循环用,i,循环进行拉伸，拉伸系数为,1,，得到如下程序：,for,i=1,to,n,do,for,j=i+1,to,i+n,do,ai,j-i,=ai-1,j-i+ai,j-i-1,endfor,endfor,拉伸前的数据相关图,国家高性能计算中心（合肥）,循环程序并行化

16、的一般方法,循环重构,2.,拉伸法,由图可见，对相同,j,值，沿,i,方向的计算无相关关系，因此交换,i,，,j,循环先后次序，,i,循环可并行执行，得到如下并行程序：,for,j=2,to,2n,do,for,i=max(1,j-n),to,min(n,j+1),par-do,ai,j-i,=ai-1,j-i+ai,j-i-1,endfor,endfor,由上述程序可见，由于各行之间的计算可以并行，因此对,A,矩阵进行行块划分,拉伸后的数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,2.,拉伸法,例,3.7.,设,A,为,n,阶矩阵，有串行程序如下：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=(ai,j+1+ai,j-1+ai+1,j+ai-1,j)/4,endfor,endfor,n=5,时的数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,2.,拉伸法,若按串行程序所定义的执行顺序，对,A,中的元素的可并行执行顺序如前面图所示。图中,(,i,j,),位置上的数字,T,表示元素,a,i,j,可并