在研究并行計(jì)算的基本算法時(shí)，有以下簡(jiǎn)單模型問(wèn)題：用計(jì)算機(jī)求n個(gè)不同的數(shù)v₁，v₂，…，v_n的和=v₁＋v₂＋v₃＋…＋v_n．計(jì)算開始前，n個(gè)數(shù)存貯在n臺(tái)由網(wǎng)絡(luò)連接的計(jì)算機(jī)中，每臺(tái)機(jī)器存一個(gè)數(shù).計(jì)算開始后，在一個(gè)單位時(shí)間內(nèi)，每臺(tái)機(jī)器至多到一臺(tái)其他機(jī)器中讀數(shù)據(jù)，并與自己原有數(shù)據(jù)相加得到新的數(shù)據(jù)，各臺(tái)機(jī)器可同時(shí)完成上述工作.

為了用盡可能少的單位時(shí)間，使各臺(tái)機(jī)器都得到這n個(gè)數(shù)的和，需要設(shè)計(jì)一種讀和加的方法.比如n=2時(shí)，一個(gè)單位時(shí)間即可完成計(jì)算，方法可用下表表示：

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

（Ⅰ）當(dāng)n=4時(shí)，至少需要多少個(gè)單位時(shí)間可完成計(jì)算?

把你設(shè)計(jì)的方法填入下表

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

（Ⅱ）當(dāng)n=128時(shí)，要使所有機(jī)器都得到，至少需要多少個(gè)單位時(shí)間可完成計(jì)算?（結(jié)論不要求證明）

 

（20）在研究并行計(jì)算的基本算法時(shí)，有以下簡(jiǎn)單模型問(wèn)題：

用計(jì)算機(jī)求n個(gè)不同的數(shù)v₁，v₂，…，v_n的和=v₁+v₂+v₃+…+v_n.計(jì)算開始前，n個(gè)數(shù)存貯在n臺(tái)由網(wǎng)絡(luò)連接的計(jì)算機(jī)中，每臺(tái)機(jī)器存一個(gè)數(shù).計(jì)算開始后，在一個(gè)單位時(shí)間內(nèi)，每臺(tái)機(jī)器至多到一臺(tái)其他機(jī)器中讀數(shù)據(jù)，并與自己原有數(shù)據(jù)相加得到新的數(shù)據(jù)，各臺(tái)機(jī)器可同時(shí)完成上述工作.

為了用盡可能少的單位時(shí)間，使各臺(tái)機(jī)器都得到這n個(gè)數(shù)的和，需要設(shè)計(jì)一種讀和加的方法.比如n=2時(shí)，一個(gè)單位時(shí)間即可完成計(jì)算，方法可用下表表示：

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

 

（Ⅰ）當(dāng)n=4時(shí)，至少需要多少個(gè)單位時(shí)間可完成計(jì)算？

把你設(shè)計(jì)的方法填入下表

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

 

（Ⅱ）當(dāng)n=128時(shí)，要使所有機(jī)器都得到，至少需要多少個(gè)單位時(shí)間可完成計(jì)算？（結(jié)論不要求證明）

（20）在研究并行計(jì)算的基本算法時(shí)，有以下簡(jiǎn)單模型問(wèn)題：

 

用計(jì)算機(jī)求n個(gè)不同的數(shù)v₁，v₂，…，v_n的和=v₁+v₂+v₃+…+v_n.計(jì)算開始前，n個(gè)數(shù)存貯在n臺(tái)由網(wǎng)絡(luò)連接的計(jì)算機(jī)中，每臺(tái)機(jī)器存一個(gè)數(shù).計(jì)算開始后，在一個(gè)單位時(shí)間內(nèi)，每臺(tái)機(jī)器至多到一臺(tái)其他機(jī)器中讀數(shù)據(jù)，并與自己原有數(shù)據(jù)相加得到新的數(shù)據(jù)，各臺(tái)機(jī)器可同時(shí)完成上述工作.

為了用盡可能少的單位時(shí)間，使各臺(tái)機(jī)器都得到這n個(gè)數(shù)的和，需要設(shè)計(jì)一種讀和加的方法.比如n=2時(shí)，一個(gè)單位時(shí)間即可完成計(jì)算，方法可用下表表示：

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

（Ⅰ）當(dāng)n=4時(shí)，至少需要多少個(gè)單位時(shí)間可完成計(jì)算？

把你設(shè)計(jì)的方法填入下表

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

（Ⅱ）當(dāng)n=128時(shí)，要使所有機(jī)器都得到，至少需要多少個(gè)單位時(shí)間可完成計(jì)算？（結(jié)論不要求證明）