当前位置：首页 > article >正文

第3章并行循环调度的准则

article 2024/12/28 10:16:04

第3章

不同循环独立是前提
反例:全局变量 total = total + fuction(…)
此时total还需要进行同步…

首先，让我们来定义一下要考察的类型。在本章中，我们假设每个循环的
迭代都与其他循环是相互独立的，也就是说，一个迭代的执行，并不使用前一个迭代的结果。
如果我们不认真处理如何给 worker 分配迭代任务，例如如何做循环调度就可能引起比较大的负载均衡问题。并且，通常我们不可能提前知道循环迭代的时间，因此，高效的循环调度问题是非常困难的。解决这些问题的方法是本章的重点。

3.1 循环调度的通用记法

假设我们有k个进程和很多循环迭代。另外，假设我们提前并不知道每
个循环迭代需要花费多长时间。常见的循环调度的类型如下:
静态调度:循环迭代是在执行开始之前分配给循环迭代的进程的。
动态调度:把循环迭代分配给进程的过程是在执行时进行的。
每当一个进程结束一个循环迭代时，它拾起一个(使用组块化时是几个)新的循环迭代来继续工作。
分块:将一组而非一个循环迭代分配给一个进程。比如在动态调度中，当
一个进程变为空闲状态时，它拾起一组新的循环迭代来继续工作。
反向调度:在某些应用中，一个迭代的执行时间会随着这个循环索引的
增长而增长。出于下文要说明原因考虑，把迭代的顺序进行反向会更加
有效率。
**注意:**静态调度和动态调度只能二选一，但既可以做组块化，又可以做
反向调度。

具体的例子

具体来说，假设我们有循环迭代A、B和C，以及两个进程P1和P2。
考虑这两种循环调度方式:
在这里插入图片描述
假设循环迭代 A、B和C的执行时间分别是 10、20和40。
让我们看看使用这两个调度方式，
我们消耗多长时间完成整个循环迭代集合，以及会在空闲状态上浪费多少时间。

3.2 snow中的分块(可能手撕)

通过代码实现,手动完成分块

3.2.1 示例：相互外链问题

和1.4.5中的代码相同,
跟从前一样，我们的mutoutpar()函数将i的值分块，但现在它们是真
正的块，而不像从前每个块只有一个i。这是通过snow包中的cluster-
Split()函数完成的:(原来是4/4,现在是400/4,代码相同,效果不同)
在这里插入图片描述

3.8 块大小的问题

在这里插入图片描述

3.9 示例：并行距离计算

略…

3.10 foreach包

在这里插入图片描述

3.10.1 示例：相互网页外链问题

第一章的串行代码如下:
在这里插入图片描述
使用foreach进行改写,详情见mulink.R文件

用户时间（user）：指的是程序在用户模式下执行的时间，不包括系统调用的时间。
系统时间（system）：指的是程序在内核模式下执行的时间，比如系统调用。
经过时间（elapsed）：指的是从程序开始执行到结束的总时间，包括了用户时间和系统时间。

3.10.2 使用foreach要当心

foreach:
将一层for改写为foreach,易并行时效率高
当有更高级的算法,例如将2层for改写为矩阵乘法时,效率就不是最优的了.

3.12 另一种调度方案：随机任务置换

在提前不知道迭代时间的情形下，另一个可行的方案是在计算开始前，对迭代顺序进行随机化。

tasks <- if (!reverse) seq(1, ncombs, chunk) 
else seq(ncombs, 1, -chunk)
nt <- length(tasks)
randpermut <- sample(1:nt, nt, replace=FALSE)
tasks <- tasks[randpermut]

if (!dyn) {
    out <- clusterApply(cls, tasks, dochunk, x, y, allcombs, chunk)
} else {
    out <- clusterApplyLB(cls, tasks, dochunk, x, y, allcombs, chunk)
}