任务并行、数据并行的应用

任务并行

将待解决问题所需要执行的各个任务分配到各个核上执行。

数据并行

将待解决问题所需要处理的数据分配给各个核，每个核在分配到的数据集上执行大致相似的操作。

冯诺依曼体系结构的瓶颈及改进，Flynn分类法涉及的几种模型及其特点

冯诺依曼体系结构的瓶颈及改进

瓶颈：CPU和主存分离

改进：使用 cache

局部性：在访问完一个内存区域（指令或者数据），程序会在不久的将来（时间局部性）访问邻近的区域（空间局部性）。

Flynn分类法涉及的几种模型及其特点

Flynn 分类法的模型

SISD（单指令单数据流）

一次执行一条指令，一次存取一个数据项。

SIMD（单指令多数据流）

• 通过在处理器之间划分数据而实现的并行性

缺点：

• 所有ALU都需要执行相同的指令，或者保持空闲状态。

• 在经典设计中，它们还必须同步运行。

• ALU不能进行指令存储。

• 对于大型数据并行问题有效，但对于其它更复杂的并行问题无效。

MISD（多指令单数据流）

MIMD（多指令多数据流）

支持多个数据流上同时运行多个指令流

一致内存访问（Uniform Memory Access）：

特点：每个核访问内存中任何一个区域的时间都相同

非一致内存访问（Nonuniform Memory Access）：

特点：

Cache的特点，Cache缺失、Cache命中、Cache一致性及解决方法、伪共享、流水线、多发射

缓存的问题

当CPU写数据到cache时，cache中的值可能与主存中的值不一致，有两种解决方法。

• 写直达（Write-through caches）当CPU向cache写数据时，高速缓存行会立即写入主存中。
• 写回（Write-back caches）将缓存中的数据标记为脏数据。当缓存行（cache line）被内存中的新缓存行替换时，脏缓存行被写入内存。

伪共享

两个线程可能访问同一个内存中不同的位置，但是当这两个位置属于同一缓存行时，缓存一致性硬件所表现出来的处理方式就好像这两个线程访问的是内存中的同一位置，如果其中一个线程更新了它所访问的主存地址的值，那么另外一个变量试图读取它要访问的主存地址时，它不得不从主存获取该值。也就是说，硬件强制该线程表现得好像它共享了变量，因此这种情况称为伪共享，这会大大降低共享内存程序的性能。

Cache缺失、Cache命中

cache 命中：处理器所要访问的存储块在高速缓存中的现象。

cache 缺失：处理器所要访问的存储块不在高速缓存中的现象。

流水线、多发射

指令级并行：通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。

流水线：将功能单元分阶段安排。

多发射：让多条指令同时启动。

静态多发：计算单元是在编译时被安排的

动态多发：功能单元是在运行时被安排的

Cache一致性及解决方法

Cache一致性：程序员无法控制缓存和何时更新。在多核系统中，各个核的Cache存储相同变量的副本，当一个处理器更新Cache中该变量的副本时，其他处理器应该知道该变量已经更新，其他处理器中Cache的副本也应该更新。这是Cache一致性问题。

解决方法：监听Cache一致性协议、基于目录的Cache一致性协议。

加速比、效率、阿姆达尔定律

加速比：$S=\frac{T_{串行}}{T_{并行}}$

效率：$E=\frac{S}{P}=\frac{T_{串行}}{P\times T_{并行}}$

阿姆达尔定律（Amdahl’s law）：除非所有的串行程序都能够并行，否则无论可用的核的数量再多，加速将非常有限。

例子：

90%的串行程序可以并行化；无论使用多少核p，并行化都是“完美的”；$T_{serial}$= 20 秒；
可并行部分运行时间为：$0.9\times T_{serial}/p=18/p$
不可并行化”部分的运行时间为：$$0.1\times T_{serial}=2$$
总的运行时间为：$$T_{parallel}=0.9\times T_{serial}/p+0.1\times T_{serial}=18/p+2$$
加速比：$S=\frac{T_{serial}}{0.9\times T_{serial}/p+0.1\times T_{serial}}=\frac{20}{18/p+2}$

静态线程、动态线程、伸缩性/可扩展性、数据依赖的识别、任务划分方式及应用

静态线程、动态线程

动态线程

主线程通常等待工作请求，当一个请求到达时，它派生出一个工作线程来执行该请求。当工作线程完成任务，就会终止执行再合并到主线程中。这种模式充分利用了系统的资源，因为线程需要的资源只在线程实际运行时使用。

