习题

1.1

为求全局总和例子中的my_first_i和my_last_i推导一个公式。需要注意的是：在循环中，应该给各个核分配数目大致相同的计算元素。 （ 提示： 先考虑 n 能被 p 整除的情况）。

for (my_i = my_first_i my_i < my_last_i; ++my_i)
{
	my_x = Compute_next_value(...);
	my_sum += my_x;
}

可以看出对于每个核心$i$，其对应累加的范围是左闭合区间$[my_first_i,my_last_i)$。

假设所有$p$个核心的编号是$0,1,\ldots,p-1$，显然对于除了最后一个核心之外，其余核心的区间长度都应当是$\lceil\frac{n}{p}\rceil$，其中$\lceil\rceil$表示向上取整。

因此，可以得到结果：

• 对于每个核心$i$，显然有$my_first_i=(i-1)\times\lceil\frac{n}{p}\rceil$；
• 对于最后一个核心$i=p$，显然有$my_last_i=n-1$
• 对于除了最后一个核心之外的每个核心$i$，有$my_last_i=my_first_(i+1)=i\times\lceil\frac{n}{p}\rceil$

1.6

在下列情况中，推到公式求出 0 号核执行接受与加法操作的次数。

最初的求全局总和的伪代码

0 号核接受其余$p-1$个核的结果并把它们加起来，因此执行了$p-1$次接受操作和$p-1$次加法操作。

树形结构求全局总和

在树形结构除了根节点那一层的每一层里，0 号核心都接受相邻节点的结果并把它和自己的结果相加，而树形结构有$\lceil\log_2n\rceil+1$层，因此进行了$\lceil\log_2n\rceil$次护额受操作和加法操作。

制作一张表来比较这两种算法在总核数是$2,4,8,\ldots,1024$时，0 号核执行的接收与加法操作的次数

2.2

请解释在 CPU 硬件里实现的一个队列，怎么使用可以提高写直达高速缓存（write-through cache）的性能。

队列的特点是队尾插入队首删除。要提高写直达高速缓存的性能，就要尽量避免频繁操作主存区。因此，可以只将队首和队尾元素放进缓存区，仅在插入删除时更新缓存区。

2.3

回顾之前一个从缓存读取二维数组的示例。请问一个更大矩阵和一个更大的缓存是如何影响两对嵌套循环的性能的？如果 MAX = 8，缓存可以存储 4 个缓存行，情况又会是怎样的？在第一对嵌套循环中对 A 的读操作，会导致发生多少次失效？第二对嵌套循环中的失效次数又是多少？

double A[MAX][MAX], x[MAX], y[MAX];
/* First pair of loops */
for (i = 0; i < MAX; ++i)
	for (j = 0; j < MAX; ++j)
		y[i] += A[i][j] * x[j];
/* Second pair of loops */
for (j = 0; j < MAX; ++j)
	for (i = 0; i < MAX; ++i)
		y[i] += A[i][j] * x[j];

Cache Line	Elements of A
0	A[0][0]	A[0][1]	A[0][2]	A[0][3]
1	A[1][0]	A[1][1]	A[1][2]	A[1][3]
2	A[2][0]	A[2][1]	A[2][2]	A[2][3]
3	A[3][0]	A[3][1]	A[3][2]	A[3][3]

更大的缓存会增加两个循环的性能，其中第一个循环性能增加更多，因为第一个循环是操作的内存地址都是相邻的，缓存增加后从主存中读取元素的次数减少了。同理，更大的矩阵会显著降低第一个循环的性能，而对第二个循环的影响较小。

MAX=8 时，第一对循环的读操作一行有两次缺失的发生，会发生$2\times 8=16$次失效。第二对循环一列有八次缺失的发生，会发生$8\times 8=64$次失效。

2.16

假定一个串行程序的运行时间为$𝑇_{串行} = 𝑛^2$，运行时间的单位为毫秒。并行程序的运行时间为$𝑇_{并行} = 𝑛^2/𝑝 + \log_2𝑝$。对于 n 和 p 的不同值，请写出一个程序并找出这个程序的加速比和效率。在 𝑛 = 10 、 20 、 40 、 …、 320 和 𝑝 = 1 、 2 、 4 、 …、 128 等不同情况下运行该程序。当 𝑝 增加、 n 保持恒定时，加速比和效率的情况分别如何？当 p 保持恒定而 n 增加呢？

