2002-北京卷理-20 解-并行计算与图论模型

本题导读

本题是一道结合现代计算机科学“并行计算”背景的创新应用题。核心意图在于考查学生将实际算法规则转化为数学模型的能力，利用指数增长模型（二分树）寻找完成海量数据相加所需的最少单位时间。

📌【题干】

Question

（2002年北京卷(理)） 在研究并行计算的基本算法时，有以下简单模型问题：用计算机求 $n$ 个不同的数 $v_1,v_2,\cdots ,v_n$ 的和 ${\sum }_{i=1}^n{v}_i=v_1+v_2+\cdots +v_n$，计算开始前，$n$ 个数贮存在 $n$ 台由网络连接的计算机中，每台机器存一个数.计算开始后，在一个单位时间内，每台机器至多到一台其他机器中读数据，并与自己原有数据相加得到新的数据，各台机器可同时完成上述工作.为了用尽可能少的单位时间，即可完成计算，方法可用下表表示（以 $n=2$ 为例）：

(1) 当 $n=4$ 时，至少需要多少个单位时间可完成计算？把你设计的方法填入下表：

(2) 当 $n=128$ 时，要使所有机器都得到 ${\sum }_{i=1}^n{v}_i$，至少需要多少个单位时间可完成计算？（结论不要求证明）

🔍【思路分析】

破题导航

1. 理解基本规则：

• 每个单位时间内，一台机器只能读一台其他机器的数据。
• 所有机器可以同时（并行）进行读取和相加。
• 目标是让所有机器都获得最终的全加和 $\sum v_i$。

2. 分析 $n=4$ 的最优策略：

• 第一步：让机器1和2互相读取，机器3和4互相读取。此时1、2拥有 $v_1+v_2$，3、4拥有 $v_3+v_4$。
• 第二步：让拥有前半部分和的机器（1或2）与拥有后半部分和的机器（3或4）进行交叉读取。

3. 推广至 $n=128$ 的一般规律：

• 每次有效的并行读取都可以使每台机器中包含的原始数据项数翻倍（$1\to 2\to 4\to 8\to \cdots \to 2^k$）。
• 建立指数方程 $2^k=n$，求解网络并行计算的最小级数 $k$。

✅【答案】

Success

(1) 至少需要 $2$ 个单位时间

(2) 至少需要 $7$ 个单位时间

✍【详细解析】

Abstract

📐 (1) 当 $n=4$ 时的方法设计

根据二分树并行归并策略，最少需要 2 个单位时间。方案设计填表如下：

机器号	初始时	第一单位时间 被读机号 | 结果	第二单位时间 被读机号 | 结果	第三单位时间 被读机号 | 结果
1	$v_1$	2 | $v_1+v_2$	3 | $v_1+v_2+v_3+v_4$	（空白）
2	$v_2$	1 | $v_2+v_1$	4 | $v_1+v_2+v_3+v_4$	（空白）
3	$v_3$	4 | $v_3+v_4$	1 | $v_1+v_2+v_3+v_4$	（空白）
4	$v_4$	3 | $v_4+v_3$	2 | $v_1+v_2+v_3+v_4$	（空白）

📐 (2) 当 $n=128$ 时的时间求解

根据（1）中的分析，由于每台机器在每个单位时间内至多能获取另一台机器的信息，这意味着每台机器中已累加的独立数据项的总个数，在最优状态下每经过一个单位时间最多只能翻一倍。

• 初始时（$t=0$）：每台机器有 $1$ 个数（$2^0$）；
• $t=1$ 后：每台机器最多有 $2$ 个数的和（$2^1$）；
• $t=2$ 后：每台机器最多有 $4$ 个数的和（$2^2$）；
• $\cdots \cdots$
• $t=k$ 后：每台机器最多有 $2^k$ 个数的和。

现要求所有机器都得到 $128$ 个数的总和，则必须满足： $2^k=128$ 因为 $128=2^7$，所以解得： $k=7$

即当 $n=128$ 时，至少需要 7 个单位时间。

答案： (1) 至少需要 2 个单位时间（表格见解析）； (2) 至少需要 7 个单位时间。

💡【考点归纳与避坑指南】

Danger

1. 核心考点：新定义应用题的规则提取；二分归并树形结构的代数特征；以 2 为底的对数运算。
2. 核心方法：分组配对法、指数模型放缩法。
3. 避坑指南：

• 串行计算思维误区：如果误用传统单机串行思维（即机器1先加2，再加3，再加4…），算出的时间将是 $n-1=127$ 个单位时间。本题的关键在于**“各台机器可同时完成上述工作”**这一并行性质，必须最大化利用每一轮的并行吞吐量。

📖【试题探源与推广】

Tip

1. 试题探源：本题以并行求和为背景，考查每轮数据交换使每台机器所含数据量翻倍的增长规律。
2. 结论推广：若共有 $n=2^k$ 个数进行并行求和，每轮交换后每台机器所含数据量翻倍，则使所有机器都得到总和所需的最少单位时间为 $k={\log }_{2}n$。本题中 ${\log }_{2}128=7$。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 04.01 指数与对数运算
• 25.01 程序框图与基本逻辑结构

类题演练 (Links)

• 1977-上海文-07 解-二次函数最小值
• 1977-内蒙古文-01 解-代数运算与三角
• 1977-内蒙古理-01 解-代数运算与极坐标