资源描述：
《并行计算-多媒体课件-并行程序设计-ch03并行程序设计简.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据划分与处理器指派带状划分方法:又叫行列划分，就是将矩阵的整行或整列地分成若干组，各组指派给一个处理器。四个处理器上16×16矩阵带状划分循环程序并行化的一般方法国家高性能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派例3.1设矩阵A有n行和m列，对其串行处理的程序段如下：fori=1tondoforj=1tomdoProcess(a[i,j])endforendfor其中，Process(a[i,j])表示对矩阵元素a[i,j]某种处理过程。设有p个处理器，令，。⑴行划分：在采用行划分的情况下，例3.1串行程序段可转化为如下的并行程
2、序段：fork=1toppar-dofori1=1tordoforj=1tomdoProcess(a[(k-1)r+i1,j])endforendforendfor其中“par-do”表示对循环体用p个处理器并行执行。国家高性能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派⑵列划分：在采用列划分的情况下，例3.1串行程序段可转化为如下的并行程序段：fork=1toppar-doforj1=1tosdofori=1tondoProcess(a[i,(k-1)s+j1])endforendforendfor⑶行循环划分：在采用行循环划分的情
3、况下，例3.1串行程序段可转化为如下的并行程序段：fork=1toppar-dofori1=1tordoforj=1tomdoProcess(a[i1-1]p+k,j)endforendforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派⑷列循环划分：在采用列循环划分的情况下，例3.1串行程序段可转化为如下并行程序段：fork=1toppar-dofori=1tondoforj1=1tosdoProcess(a[i,(j1-1)p+k])endforendforendfor国家高性能计算中心（合肥）循环程序并行化的
4、一般方法数据划分与处理器指派2、块状划分方法所谓块状划分又叫棋盘划分（CheckerBoardPartitioning），就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任一处理器均不包含整行或整列。可分为图3.11(a)所示的块棋盘划分（Block-checkerBoardPartitioning）和图3.11(b)所示的循环棋盘划分（Cyclic-checkerBoardPartitioning）。国家高性能计算中心（合肥）循环程序并行化的一般方法四个处理器上4×4矩阵棋盘划分棋盘划分比带状划分可开发更高的并行度。例如，对于一个的方
5、阵，棋盘划分最多可使用n2个处理器；而带状划分可用的处理器数不能多于n个。数据划分与处理器指派国家高性能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派3.数据划分准则:⑴并行粒度准则：若多处理机系统有p台处理器，所有工作的处理器均经由一单独的全局信号灯同步，要是某一项给定的任务在其完成后要求同步时的最坏时间复杂度为t(m)，那么最大可能加速比为。⑵数据相关性准则：划分后的数据要指派给各处理器去执行一些操作，所以划分应该减少处理器间的通信，把那些彼此相关的数据尽可能分配到同一个处理器上，以使各处理器能独立地工作或只进行少量的通信。国家高性
6、能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派4.基于数据内部相关分析的划分数据内部相关分析是指同一数据划分的相关分析。例3.2设A为一个n阶方阵，有如下串行程序段：fori=1tondoforj=1tondoa[i,j]=a[i-1,j]endforendfor分析矩阵A的元素下标i和j，则i和j的相关方向向量为，各列之间数据无任何相关关系。因此对矩阵A可按列划分。串行程序段可转化为如下并行程序段：fork=1toPPar-doforj1=1tomdofori=1tondoa[i,(k-1)m+j1]=a[i-1,(k-1)m+j1
7、]endforendforendfor国家高性能计算中心（合肥）循环程序并行化的一般方法数据划分与处理器指派4.基于数据内部相关分析的划分例3.3设A为矩阵，有如下串行程序段：fori=1tondoforj=1tondoa[3i,2j]=a[3i-2,2j-1]endforendfor其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和方块划分.在行划分的情况下令,例3.3的串行程序段可以转化为如下的并行程序段：fork=1toPPar-dofori1=1tomdoforj=1tondoa[3(k-1)m+3i1,2j]=
8、a[3(k-1)m+3i1-2,2j-1]endforendforendfor国家高性能计算中心（合肥）循环
