Question

在研究并行計(jì)算的基本算法時，有以下簡單模型問題：
用計(jì)算機(jī)求n個不同的數(shù)v₁，v₂，…，v_n的和

n

i=1

vi=v1+v2+v3+…+vn．計(jì)算開始前，n個數(shù)存貯在n臺由網(wǎng)絡(luò)連接的計(jì)算機(jī)中，每臺機(jī)器存一個數(shù)，計(jì)算開始后，在一個單位時間內(nèi)，每臺機(jī)器至多到一臺其他機(jī)器中讀數(shù)據(jù)，并與自己原有數(shù)據(jù)相加得到新的數(shù)據(jù)，各臺機(jī)器可同時完成上述工作．為了用盡可能少的單位時間，使各臺機(jī)器都得到這n個數(shù)的和，需要設(shè)計(jì)一種讀和加的方法．比如n=2時，一個單位時間即可完成計(jì)算，方法可用下表表示：

機(jī)器號	初始時	第一單位時間		第二單位時間		第三單位時間
		被讀機(jī)號	結(jié)  果	被讀機(jī)號	結(jié)  果	被讀機(jī)號	結(jié)  果
1	v1	2	v1+v2
2	v2	1	v2+v1

（Ⅰ）當(dāng)n=4時，至少需要多少個單位時間可完成計(jì)算？把你設(shè)計(jì)的方法填入下表

機(jī)器號	初始時	第一單位時間		第二單位時間		第三單位時間
		被讀機(jī)號	結(jié)  果	被讀機(jī)號	結(jié)  果	被讀機(jī)號	結(jié)  果
1	v1
2	v2
3	v3
4	v4

（Ⅱ）當(dāng)n=128時，要使所有機(jī)器都得到

n

i=1

vi，至少需要多少個單位時間可完成計(jì)算？（結(jié)論不要求證明）

Answer 1

（Ⅰ）當(dāng)n=4時，只用2個單位時間即可完成計(jì)算．方法之一如下：

機(jī)器號	初始時	第一單位時間		第二單位時間		第三單位時間
		被讀機(jī)號	結(jié) 果	被讀機(jī)號	結(jié) 果	被讀機(jī)號	結(jié) 果
1	v1	2	v1+v2	3	v1+v2+v3+v4
2	v2	1	v2+v1	4	v2+v1+v4+v3
3	v3	4	v3+v4	1	v3+v4+v1+v2
4	v4	3	v4+v3	2	v4+v3+v2+v1

（Ⅱ）當(dāng)n=128=2⁷時，至少需要7個單位時間才能完成計(jì)算．