并行计算,第一级,第二级,第三级,第一级,第二级,第三级,国家高性能计算中心（合肥）,*,数据划分与处理器指派,带状划分方法,:,又叫,行列划分,，就是将矩阵的整行或整列地分成若干组，各组指派给一个处理器四个处理器上,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,),表示对矩阵元素,ai,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=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,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),所示的,循环棋盘划分,（,Cyclic-checker Board Partitioning,）国家高性能计算中心（合肥）,循环程序并行化的一般方法,四个处理器上,44,矩阵棋盘划分,棋盘划分比带状划分可开发更高的并行度例如，对于一个的方阵，棋盘划分最多可使用,n2,个处理器；而带状划分可用的处理器数不能多于,n,个数据划分与处理器指派,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,3.,数据划分准则,:,并行粒度准则：,若多处理机系统有,p,台处理器，所有工作的处理器均经由一单独的全局信号灯同步，要是某一项给定的任务在其完成后要求同步时的最坏时间复杂度为,t(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,，则,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,endfor,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,均为,n,阶矩阵，有如形式的下串行程序段：,for i=1 to n do,for j=1 to n do,endfor,endfor,其中 、都是,i,，,j,的线性组合：,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,现在对 进行一种数据划分，也有一种数据划分与其对应，使它们被划分的数据块之间无数据相关关系，相应处理器之间不产生通信开销划分方法如下：,对 数组，设其划分后某一子阵列的元素下标满足：,c,为某一常数，对 数组，划分后相应子阵列的元素下标有如下关系：,将式 代入 、式得：,对于,A,有,对于,B,有,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,经变换可写为：,划分结果要使得相关数据被划分至同一处理器中，各处理器间无通信开销，则必须满足以下条件：,对于固定值,c,，由此式可求得 、及 、国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,例,3.5,.,设,A,为,n,阶矩阵，,B,为 矩阵，对如下二重循环计算：,for,i=2,to,n,do,for,j=2,to,n,do,endfor,endfor,存在如下数据相关关系：,即,满足上述关系的 有很多组，例如：取 即对常数,c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,来划分，对于下标空间所允许的每一个,c,值，满足以上二式的,A,，,B,元素构成了一个独立执行的部分,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,满足上述关系的 有很多组，例如：取 即对常数,c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,来划分，对于下标空间所允许的每一个,c,值，满足以上二式的,A,，,B,元素构成了一个独立执行的部分。
迭代空间数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,数据划分与处理器指派,5.,基于数据外部相关分析的划分,再如：取 即对常数,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.,循环交换,通过交换内外循环的先后次序对循环体结构进行调整，以实现划分后处理器内部数据的局部相关，从而减少通信开销，提高计算的并行性对如下循环：,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,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,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,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,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,拉伸前的数据相关图,国家高性能计算中心（合肥）,循环程序并行化的一般方法,循环重构,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,可并。