特点：资源的有效使用，但是线程的创建和终止非常耗时。

静态线程

创建线程池并分配任务，但线程不被终止直到被清理。

特点：性能更好，但可能会浪费系统资源。

可扩展性

可扩展性

如果一个技术可以处理规模不断增加的问题，那么它就是可扩展的

强可扩展性：

如果在增加进程或线程的数量时，可以维持固定的效率，却不增加问题规模，那么程序被称为强可扩展的

弱可扩展性：

如果在增加进程或线程的数量时，只能以相同倍率增加问题的规模才能使效率值保持不变。

任务划分方式及应用

Foster的方法

1. 划分（Partitioning）：将要执行的指令和数据按照计算拆分为多个小任务。 这一步的关键在于识别出可以并行执行的任务。
2. 通信（Communication）：确定前一步所识别出来的任务之间需要执行哪些通信。
3. 聚集或聚合（Agglomeration or aggregation）：将第一步中确定的任务和通信合并成更大的任务。 例如，如果任务A必须在任务B执行之前执行，那么将它们聚合为单个复合任务可能更为明智。
4. 分配（Mapping）：将上一步聚合好的任务分配给进程/线程。这一步还要使通信最小化，使得每个进程/ 线程得到的工作量大致均衡（负载均衡）。

为什么要并行计算

关于并行程序，首先思考它的目的，具体来说：

1. 为什么我们要不断提高性能? 因为计算能力的提升是很多邻域能够进步的核心。
2. 为什么我们要建立并行系统？ 因为对于单处理器而言，其性能的提升实际是提高了处理器上晶体管的密度，但受限于散热问题等，密度无法一直提升。如果考虑并行化，即生产多个相对简单的完整处理器放在一个芯片上，即多核处理器，就能解决密度问题。
3. 为什么我们要写并行程序？ 编写并行程序是为了充分发挥多核处理器的优势，然而将串行程序改写成并行程序并不顺利。

关于并行程序和串行程序，举一个例子，假设要计算$n$个数的值，并求它们的和。对于这个问题，串行代码解法如下：

sum = 0;
for (i = 0; i < n; i++) {
    x = Compute_next_value(...); // 求得x的值
    sum += x;
}

现假设计算机有$p$个核，且$p<<n$，那么每个核只需处理约$\frac{n}{p}$个数的求值及加和，此时代码如下：

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

上面代码中的my_开头的变量代表了每个核的私有变量。

当每个核计算得到自己的my_sum后，这些核把这个结果发送给核master，由master这个核来计算总和sum：

if (IsMasterCore) {
    sum  = my_x;
    for each core than myself {
        receive value from core;
        sum += value;
    }
} else {
    send my_x to the master;
}

当然，让master完成最终的求和并不是最优解，在核数足够多的情况下，可以采取如下策略：让0号核加上1号核的值，2号核加上3号核的值，以此类推，即偶数号核加上其后一号的核对应的值；然后让0号核加上2号核的值，4号核加上6号核的值……

虽然最优解听上去很完美，但是却难以作为一套方案通过编写并行程序来实现。因此才会有上面提到的，改写不顺利，但不能因为不顺利就浪费掉多处理器的能力。

如何编写并行程序

这个问题取决于如何在内核间划分工作的想法。主流的划分方法有：任务并行(task-parallelism) 和 数据并行(data-parallelism)。顾名思义：

• 任务并行：不同的核分配到的任务不同，每个核各司其职，最终完成整个任务。
• 数据并行：每个核处理的任务相似，但是处理的数据则不同。

在上面提到的求值并求和的例子中，master和其余核就是任务并行的一个实例，而除了master以外的这些核在做求值和加法运算的过程就是一个数据并行的实例。

编写并行程序过程中需要协调的问题：

