NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 22 题

有如下的一段程序：

1. a=1;
2. b=a;
3. d=-a;
4. e=a+d;
5. c=2*d;
6. f=b+e-d;
7. g=a*f+c;

现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC 执行其中的某几个语句，并可随时通过电缆与其他 PC 通讯，交换一些中间结果。假设每台 PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在[ ]单位时间内执行完毕。

注意：任意中间结果只有在某台 PC 上已经得到，才可以被其他 PC 引用。例如若语句 4 和 6 被分别分配到两台 PC 上执行，则因为语句 6 需要引用语句 4 的计算结果，语句 6 必须在语句 4 之后执行。

这道题考的是并行计算中的依赖关系分析，核心就是画出数据依赖图，找出最长的那条依赖链（关键路径）。拿到题先别急着算数，把每条语句依赖哪些前驱变量列出来，看看哪些能同时跑，哪些必须等前一个结果出来再动。

学生最容易犯的错误是只盯着代码里的行号顺序，以为第1行到第7行就是串行执行，忽略了变量之间的数据依赖。比如看到第2行b=a和第3行d=-a都依赖a，就以为它们可以并行，但没注意到第4行e=a+d其实同时依赖第1行的a和第3行的d，所以e必须在d之后。还有人会漏掉第6行f=b+e-d同时依赖b、e、d，误以为只要e算完就能算f，忘了b也要等a算完。这种漏依赖往往导致把关键路径算短了，比如误以为第4行和第5行都能和第6行并行，从而得出4单位时间的错误答案。

考点与命题视角

这道题属于C++程序设计与顺序结构的交叉考查。命题人专门挑了7条语句，每条都依赖前面的变量，目的是让学生跳出“按行号串行执行”的惯性思维，真正理解并行计算中的依赖关系。在NOIP普及组初赛里，这类题通常不会考复杂的调度算法，而是考你能否准确画出依赖图，并找出关键路径。

变量依赖关系梳理

我们先逐条看每条语句依赖哪些变量（只有变量在上一步已经算出，才能被这一步使用）： 1. a=1; —— 不依赖任何变量，是起点。 2. b=a; —— 依赖a。 3. d=-a; —— 依赖a。 4. e=a+d; —— 依赖a和d。 5. c=2*d; —— 依赖d。 6. f=b+e-d; —— 依赖b、e、d。 7. g=a*f+c; —— 依赖a、f、c。

注意：虽然第7行用了a，但a在第1行就已经算好了，所以第7行对a没有等待要求；它真正卡在第6行的f和第5行的c上。