在研究并行计算的基本算法时，有以下简单模型问题：

在研究并行计算的基本算法时，有以下简单模型问题：
用计算机求n个不同的数v 1 ，v 2 ，…，v n 的和
n




i=1
v i = v 1 + v 2 + v 3 +…+ v n ．计算开始前，n个数存贮在n台由网络连接的计算机中，每台机器存一个数，计算开始后，在一个单位时间内，每台机器至多到一台其他机器中读数据，并与自己原有数据相加得到新的数据，各台机器可同时完成上述工作．为了用尽可能少的单位时间，使各台机器都得到这n个数的和，需要设计一种读和加的方法．比如n=2时，一个单位时间即可完成计算，方法可用下表表示：
机器号 初始时 第一单位时间 第二单位时间 第三单位时间
被读机号 结 果 被读机号 结 果 被读机号 结 果
1 v 1 2 v 1 +v 2
2 v 2 1 v 2 +v 1
（Ⅰ）当n=4时，至少需要多少个单位时间可完成计算？把你设计的方法填入下表
机器号 初始时 第一单位时间 第二单位时间 第三单位时间
被读机号 结 果 被读机号 结 果 被读机号 结 果
1 v 1
2 v 2
3 v 3
4 v 4
（Ⅱ）当n=128时，要使所有机器都得到
n




i=1
v i ，至少需要多少个单位时间可完成计算？（结论不要求证明）
lena1210 1年前 已收到1个回答 举报
赞

冰吻百合 幼苗

共回答了12个问题采纳率：91.7% 举报

（Ⅰ）当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 2 +v 1 +v 4 +v 3
3 v 3 4 v 3 +v 4 1 v 3 +v 4 +v 1 +v 2
4 v 4 3 v 4 +v 3 2 v 4 +v 3 +v 2 +v 1 （Ⅱ）当n=128=2 7 时，至少需要7个单位时间才能完成计算．

1年前

4
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 1.060 s. - webmaster@yulucn.com