如下这段 c 语言矩阵加法的程序，随着 n 的增加，运行时间成二次增长，其对应的并行版本的时间$𝑇_{并行} = 𝑛^2/𝑝 + T_{开销}$。

#define N 320
#define double lf
void addMatrix(lf a[N][N], lf b[N][N])
{
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			a[i][j] += b[i][j];
}

p 增加，n 保持恒定的时候，加速比先增后降，效率降低。

p 保持恒定，n 增加的时候，加速比增加，效率增加。

假设$𝑇_{并行}=𝑇_{串行}/𝑝+𝑇_{开销}$，我们固定 p 的大小，并增加问题的规模。

• 请解释如果$𝑇_{开销}$比$𝑇_{串行}$增长得慢，随着问题规模的增加，并行效率也将增加。
• 请解释如果$𝑇_{开销}$比$𝑇_{串行}$增长得快，随着问题规模的增加，并行效率将降低。

$E=\frac{T_{串行}}{pT_{并行}}=\frac{T_{串行}}{p(𝑇_{串行}/𝑝+𝑇_{开销})}=\frac{1}{1+p\frac{T_{开销}}{T_{串行}}}$,显然$\frac{T_{开销}}{T_{串行}}$越大,效率 E 越小,反之亦然.因此:

• 如果$𝑇_{开销}$比$𝑇_{串行}$增长得慢，随着问题规模的增加，$\frac{T_{开销}}{T_{串行}}$减小,并行效率 E 增加。
• 如果$𝑇_{开销}$比$𝑇_{串行}$增长得快，随着问题规模的增加，$\frac{T_{开销}}{T_{串行}}$增加,并行效率将降低。

2.17

如果一个并行程序所获得的加速比可以超过 𝑝（进程或线程的个数），则我们有时称该并行程序拥有超线性加速比（superlinear speedup）。然而，许多作者并不将能够克服「资源限制」的程序视为是拥有超线性加速比。例如，当一个程序运行在一个单处理器系统上时，它必须使用二级存储，当它运行在一个大的分布式内存系统上时，它可以将所有数据都放置在主存上。请给出另外一个例子，说明程序是如何克服资源限制，并获得大于 𝑝 的加速比的。

当一个程序串行运行的时候，某些资源可能会在程序的不同阶段被重复加载。并行运行的时候，这些资源可以只加载一次，然后进程/线程可以共享，避免重复加载。

2.19

假定$𝑇_{串行}=𝑛,𝑇_{并行}=𝑛/𝑝+\log_2𝑝$， 时间单位为毫秒。如果以倍率 𝑘 增加 𝑝，那么为了保持效率值得恒定，需要如何增加 𝑛？请给出公式。如果我们将进程数从 8 加倍到 16，则 𝑛 的增加又是多少？该并行程序是可扩展的吗？

$E=\frac{T_{串行}}{pT_{并行}}=\frac{n}{p(n/p+\log_2p)}=\frac{n}{n+plog_2p}=\frac{1}{1+\frac{p}{n}\log_2p}$恒定，则$\frac{p}{n}\log_2p\equiv c$，其中 c 为常数。以 kp 代替 p，$n’$代替$n$到左式，有$\frac{p}{n}\log_2p=\frac{kp}{n’}\log_2kp$，即$n’=nk\frac{\log_2kp}{\log_2p}$，因此需要以$k\frac{\log_2k+log_2p}{\log_2p}$的倍率增加 n。

p 从 8 到 16 时，即 k=2，代入得 n 增加的倍率为$2\times\frac{1+3}{3}=\frac{8}{3}$。

该并行程序是可扩展的，因为对于任意一个 n 都可以找到一个对应的相等规模的 p 解决问题。

2.20

一个可以获得线性加速比的程序是强可扩展的吗？请解释。

是。如果一个程序获得了线性加速比，那么问题规模就可以认为是一个常数，且这个常数不随着 p 的变化而变化，我们只需要线性增加进程/线程数量，就能使线性加速后的程序以相同的效率解决不断增加的问题，无需同时增加问题大小。所以这样的程序是强可扩展的程序。