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

《并行计算-多媒体课件-并行程序设计-ch03并行程序设计简.ppt》由会员分享，可在线阅读，更多相关《并行计算-多媒体课件-并行程序设计-ch03并行程序设计简.ppt（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派带状划分方法:又叫行列划分行列划分，就是将矩阵的整行或整列地分成若干组，各组指派给一个处理器。四个处理器上四个处理器上1616矩阵带状划分矩阵带状划分循环程序并行化的一般方法循环程序并行化的一般方法 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 例例例例3.13.1 设矩阵设矩阵A A有有n n行和行和mm列，对其串行处理的程序段如下：列，对其串行处理的程序段如下：for for i=1 i=1 toto

2、 n n dodo for for j=1 j=1 to to m m dodo Process(ai,jProcess(ai,j)endforendfor endforendfor 其中，其中，Process(ai,jProcess(ai,j)表示对矩阵元素表示对矩阵元素ai,jai,j 某种处理过程。设有某种处理过程。设有p p个处理器，令，。个处理器，令，。行划分：行划分：行划分：行划分：在采用行划分的情况下，例在采用行划分的情况下，例3.13.1串行程序段可转化为如下的并行程序段：串行程序段可转化为如下的并行程序段：for for k=1 k=1 toto p p par-dopar-

3、do for for i1=1 i1=1 to to r r dodo for for j=1 j=1 toto m m do do Process(a(k-1)r+i1,j)Process(a(k-1)r+i1,j)endforendfor endforendfor endforendfor 其中其中“par-do”par-do”表示对循环体用表示对循环体用p p个处理器并行执行。个处理器并行执行。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 列划分：列划分：列划分：列划分：在采用

4、列划分的情况下，例在采用列划分的情况下，例3.13.1串行程序段可转化为如下的并行程序段：串行程序段可转化为如下的并行程序段：for for k=1k=1 to to p p par-dopar-do for for j1=1 j1=1 to to s s dodo for for i=1 i=1 toto n n dodo Process(aiProcess(ai,(k-1)s+,(k-1)s+j1)j1)endforendfor endforendfor endforendfor 行循环划分：行循环划分：行循环划分：行循环划分：在采用行循环划分的情况下，例在采用行循环划分的情况下，例3.1

5、3.1串行程序段可转化为如下串行程序段可转化为如下的并行程序段：的并行程序段：for for k=1k=1 to to p p par-dopar-do for for i1=1 i1=1 toto r r do do for for j=1 j=1 to to m m dodo Process(ai1-1p+k,j)Process(ai1-1p+k,j)endforendfor endforendfor endforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派列循环划分：列循环划分：列循环划分：列循环划分：在

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

7、2 2、块状划分方法块状划分方法 所谓块状划分又叫所谓块状划分又叫棋盘划分棋盘划分棋盘划分棋盘划分（Checker Board Checker Board PartitioningPartitioning），就是将矩阵划分成若干个子矩阵，每），就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任一处理器均不包含个子矩阵指派给一个处理器，此时任一处理器均不包含整行或整列。整行或整列。可分为图可分为图 3.11(a)3.11(a)所示的所示的块棋盘划分块棋盘划分块棋盘划分块棋盘划分（Block-Block-checker Board Partitioningchecker Board

8、Partitioning）和图）和图 3.11(b)3.11(b)所示的所示的循环循环循环循环棋盘划分棋盘划分棋盘划分棋盘划分（Cyclic-checker Board PartitioningCyclic-checker Board Partitioning）。）。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 四个处理器上四个处理器上44矩阵棋盘划分矩阵棋盘划分棋盘划分比带状划分可开发更高的并行度。棋盘划分比带状划分可开发更高的并行度。例如，对于一个的方阵，棋盘划分最多可使例如，对于一个的方阵，棋盘划分最多可使用用n2个处理器；而带状划分可用的处理器数个处理器；

9、而带状划分可用的处理器数不能多于不能多于n个。个。数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派 3.3.数据划分准则数据划分准则:并行粒度准则：并行粒度准则：并行粒度准则：并行粒度准则：若多处理机系统有若多处理机系统有p p台处理器，所有工作的处理器均经由一单台处理器，所有工作的处理器均经由一单独的全局信号灯同步，要是某一项给定的任务在其完成后要求同独的全局信号灯同步，要是某一项给定的任务在其完成后要求同步时的最坏时间复杂度为步时的最坏时间复杂

10、度为t(mt(m)，那么最大可能加速比为，那么最大可能加速比为 。数据相关性准则数据相关性准则数据相关性准则数据相关性准则：划分后的数据要指派给各处理器去执行一些操作，所以划分划分后的数据要指派给各处理器去执行一些操作，所以划分应该减少处理器间的通信，把那些彼此相关的数据尽可能分配到应该减少处理器间的通信，把那些彼此相关的数据尽可能分配到同一个处理器上，以使各处理器能独立地工作或只进行少量的通同一个处理器上，以使各处理器能独立地工作或只进行少量的通信。信。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据

11、划分与处理器指派 4.4.基于数据内部相关分析的划分基于数据内部相关分析的划分基于数据内部相关分析的划分基于数据内部相关分析的划分 数据内部相关分析是指同一数据划分的相关分析。数据内部相关分析是指同一数据划分的相关分析。数据内部相关分析是指同一数据划分的相关分析。数据内部相关分析是指同一数据划分的相关分析。例例例例3.2 3.2 设设设设A A为一个为一个为一个为一个n n阶方阵，有如下串行程序段：阶方阵，有如下串行程序段：阶方阵，有如下串行程序段：阶方阵，有如下串行程序段：for i=1 to n dofor i=1 to n do for j=1 to n dofor j=1 to n d

12、o ai,jai,j=ai-1,j=ai-1,j endforendfor endforendfor 分析矩阵分析矩阵A A的元素下标的元素下标i i和和j j，则，则i i和和j j的相关方向向量为，各列之间数据无任的相关方向向量为，各列之间数据无任何相关关系。因此对矩阵何相关关系。因此对矩阵A A可按列划分。可按列划分。串行程序段可转化为如下并行程序段：串行程序段可转化为如下并行程序段：forfor k=1 k=1 to to P P Par-doPar-dofor for j1=1j1=1 to to m m dodoforfor i=1 i=1 to to n n dodoai,(k-

13、1)m+j1=ai-1,(k-1)m+j1ai,(k-1)m+j1=ai-1,(k-1)m+j1endforendforendforendforendforendfor 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 4.4.基于数据内部相关分析的划分基于数据内部相关分析的划分基于数据内部相关分析的划分基于数据内部相关分析的划分 例例例例3.3 3.3 设设设设A A为矩阵，有如下串行程序段：为矩阵，有如下串行程序段：为矩阵，有如下串行程序段：为矩阵，有如下串行程序段：for i=1

14、to n dofor i=1 to n dofor j=1 to n dofor j=1 to n doa3i,2j=a3i-2,2j-1a3i,2j=a3i-2,2j-1endforendforendforendfor 其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和方块划分划分和方块划分.在行划分的情况下令在行划分的情况下令 ,例例3.33.3的串行程序段可以转化为如下的并行程序段：的串行程序段可以转化为如下的并行程序段：forfor k=1 k=1 to to P P Par-doP

15、ar-dofor for i1=1i1=1 to to m m dodoforfor j=1 j=1 to to n n dodoa3(k-1)m+3i1,2j=a 3(k-1)m+3i1-2,2j-1a3(k-1)m+3i1,2j=a 3(k-1)m+3i1-2,2j-1endforendforendforendforendforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 5.5.基于数据外部相关分析的划分基于数据外部相关分析的划分所谓数据外部相关分析是指对不同数据划

16、分的相关分析。所谓数据外部相关分析是指对不同数据划分的相关分析。例例例例3.4 3.4 设设A A和和B B均为均为n n阶矩阵，有如形式的下串行程序段：阶矩阵，有如形式的下串行程序段：for i=1 to n dofor i=1 to n dofor j=1 to n dofor j=1 to n doendforendforendforendfor其中其中 、都是都是i i，j j的线性组合：的线性组合：国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 5.5.基于数据外部相关分析的

17、划分基于数据外部相关分析的划分 现在对现在对 进行一种数据划分，进行一种数据划分，也有一种数据划分与其对应，使它也有一种数据划分与其对应，使它们被划分的数据块之间无数据相关关系，相应处理器之间不产生们被划分的数据块之间无数据相关关系，相应处理器之间不产生通信开销。划分方法如下：通信开销。划分方法如下：对对 数组，设其划分后某一子阵列的元素下标满足：数组，设其划分后某一子阵列的元素下标满足：c c为某一常数，对为某一常数，对 数组，划分后相应子阵列的元素下标有如下关系：数组，划分后相应子阵列的元素下标有如下关系：将式将式 代入代入 、式得：式得：对于对于A A有有 对于对于 B B有有国家高性能

18、计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派数据划分与处理器指派 5.5.基于数据外部相关分析的划分基于数据外部相关分析的划分 经变换可写为：经变换可写为：划分结果要使得相关数据被划分至同一处理器中，各处理划分结果要使得相关数据被划分至同一处理器中，各处理器间无通信开销，则必须满足以下条件：器间无通信开销，则必须满足以下条件：对于固定值对于固定值c c，由此式可求得，由此式可求得 、及及 、。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 数据划分与处理器指派数据划分与处理器指派数据划分

19、与处理器指派数据划分与处理器指派 5.5.基于数据外部相关分析的划分基于数据外部相关分析的划分例例例例3.53.5.设设A A为为n n阶矩阵，阶矩阵，B B为为 矩阵，对如下二重循环计算：矩阵，对如下二重循环计算：for for i=2 i=2 toto n n dodo for for j=2 j=2 to to n n do do endforendfor endforendfor存在如下数据相关关系：存在如下数据相关关系：即即 满足上述关系的满足上述关系的 有很多组，例如：取有很多组，例如：取 即对常数即对常数c c，B B按按i i-j j=c c，A A按按j j=c c 来划分，

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

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

22、 A，B B元素构成了一个独立执行的部分。元素构成了一个独立执行的部分。按图中的虚线所示划分数据将保证对应的按图中的虚线所示划分数据将保证对应的A A，B B元素被分配到相同的处理器中，计算时处理器元素被分配到相同的处理器中，计算时处理器之间不发生通信。由于斜线划分不利于并行计算，故采用第二种划分方法，进而可得出相应的之间不发生通信。由于斜线划分不利于并行计算，故采用第二种划分方法，进而可得出相应的并行程序：并行程序：for for i=2 i=2 toto n n par-dopar-do for for j=2 j=2 toto n n dodo endforendforendforend

23、for 迭代空间数据相关图迭代空间数据相关图 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 1.1.循环交换循环交换 通过交换内外循环的先后次序对循环体结构进行调整，以实现划分后处理通过交换内外循环的先后次序对循环体结构进行调整，以实现划分后处理器内部数据的局部相关，从而减少通信开销，提高计算的并行性。对如下器内部数据的局部相关，从而减少通信开销，提高计算的并行性。对如下循环：循环：for for i=1 i=1 toto n n dodo for for j=1j=1 to to n n dodo ai,jai,j=ai-1,j =ai-1,j

24、 endforendfor endforendfor 按数据相关性准则，按数据相关性准则，的相关方向向量为的相关方向向量为 ，应该对矩阵，应该对矩阵A A按列划分，按列划分，按并行粒度准则，循环的最外层是按并行粒度准则，循环的最外层是i i，应该对矩阵，应该对矩阵A A按行划分，两条准则发按行划分，两条准则发生矛盾。现交换生矛盾。现交换I,jI,j循环的先后次序。通过重构得到如下并行程序：循环的先后次序。通过重构得到如下并行程序：for j=1 to n par-do for j=1 to n par-do for i=1 to n do for i=1 to n do ai,jai,j=ai

25、-1,j =ai-1,j endforendforendforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 1.1.循环交换循环交换 上例中，对上例中，对i i的循环具有相关性，对它应该串行执行，因此可利用循环交换，的循环具有相关性，对它应该串行执行，因此可利用循环交换，使无相关性的分量调换至最外层。在循环交换时，应该注意循环初值和终使无相关性的分量调换至最外层。在循环交换时，应该注意循环初值和终值的变化，对于如下循环：值的变化，对于如下循环：for for i=1 i=1 toto n n dodo for for j=i+1 j=

26、i+1 toto n n dodo Process(ai,jProcess(ai,j)endforendforendforendfor 由于内层循环由于内层循环j j的初值是外层循环的初值是外层循环i i的函数，在循环交换后，这样的初值和终的函数，在循环交换后，这样的初值和终值也相应地变化为：值也相应地变化为：for for j=2 j=2 to to n n dodo for for i=1 i=1 to to j-1 j-1 dodo Process(ai,jProcess(ai,j)endforendfor endforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法循环程

27、序并行化的一般方法 循环重构循环重构 2.2.拉伸法拉伸法 例例例例3.6.3.6.在下列程序中：在下列程序中：for for i=1 i=1 toto n n dodo for for j=1 j=1 toto n n dodo ai,jai,j=ai-1,j+ai,j-1=ai-1,j+ai,j-1 endforendfor endforendfor 有两个相关向量：有两个相关向量：有两个相关向量：有两个相关向量：及及及及 。由于行列间皆存在相关关系，所以既不能进行行由于行列间皆存在相关关系，所以既不能进行行由于行列间皆存在相关关系，所以既不能进行行由于行列间皆存在相关关系，所以既不能进行

28、行列块划分、方块划分，也不能进行行列循环划分。列块划分、方块划分，也不能进行行列循环划分。列块划分、方块划分，也不能进行行列循环划分。列块划分、方块划分，也不能进行行列循环划分。但如果我们对但如果我们对但如果我们对但如果我们对j j循环用循环用循环用循环用i i循环进行拉伸，拉伸系数为循环进行拉伸，拉伸系数为循环进行拉伸，拉伸系数为循环进行拉伸，拉伸系数为1 1，得到如下程序：，得到如下程序：，得到如下程序：，得到如下程序：forfor i=1 i=1 toto n n dodo for for j=i+1 j=i+1 to to i+ni+n dodo ai,j-iai,j-i=ai-1,j

29、-i+ai,j-i-1=ai-1,j-i+ai,j-i-1 endforendforendforendfor拉伸前的数据相关图拉伸前的数据相关图 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 2.2.拉伸法拉伸法由图可见，对相同由图可见，对相同j j值，沿值，沿i i方向的计算无相关关系，因此交换方向的计算无相关关系，因此交换i i，j j循环先后次序，循环先后次序，i i循环循环可并行执行，得到如下并行程序：可并行执行，得到如下并行程序：for for j=2 j=2 to to 2n2n do do for for i=max(1,j-n)i

30、=max(1,j-n)to to min(n,j+1)min(n,j+1)par-dopar-do ai,j-iai,j-i=ai-1,j-i+ai,j-i-1=ai-1,j-i+ai,j-i-1 endforendfor endforendfor由上述程序可见，由于各行之间的计算可以并行，因此对由上述程序可见，由于各行之间的计算可以并行，因此对A A矩阵进行行块划分矩阵进行行块划分 拉伸后的数据相关图拉伸后的数据相关图 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 2.2.拉伸法拉伸法例例例例3.7.3.7.设设A A为为n n阶矩阵，有串行程

31、序如下：阶矩阵，有串行程序如下：for for i=1 i=1 to to n n dodo for for j=1 j=1 toto n n dodo ai,jai,j=(ai,j+1+ai,j-1+ai+1,j+ai-1,j)/4=(ai,j+1+ai,j-1+ai+1,j+ai-1,j)/4 endforendfor endforendforn=5n=5时的数据相关图时的数据相关图 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 2.2.拉伸法拉伸法 若按串行程序所定义的执行顺序，对若按串行程序所定义的执行顺序，对A A中的元素的可并行执行顺

32、序如前面图所示。中的元素的可并行执行顺序如前面图所示。图中图中(i,ji,j)位置上的数字位置上的数字T T表示元素表示元素aai,ji,j 可并行计算的时间。例如可并行计算的时间。例如a1,1a1,1可在可在T T=1=1时计时计算，算，a2,1a2,1及及a1,2a1,2可在可在T T=2=2时并行计算等。即：沿对角线方向上的计算可以并行。时并行计算等。即：沿对角线方向上的计算可以并行。为了挖掘此并行性，我们采用拉伸法对串行程序进行改造。对循环为了挖掘此并行性，我们采用拉伸法对串行程序进行改造。对循环j j利用循环利用循环i i进行进行拉伸，拉伸系数为拉伸，拉伸系数为1 1，得到如下程序：

33、，得到如下程序：for for i=1i=1 to to n n dodo for for j=1+i j=1+i toto n+in+i dodo ai,j-iai,j-i=(ai,j+1-i+ai,j-1-i+ai+1,j-i+ai-1,j-i)/4=(ai,j+1-i+ai,j-1-i+ai+1,j-i+ai-1,j-i)/4 endforendfor endforendfor 通过交换内外循环的先后次序，得到如下并行程序：通过交换内外循环的先后次序，得到如下并行程序：for for j=2 j=2 to to 2n 2n dodo for for i=max(1,j-n)i=max(1

34、,j-n)to to min(n,j-1)min(n,j-1)par-dopar-do ai,j-iai,j-i=(ai,j+1-i+ai,j-1-i+ai+1,j-i+ai-1,j-i)/4=(ai,j+1-i+ai,j-1-i+ai+1,j-i+ai-1,j-i)/4 endforendfor endforendfor 调整后的内层循环将被并行执行，即在同一列的各行之间并行。因此对调整后的内层循环将被并行执行，即在同一列的各行之间并行。因此对A A进行行块进行行块划分。划分。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法循环重构循环重构 3.3.分裂法分裂法 分

35、裂法是一种通过将循环迭代空间细分成相同形分裂法是一种通过将循环迭代空间细分成相同形状和大小的数据块以达到局部化相关关系的变换方法。状和大小的数据块以达到局部化相关关系的变换方法。变换之后，一个子数据块内部的全部迭代被同一个处理变换之后，一个子数据块内部的全部迭代被同一个处理器执行，只有在子数据块之间计算才需要通信。器执行，只有在子数据块之间计算才需要通信。分裂法的变换分两步进行：第一步，将原算法中分裂法的变换分两步进行：第一步，将原算法中的每重循环按块连续划分，细化为双重嵌套循环，外层的每重循环按块连续划分，细化为双重嵌套循环，外层对子块进行循环，内层对块内数据进行循环；第二步，对子块进行循环

36、，内层对块内数据进行循环；第二步，将所有对子块的循环交换至经变换后循环体的最外层以将所有对子块的循环交换至经变换后循环体的最外层以并行执行。并行执行。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 3.3.分裂法分裂法例例例例3.8.3.8.设设A A，B B，C C为为n n阶矩阵，有串行程序如下：阶矩阵，有串行程序如下：for for i=1 i=1 toto n n dodo for for j=1 j=1 to to n n dodo Ai,jAi,j=Ai,j+Bi,jAi,j+Bi,j Ci,jCi,j=2*Ai-1,j=2*Ai-1,

37、j endforendfor endforendfor经分裂法变换后，得到如下并行程序：经分裂法变换后，得到如下并行程序：for for it=1 it=1 toto n n stepstep ssss par-dopar-do for for jtjt=1=1 toto n n step step ssss par-dopar-do for for i=it i=it toto min(n,it+ss-1)min(n,it+ss-1)dodo for for j=j=jtjt to to min(n,jt+ss-1)min(n,jt+ss-1)dodo Ai,jAi,j=Ai,j+Bi,jA

38、i,j+Bi,j Ci,jCi,j=2*Ai-1,j=2*Ai-1,j endforendfor endforendfor endforendfor endforendfor 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 3.3.分裂法分裂法 并行计算中，将同一子块内的全部计算加载到一个处理器上执行。不并行计算中，将同一子块内的全部计算加载到一个处理器上执行。不同处理器执行不同子块。经分裂变换，矩阵同处理器执行不同子块。经分裂变换，矩阵A A、B B、C C的数据都进行了方块的数据都进行了方块划分，其中对划分，其中对C C数据的行向分割比数据的行

39、向分割比A A、B B低一格。低一格。通过此例，可以发现分裂变换既提高了计算的并行性，又控制了通信开销。通过此例，可以发现分裂变换既提高了计算的并行性，又控制了通信开销。数据数据A,B,CA,B,C的划分图的划分图 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 4.4.轮转法轮转法 对于初值为对于初值为0 0，步长为，步长为1 1的循环，我们称之为正规循环。对正规循环可以通过实的循环，我们称之为正规循环。对正规循环可以通过实施轮转法来挖掘其中的并行性，对于非正规的循环，我们总可以通过简单的下标变施轮转法来挖掘其中的并行性，对于非正规的循环，我们总

40、可以通过简单的下标变换使之变为正规循环。换使之变为正规循环。对于如下正规循环：对于如下正规循环：for for i=0 i=0 to to n-1 n-1 dodo for for j=0 j=0 toto m-1 m-1 dodo Process(ai,jProcess(ai,j)endforendfor endforendfor 轮转法的作法与拉伸法很类似，对循环轮转法的作法与拉伸法很类似，对循环j j和循环和循环i i进行拉伸，拉伸系数为进行拉伸，拉伸系数为1 1，可得如下，可得如下并行程序：并行程序：for for i=0 i=0 to to n-1 n-1 dodo for for

41、j=0 j=0 toto m-1 m-1 par-dopar-do Process(ai,(j+i)modnProcess(ai,(j+i)modn)endforendforendforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 5.5.并列法并列法 并列法将循环体中无相关关系可以互相并行的部分折分成几个并列的循环，使并列法将循环体中无相关关系可以互相并行的部分折分成几个并列的循环，使这几个循环之间可以互相并行执行，以如下循环为例：这几个循环之间可以互相并行执行，以如下循环为例：for for i=1 i=1 toto n n do

42、do for for j=1 j=1 toto n n dodo S1;S2;S1;S2;SmSm endforendforendforendfor 这里这里S1,S2,S1,S2,SmSm为相互之间无相关关系的程序段，而且在任意为相互之间无相关关系的程序段，而且在任意SkSk与与SlSl对循环对循环变量变量i i，j j的任不同取值的计算之间也无相关关系。则上述串行程序可变换为如下并的任不同取值的计算之间也无相关关系。则上述串行程序可变换为如下并行程序：行程序：for for k=1 k=1 toto m m par-dopar-do for for i=1 i=1 toto n n dod

43、o for for j=1 j=1 toto n n dodo SkSkendforendfor endforendfor endforendfor 如何从循环体中划分出几个独立的模块，这要使用功能分解的方法。如何从循环体中划分出几个独立的模块，这要使用功能分解的方法。国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 5.5.并列法并列法 例例例例3.103.10 我们以对称方阵我们以对称方阵CHOLESKYCHOLESKY分解为例，说明利用循环重构的过程。分解为例，说明利用循环重构的过程。CHOLESKYCHOLESKY分解串行分解串行算法如下算法

44、如下：输入：对称矩阵输入：对称矩阵A A 输出：下三角矩阵输出：下三角矩阵L L，使得，使得A=LLTA=LLT PROCEDURE PROCEDURE CHOLESKY(A)CHOLESKY(A)Begin Begin for for k=1 k=1 toto n n dodo ak,kak,k=sqrt(ak,ksqrt(ak,k)forfor i=k+1 i=k+1 toto n n dodo ai,kai,k=ai,k/ak,kai,k/ak,k for for j=k+1j=k+1 to to i i do do ai,jai,j=ai,j-ai,kai,j-ai,k*aj,kaj,

45、k endforendfor endforendfor endforendfor for for i=1 i=1 to to n n dodo for for j=1j=1 to to n n dodo ifif (i (i j)j)thenthen li,jli,j=ai,jai,j endifendif endforendfor endforendfor OUTPUT L OUTPUT L End End 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法循环重构循环重构 5.5.并列法并列法 在在CHOLESKYCHOLESKY分解算法中，尽管是循环的最外层，但循

46、环决分解算法中，尽管是循环的最外层，但循环决定了对主元素的选择，而对不同主元素的处理不能同时进行，故定了对主元素的选择，而对不同主元素的处理不能同时进行，故循环必须串行执行。由于循环必须串行执行。由于i i循环在外层，按并行性粒度准则，应该循环在外层，按并行性粒度准则，应该按行划分。考虑到处理器的负载平衡，我们采用行交叉划分。分按行划分。考虑到处理器的负载平衡，我们采用行交叉划分。分析上述析上述CHOLESKYCHOLESKY分解的过程，可发现同一列的计算用到了同一分解的过程，可发现同一列的计算用到了同一个个a a j,kj,k。可将对它的计算独立出来，然后广播至其余同列数据所。可将对它的计算

47、独立出来，然后广播至其余同列数据所在的处理器，为此我们使用并列法将原串行程序中的在的处理器，为此我们使用并列法将原串行程序中的i i循环的循环循环的循环体分成两部分，将对体分成两部分，将对a a j,kj,k 的计算独立出来，而另一部分为对的计算独立出来，而另一部分为对i i，j j的二重循环。由于在对行进行并行处理时，对第的二重循环。由于在对行进行并行处理时，对第j j列的元素的处理列的元素的处理需要接收其它行广播来的需要接收其它行广播来的a a j,kj,k 元素，为了使广播数据集中使用，元素，为了使广播数据集中使用，方便按行的并行处理，我们采用循环交换法对此方便按行的并行处理，我们采用循

48、环交换法对此i i，j j循环进行交换，循环进行交换，从而得到重构后的程序（见下页）：从而得到重构后的程序（见下页）：国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 5.5.并列法并列法 PROCEDUREPROCEDURE CHOLESKY(A)CHOLESKY(A)Begin Begin for for k=1 k=1 to to n n dodo ak,kak,k=sqrt(ak,ksqrt(ak,k)for for i=k+1 i=k+1 to to n n dodo ai,kai,k=ai,k/ak,kai,k/ak,k for for

49、j=k j=k to to n n dodo for for i=j+1 i=j+1 toto n n dodo ai,j+1=ai,j+1-ai,k*aj+1,k ai,j+1=ai,j+1-ai,k*aj+1,k endforendfor endforendfor endforendforendforendfor for for i=1 i=1 toto n n dodo for for j=1 j=1 to to n n dodo if if(i(i j)j)then then li,jli,j=ai,jai,j endifendif endforendforendforendfor OUTPUT L OUTPUT LEndEnd 国家高性能计算中心（合肥）循环程序并行化的一般方法循环程序并行化的一般方法 循环重构循环重构 5.5.并列法并列法 在重构的基础上对矩阵在重构的基础上对矩阵A A按行循环划分，设处理器个按行循环划分，设处理器个数为数为p p，矩阵的阶数为，矩阵的阶数为n n，对矩阵，对矩阵A A行交叉划行交叉划分后，编号为分后，编号为i i的处理器含有的处理器含有A A的第的第 行行 。国家高性能计算中心（合肥）