20. 在研究并行计算的基本算法时,有以下简单模型问题:用计算机求
n个不同的数
的和
,计算开始前,
n个数存贮在
n台由网络连接的计算机中,每台机器存一个数.计算开始后,在一个单位时间内,每台机器至多到一台其他机器中读数据,并与自己原有数据相加得到新的数据,各台机器可同时完成上述工作.为了用尽可能少的单位时间,即可完成计算,方法可用下表表示:
机器号 | 初始时 | 第一单位时间 | 第二单位时间 | 第三单位时间 |
被读机号 | 结果 | 被读机号 | 结果 | 被读机号 | 结果 |
1 | | 2 | | | | | |
2 | | 1 | | | | | |
(1)当
时,至少需要多少个单位时间可完成计算?把你设计的方法填入下表:
机器号 | 初始时 | 第一单位时间 | 第二单位时间 | 第三单位时间 |
被读机号 | 结果 | 被读机号 | 结果 | 被读机号 | 结果 |
1 | | | | | | | |
2 | | | | | | | |
3 | | | | | | | |
4 | | | | | | | |
(2)当
时,要使所有机器都得到
,至少需要多少个单位时间可完成计算?(结论不要求证明)