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

国家高性能计算中心 合肥 数据划分与处理器指派带状划分方法 又叫行列划分 就是将矩阵的整行或整列地分成若干组 各组指派给一个处理器 四个处理器上16 16矩阵带状划分 循环程序并行化的一般方法 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派例3 1设矩阵A有n行和m列 对其串行处理的程序段如下 fori 1tondoforj 1tomdoProcess a i j endforendfor其中 Process a i j 表示对矩阵元素a i j 某种处理过程 设有p个处理器 令 行划分 在采用行划分的情况下 例3 1串行程序段可转化为如下的并行程序段 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 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 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派2 块状划分方法所谓块状划分又叫棋盘划分 CheckerBoardPartitioning 就是将矩阵划分成若干个子矩阵 每个子矩阵指派给一个处理器 此时任一处理器均不包含整行或整列 可分为图3 11 a 所示的块棋盘划分 Block checkerBoardPartitioning 和图3 11 b 所示的循环棋盘划分 Cyclic checkerBoardPartitioning 国家高性能计算中心 合肥 循环程序并行化的一般方法 四个处理器上4 4矩阵棋盘划分棋盘划分比带状划分可开发更高的并行度 例如 对于一个的方阵 棋盘划分最多可使用n2个处理器 而带状划分可用的处理器数不能多于n个 数据划分与处理器指派 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派3 数据划分准则 并行粒度准则 若多处理机系统有p台处理器 所有工作的处理器均经由一单独的全局信号灯同步 要是某一项给定的任务在其完成后要求同步时的最坏时间复杂度为t m 那么最大可能加速比为 数据相关性准则 划分后的数据要指派给各处理器去执行一些操作 所以划分应该减少处理器间的通信 把那些彼此相关的数据尽可能分配到同一个处理器上 以使各处理器能独立地工作或只进行少量的通信 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派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 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 a 3 k 1 m 3i1 2 2j 1 endforendforendfor 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派5 基于数据外部相关分析的划分所谓数据外部相关分析是指对不同数据划分的相关分析 例3 4设A和B均为n阶矩阵 有如形式的下串行程序段 fori 1tondoforj 1tondoendforendfor其中 都是i j的线性组合 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派5 基于数据外部相关分析的划分现在对进行一种数据划分 也有一种数据划分与其对应 使它们被划分的数据块之间无数据相关关系 相应处理器之间不产生通信开销 划分方法如下 对数组 设其划分后某一子阵列的元素下标满足 c为某一常数 对数组 划分后相应子阵列的元素下标有如下关系 将式代入 式得 对于A有对于B有 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派5 基于数据外部相关分析的划分经变换可写为 划分结果要使得相关数据被划分至同一处理器中 各处理器间无通信开销 则必须满足以下条件 对于固定值c 由此式可求得 及 国家高性能计算中心 合肥 循环程序并行化的一般方法 数据划分与处理器指派5 基于数据外部相关分析的划分例3 5 设A为n阶矩阵 B为矩阵 对如下二重循环计算 fori 2tondoforj 2tondoendforendfor存在如下数据相关关系 即满足上述关系的有很多组 例如 取即对常数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元素被分配到相同的处理器中 计算时处理器之间不发生通信 由于斜线划分不利于并行计算 故采用第二种划分方法 进而可得出相应的并行程序 fori 2tonpar doforj 2tondoendforendfor 迭代空间数据相关图 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构1 循环交换通过交换内外循环的先后次序对循环体结构进行调整 以实现划分后处理器内部数据的局部相关 从而减少通信开销 提高计算的并行性 对如下循环 fori 1tondoforj 1tondoa i j a i 1 j endforendfor按数据相关性准则 的相关方向向量为 应该对矩阵A按列划分 按并行粒度准则 循环的最外层是i 应该对矩阵A按行划分 两条准则发生矛盾 现交换I j循环的先后次序 通过重构得到如下并行程序 forj 1tonpar dofori 1tondoa i j a i 1 j endforendfor 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构1 循环交换上例中 对i的循环具有相关性 对它应该串行执行 因此可利用循环交换 使无相关性的分量调换至最外层 在循环交换时 应该注意循环初值和终值的变化 对于如下循环 fori 1tondoforj i 1tondoProcess a i j endforendfor由于内层循环j的初值是外层循环i的函数 在循环交换后 这样的初值和终值也相应地变化为 forj 2tondofori 1toj 1doProcess a i j endforendfor 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构2 拉伸法例3 6 在下列程序中 fori 1tondoforj 1tondoa i j a i 1 j a i j 1 endforendfor有两个相关向量 及 由于行列间皆存在相关关系 所以既不能进行行列块划分 方块划分 也不能进行行列循环划分 但如果我们对j循环用i循环进行拉伸 拉伸系数为1 得到如下程序 fori 1tondoforj i 1toi ndoa i j i a i 1 j i a i j i 1 endforendfor 拉伸前的数据相关图 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构2 拉伸法由图可见 对相同j值 沿i方向的计算无相关关系 因此交换i j循环先后次序 i循环可并行执行 得到如下并行程序 forj 2to2ndofori max 1 j n tomin n j 1 par doa i j i a i 1 j i a i j i 1 endforendfor由上述程序可见 由于各行之间的计算可以并行 因此对A矩阵进行行块划分 拉伸后的数据相关图 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构2 拉伸法例3 7 设A为n阶矩阵 有串行程序如下 fori 1tondoforj 1tondoa i j a i j 1 a i j 1 a i 1 j a i 1 j 4endforendfor n 5时的数据相关图 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构2 拉伸法若按串行程序所定义的执行顺序 对A中的元素的可并行执行顺序如前面图所示 图中 i j 位置上的数字T表示元素a i j 可并行计算的时间 例如a 1 1 可在T 1时计算 a 2 1 及a 1 2 可在T 2时并行计算等 即 沿对角线方向上的计算可以并行 为了挖掘此并行性 我们采用拉伸法对串行程序进行改造 对循环j利用循环i进行拉伸 拉伸系数为1 得到如下程序 fori 1tondoforj 1 iton idoa i j i a i j 1 i a i j 1 i a i 1 j i a i 1 j i 4endforendfor通过交换内外循环的先后次序 得到如下并行程序 forj 2to2ndofori max 1 j n tomin n j 1 par doa i j i a i j 1 i a i j 1 i a i 1 j i a i 1 j i 4endforendfor调整后的内层循环将被并行执行 即在同一列的各行之间并行 因此对A进行行块划分 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构3 分裂法分裂法是一种通过将循环迭代空间细分成相同形状和大小的数据块以达到局部化相关关系的变换方法 变换之后 一个子数据块内部的全部迭代被同一个处理器执行 只有在子数据块之间计算才需要通信 分裂法的变换分两步进行 第一步 将原算法中的每重循环按块连续划分 细化为双重嵌套循环 外层对子块进行循环 内层对块内数据进行循环 第二步 将所有对子块的循环交换至经变换后循环体的最外层以并行执行 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构3 分裂法例3 8 设A B C为n阶矩阵 有串行程序如下 fori 1tondoforj 1tondoA i j A i j B i j C i j 2 A i 1 j endforendfor经分裂法变换后 得到如下并行程序 forit 1tonstepsspar doforjt 1tonstepsspar dofori ittomin n it ss 1 doforj jttomin n jt ss 1 doA i j A i j B i j C i j 2 A i 1 j endforendforendforendfor 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构3 分裂法并行计算中 将同一子块内的全部计算加载到一个处理器上执行 不同处理器执行不同子块 经分裂变换 矩阵A B C的数据都进行了方块划分 其中对C数据的行向分割比A B低一格 通过此例 可以发现分裂变换既提高了计算的并行性 又控制了通信开销 数据A B C的划分图 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构4 轮转法对于初值为0 步长为1的循环 我们称之为正规循环 对正规循环可以通过实施轮转法来挖掘其中的并行性 对于非正规的循环 我们总可以通过简单的下标变换使之变为正规循环 对于如下正规循环 fori 0ton 1doforj 0tom 1doProcess a i j endforendfor轮转法的作法与拉伸法很类似 对循环j和循环i进行拉伸 拉伸系数为1 可得如下并行程序 fori 0ton 1doforj 0tom 1par doProcess a i j i modn endforendfor 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构5 并列法并列法将循环体中无相关关系可以互相并行的部分折分成几个并列的循环 使这几个循环之间可以互相并行执行 以如下循环为例 fori 1tondoforj 1tondoS1 S2 Smendforendfor这里S1 S2 Sm为相互之间无相关关系的程序段 而且在任意Sk与Sl对循环变量i j的任不同取值的计算之间也无相关关系 则上述串行程序可变换为如下并行程序 fork 1tompar dofori 1tondoforj 1tondoSkendforendforendfor如何从循环体中划分出几个独立的模块 这要使用功能分解的方法 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构5 并列法例3 10我们以对称方阵CHOLESKY分解为例 说明利用循环重构的过程 CHOLESKY分解串行算法如下 输入 对称矩阵A输出 下三角矩阵L 使得A LLTPROCEDURECHOLESKY A Beginfork 1tondoa k k sqrt a k k fori k 1tondoa i k a i k a k k forj k 1toidoa i j a i j a i k a j k endforendforendforfori 1tondoforj 1tondoif i j thenl i j a i j endifendforendforOUTPUTLEnd 国家高性能计算中心 合肥 循环程序并行化的一般方法 循环重构5 并列法在CHOLE