并行计算-多媒体课件-并行程序设计-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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并行 计算 多媒体 课件 程序设计 ch03
限制150内