在研究并行計(jì)算的基本算法時(shí),有以下簡(jiǎn)單模型問(wèn)題:
用計(jì)算機(jī)求n個(gè)不同的數(shù)v
1,v
2,…,v
n的和
n |
|
i=1 |
vi=v1+v2+v3+…+vn.計(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ī)器都得到
n |
|
i=1 |
vi,至少需要多少個(gè)單位時(shí)間可完成計(jì)算?(結(jié)論不要求證明)