1. 通信(communication）
2. 负载均衡(load balancing)
3. 同步(synchronization)

编写显式并行（explicit parallel）程序

这里学习三种不同的C扩展：

• Message-Passing Interface (MPI)
• POSIX threads (Pthreads)
• OpenMP

在学习的过程中，将重点关注两种主要类型的并行系统：共享内存系统 (shared-memory system)和分布式内存系统 (distributed-memory system)。

在共享内存系统中，核心可以共享对计算机内存的访问；原则上，每个核都可以读写每个内存位置。（Pthreads, OpenMP）

在分布式内存系统中，每个核都有自己的私有内存，核必须通过通过网络发送消息之类的方式显式通信。（MPI）

上图中，图(a)是共享内存系统，图(b)是分布式内存系统。

并发、并行和分布式

在并发计算中，一个程序是指在任何时刻都可以同时进行多个任务的程序。

在并行计算中，一个程序是指多个任务紧密合作来解决一个问题的程序。

在分布式计算中，一个程序可能需要与其他程序合作来解决一个问题。

// 以上内容整理自《Introduction to Parallel Programming》一书

2.1 当讨论浮点数加法时，我们简单那地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都花费2纳秒，其余的每个操作耗费1纳秒。
a 在上述假设下，每个浮点数加法要耗费多少时间？
b 非流水线1000对浮点数的加法要耗费多少时间？
c 流水线1000对浮点数加法要耗费多少时间？
d 如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上去数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水线会发生什么情况？如果又发生二级缓存失效，又会怎样？

解答：

a 对照第17页的图，自行画一下就出来了，9纳秒

b 因为1000对要串行执行，所以9 * 1000 = 9000纳秒

c 这个可以画一下图，可能更有助与明白为什么这么算。1000 + (9 - 1) = 1008纳秒
(感谢sinat_26845549同学的提醒)这里确实是计算错误了。
这里根据17页的提示
【引用】有些延迟（例如等待操作数）会造成流水线的阻塞。
这里可以画图，得出一个函数表达式：f(n)=2n+7。这里的n就是浮点数加法对的数量。
所以，这里的答案应为f(1000)=2007ns

d ① 因为指令会逐层查询，所以在一级缓存失效的时候，会去二级缓存中找，这样这次指令查找的时间为2+5=7纳秒。

② 假设这里的告诉缓存只有两级，这次指令查找的时间为2+5+50=57ns
对于整个流水线来说，只要这两次失效不在最后执行的几个任务上发生，那么对于整体的执行时间不会有影响。这个可以从第18页图中看出来。

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

解答：

因为高速缓存的速度要比主存块很多，且写直达有一个特性就是，当CPU想Cache写数据时，高速缓存行会立即写入主存中。

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

解答：

① 当矩阵增大时，第一个嵌套循环的缺失次数要增加。

 当缓存增大时，第一个嵌套循环的缺失次数会减少。

 第二个嵌套循环在矩阵增大的情况下缺失次数会增多，当缓存达到一定程度的时候，才会出现缺失次数减少的情况。

② 这里假设每个缓存行可以存4个元素。

 第一个循环一行有两次缺失的发生，所以2*8=16次

 第二个循环一列有八次缺失的发生，所以8*8=64次

2.4 在表2-2中，虚拟地址由12位自己偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样页大小和虚拟空间，这个程序有多少页？

解答：

页的数量=2^20=1048576=1024k

2.5 在冯·诺依曼系统中加入缓存的虚拟内存改变了它作为SISD系统的类型吗？如果加入流水线呢？多发射或硬件多线程呢？

解答：

① 这里没有改变SISD的类型，这里只是对与数据的存储做了一定的处理，而没有对指令和数据的数量进行变动。

② 当加入流水线是属于指令级别的并行，所以当加入流水线时，系统的类型变为MISD。

③ 添加多发射和硬件多线程也是一样的，依旧是数据指令级别的并行，所以系统还是MISD。

2.6 假设一个向量处理器的内存系统需要用10个周期从内存载入一个64位的字。为了使一个载入流的平均载入时间为一个周期载入一个字，需要多少个内存体(memory bank)?

解答：

那这里就需要10个了。因为这里需要在一个周期内将64位的字进行载入，所以使用10个刚好能在一个周期内完成读取。当字的各个部分分布在不同的内存体中时，那么在装入/存储连续数据时能够几乎无延迟的访问，这样就能保证平均载入时间为一个周期的要求了。

2.7 请讨论GPU与向量处理器执行以下代码时的不同之处：

sum = 0.0;
for (i = 0; i < n; i++){
  y[i] += a*x[i];
  sum += z[i]*z[i];
}

解答：

① 因为向量处理器是单指令多数据的处理方式，所以对于上面的代码其可能会分为两个指令来执行。下面分解一下上面的代码，其中每一个循环代表着一个向量指令。

sum=0.0;
for (i = 0; i < n; i++){ // loop 1
  y[i] += a*x[i];
}
for (i = 0; i < n; i++){  // loop 2
  sum += z[i]*z[i];
}

通过这两指令来完成。
②而GPU的处理方式就不大一样了，虽然书中没有提任何有关GPU计算的方式。不过就根据本人接触到的异构计算，GPU应该会这样做：

sum = 0.0 // host side

// create a buffer for sum(host side)
int _sum[n]={0};

// the 1st GPU processor(device side)
{
  y[0] += a*x[0];
  sum[0] += z[0]*z[0];
}

// the 2ed GPU processor(device side)
{
  y[1] += a*x[1];
  sum[1] += z[1]*z[1];
}

...

// the n th GPU processor(device side)
{
  y[n-1] += a*x[n-1];
  sum[n-1] += z[n-1]*z[1];
}

//host
sum= sum[0]+sum[1]+...+sum[n-1];  // (host side)

这样就可以看出两者的差别了吧。GPU是将每个计算分解成一个任务，让一个GPU处理器来完成，所以这里GPU的方式类似与SIMD，但也如书中所写，GPU不是纯粹的SIMD系统。

2.8 如果硬件多线程处理器拥有大缓存，并且运行多个线程，请解释为何改处理器的性能会下降。

解答：

这里和大缓存的关系并不大，重要的影响是来自于多个线程。因为在硬件多线程处理器中，当前任务需要等待数据从内存中读出，那么它可以通过执行其他线程而不是继续当前线程来发掘并行性。所以就需要支持线程间的快速切换，当切换速度过慢且线程的数量过多的情况下，性能自然会下降。

2.9 在关于并行硬件的讨论中，用Flynn分类发来识别三种并行系统：SISD、SIMD和MIMD。我们讨论系统中没有多指令单指令流单数据系统，或称为MISD系统。那么，MISD系统是如何工作的呢？请举例说明。

解答：

从名字上就能看出来，对于单个数据，进行不同的指令操作。比如，处理器取到了一个数据，在同一时间对这个数据进行乘和减的操作。这样的系统没有存在的意义，其功能完全可以由SIMD或MIMD进行替换。

2.10 假设一个程序需要运行10^12条指令来解决一个特定的问题，一个单处理器系统可以在10^6秒(大约11.6天)内完成。所以，一个单处理器系统平均每秒运行10^6条指令。现在假设程序已经实现并行化，可以在分布式内存系统上运行。该并行程序使用p个处理器，每个处理器执行(10^12)/p条指令并必须发送10^9(p-1)条消息。执行该程序时，不会有额外的开销，即每个处理器执行完所有的指令并发送完所有的消息之后，程序就完成了，而不会有由诸如等待消息等事件所产生的延迟。那么：
a 假设发送一条消息需要耗费10^-9秒。如果使用1000个处理器，每个处理器的速度和单个处理器运行串行程序的速度一样，那么该程序的运行需要多少时间？
b 假设发送一条消息耗费10^-3秒。如果使用1000个处理器，那么改程序的运行需要多少时间？

解答：

这里每个核上的总工作时间为：指令+发送消息= (10^12)/p/T指令 + 10^9(p-1)/T消息

① 根据上面方程可得，(10^12)/1000/(10^6) + 10^9(1000-1)/10^9 = 1999s。

② (10^12)/1000/(10^6) + 10^9(1000-1)/10^3 = 999001000s =1.0547年

2.11 请写出不同的分布式内存互连形式的总连路数的表达式。

解答：

分布式内存互连网络通常分成两种：直接链接与间接互连。因为间接链接没有固定的表达式，所以这里只罗列出直接连接的表达式：环状直连（2p），环面网格（3p），等分宽度（2p^(1/2)），全相连网络（(p^2)/2+p/2）,超立方体（4*log(p)）【以2为底的log】。

2.12
a 除了没有循环链接(“wraparound” link)，平面网格（planar mesh）和二维环面网格(toroidal mesh)是相似的。请问一个平面网格的等分宽度是多少？
b 三维网格与平面网格是相似的，除了三维网格拥有深度这个特性外。请问一个三维网格的等分宽度是多少？

解答：

这个等分宽度的确是没有怎么看懂。只能根据推断来做了。

a 这个不太清楚怎么去求，因为当平面内有奇数个核就不太清楚应该怎么去求了。
b 感觉应该是（1+log(p)）【以2为底的log】

2.13
a.请画出一个思维超立方体结构
b.请用超立方体的归纳定义来解释为何超立方体的等分宽度为p/2

解答：

a.这个可以在网上找一下图，百度一下挺多的。这里我上传两幅图。

b.这个就省略了吧，真的不知为何

2.14
为了定义间接网络的等分宽度，我们将处理器分为两组，每组拥有一半数量的处理器。然后，在网络的任意处移除链接，使两组之间不再链接。移除的最小连路数就是该网络的等分宽度。当我们对链路计数时，如果图中用的是单向链接，则两条单向链接算作一条链路。请说明一个8x8的交叉开关的等分宽度小于等于8，并说明一个拥有8个处理器的omega网络的等分宽度小于或等于4。

解答：

这是一道证明题，自己对这块的理解还差很多，这里也就先略过吧。

2.15
a. 假定一个共享内存系统使用监听一致性协议和写回缓存。并假设0号核的缓存里有变量x，并执行赋值命令x=5。1号核的缓存里没有变量x。当0号核更新x后，1号核开始尝试执行y=x。y被赋值是多少？为什么？
b. 假设上面的共享内存系统使用的基于目录的协议，则y的值将是多少？为什么？
c. 你能否为前两部分中所发现的问题提出解决方案？

解答：

a.因为x在更新前，1号核并没有x这个变量。所以，在1号核的cache中，x变量的副本是已经被广播更新了的。这里y的值是5。

b.与监听一致性协议不同的是，基于目录的Cache一致性协议是可以直接访问另一核的内存的。所以，在1号核要对y赋值时，会去0号核的内存中获取x变量的值。这里y依旧是5。

c.以上两种一致性解决办法都有其自身的缺点，这些缺点在书中第29页中也提到了。所以，有了两者结合的解决方案——“基于目录的Cache一致性协议”。

2.16
a.假定一个串行程序的运行时间为T(串行)=n^2，运行时间单位为毫秒。并行程序的运行时间为T(并行)=(n^2)/p+log(p)【以2为底】。对于n和p的不同值，请写一个程序并找出这个程序的加速比和效率。在n= 10、20、40、。。。、320和p=1、2、4、。。。、128等不同情况下运行该程序。当p增加、n保持恒定时，加速比和效率的情况分别如何？当p保持恒定而n增加呢？
b. 假设T(并行)=T(串行)/p+T(开销)，我们固定p的大小，并增加问题的规模。
· 请解释如果T(开销)比T(串行)增长的慢，随着问题规模的增加，并行效率也将增加。
· 请解释如果T(开销)比T(串行)增长的快，随着问题规模的增加，并行效率将降低。

解答：

a. 这里n是问题规模，而p则是加速比。当p选定时，问题规模越大，实际加速比越靠近p；效率也会有所上升，并趋近于1。

b. 这里使用公式来证明的比较好。我们知道效率的公式是E=T(串行)/(pxT(并行))。带入题目中的并行表达式，得E=T(串行)/(pxT(串行)/p+T(开销))，这个方程看着还是不直观，对等号两边求倒得1/E=1+pxT(开销)/T(串行)，在这个等式中，当p固定，开销时间与效率成反比，串行时间与效率成正比。这就解释了上面两个情况。

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

解答：
自己的理解就是在缓存上不存在“未命中”的情况，加速了数据的载入速度，从而超除了应有的加速比。
这里引用wiki和百度百科的解释。摘取关键部分，对其他内容有兴趣的可以直接去百科上查看。
超线性加速比有几种可能的成因，如现代计算机的存储层次不同所带来的“高速缓存效应”；具体来说，较之顺序计算，在并行计算中，不仅参与计算的处理器数量更多，不同处理器的高速缓存也集合使用。而有鉴于此，集合的缓存便足以提供计算所需的存储量，算法执行时便不必使用速度较慢的内存，因而存储器读些时间便能大幅降低，这便对实际计算产生了额外的加速效果。

2.19
假定T(串行)=n,T(并行)=n/p+log(p)【以2为底】，时间单位为毫秒。如果以倍率k增加p，那么为了保持效率值恒定，需要如何增加n？请给出公式。如果我们将进程数从8加倍到16，则n的增加又是多少？该并行程序是可扩展的吗？

解答：
以下log都是以2为底的。
1）这里需要效率相等，所以我们可以将加倍和没加倍之前的效率放在等号两边。
就有
n/[p(n/p+log(p))]=n’/[kp(n’/kp+log(kp))],
计算可得n’/n=klog(kp)/log(p)=klog(k)/log(p)+k
2）可以通过与上一小题相同的方式来计算。我算得结果是n’/n=8/3
3）这里需要重温一下“可扩展”的定义了。【引用】“一个并行程序，如果问题的规模与进程/线程数都以一定的倍率增加，而效率保持一个常数值，那么该并行程序就是可扩展的。”所以本题的程序是可扩展的。

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

解答：
是的。根据加速比的计算公式S=T(串行)/(T(串行)/p+log(p))，当获得线性加速比时，S=p，则这里分母部分中对数的那部分就完全多余了；可以写成，S=T(串行)/(T(串行)/p)，这样的话加速比与问题规模就没有关系了，所以这里问题规模就可以认为是一个常数，且这个常数不随着p的变化而变化，所以这样的程序是强可扩展的程序。

2.21
Bob有个程序，相对两组数据进行计时，input_data1和input_data2。为了在程序中加入计时函数前得到一些想法，他用两组数据和UNIX的shell命令time，运行了程序：
$ time ./bobs_prog < input_data1

real 0m0.001s
user 0m0.001s
sys 0m0.000s
$ time ./bobs_prog < input_data2

real 1m1.234s
user 1m0.001s
sys 0m0.111s

Bob用的时间函数的精度为毫秒。Bob应该使用第一组数据和时间函数对他的程序计时吗?如果使用第二组数据呢？请分别解释使用和不使用的原因。

解答：
不建议使用第一组数据用来计时。根据题目可以看出来data1明显要比data2的数据规模小很多，这样的话，毫秒级的计时对于data1来说就不够用了，而使用data2来计时就很容易看出程序在运行时所消耗的时间，以及系统中是否有其他任务在CPU上运行。有关于time命令的解析，大家可以使用man time或 该博客中查看。

2.22
正如我们在习题2.21中所看到的，UNIX的shell命令time报告用户时间、系统时间，以及“实际”时间或全部耗费的时间。
假设Bob定义了一下这些可被C程序调用的函数：
double utime(void)
double stime(void)
double rtime(void)
第一个函数返回的是从程序开始执行用户时间所消耗的秒数。第二个返回的是系统时间秒数，第三个是总时间秒数。大致上，用户时间主要消耗在不需要操作系统执行的用户代码和数据库函数上，如sin和cos函数。系统时间耗费在那些需要操作系统执行的函数上，如printf和scanf函数。
a. 这三个函数值的数学关系是怎么样的？假定程序包含如下代码：
u=double utime(void)
s=double stime(void)
r=double rtime(void)
请写出u、s和r之间关系的表达式(可以假定忽略函数调用的时间花费)
b. 在Bob的系统上，任何使用，如果一个MPI进程在等待消息，则它花费的时间不计入utime和stime，而计入rtime。请解释Bob是如何根据这些条件来确定一个MPI程序是否在等待消息上耗费了过多时间。
c. Bob提供给了Sally他的计时函数。然而，Sally发现在她的系统上，一个MPI进程在等待消息上的时间是计入用户时间的。那么，Sally可以用Bob的函数去判断一个MPI进程是否在等待消息上耗费了过多时间吗？请解释。

解答：
a. 这里根据题目对三种时间的描述，CPU时间应该是用户态执行的时间，加上内核态执行的时间(也就是stime)，而实际CPU运行的时间，则为rtime。根据题目中给出的代数字母，可得r=u+s(理论上)(实际是r>=u+s)。
b. 这里假设MPI进程除了执行，就是等待消息状态，再无其他状态。可以使用rtime的时间减去其他两个时间的和，这个差值必然是大于等于0的小数，Bob可以根据这个差值的大小来判断，MPI进程是否在等待消息上花费了过多的时间。
c. 在Sally系统上，就不满足a问中的表达式，这个表达式应该r=u+s，而不会有大于的情况了。这里因为实际代码运行的时间无法计算出来，也就是用户代码的执行时间，所以无法得知在等待消息上是否耗费了过多的时间。

2.23
在我们应用Foster方法来构建直方图的过程中，我们实质上是用data数组的元素来识别聚合任务的。一个很明显的替代方法是，使用bin_counts数组的元素来识别聚合任务，所以一个聚合任务会由bin_counts[b]的增加，和返回b的Find_bin函数的调用所组成。请解释为何这样聚合可能存在问题。

解答：
这里应该是这么一个过程。
还是使用书44页中的例子，然后算出桶数为五个，然后用一个桶接一个桶的方式去遍历数据，将在其范围内的数据放入桶中。
这样做从结果来看应该是没有什么问题的，但是从性能上，就等于对数据列表遍历了5次，而使用data数据来识别聚合任务的方式只需要遍历1次。