iT邦幫忙

0

請問一個很笨的問題??遞回能做平行計算嗎?

  • 分享至 

  • xImage

其實小第不請楚這樣表達對不對
一個電腦叢集可以做大量的計算
可是現實中我們沒辦法把兩台爛電腦連接起來玩高需求的電腦遊戲=口=
離題了...

我今天聽到同學再討論一個數學公式
公式的作用是,將上次的計算結果當成下次的計算條件
ㄜ~一聽很直覺就是遞回
他們在討論的是
老師給的題目用電腦來計算都要算上好幾天...

我在旁邊聽到就在想,能不能用更快的方式求出結果呢??
當然先想到的就是連接多台電腦來計算
可是數學公式是用遞回來求解
感覺上還是只能用單一台電腦來計算

所以上來請教各位前輩有沒有更好的方式??
(除了換更好的電腦之外)

看更多先前的討論...收起先前的討論...
一尾 iT邦研究生 1 級 ‧ 2015-09-18 17:13:14 檢舉
所以我們應該拿數個pi 串起來玩一些大型3d game
毆飛
q00153提到:
老師給的題目用電腦來計算都要算上好幾天...


是什麼樣的題目
可否 PO 上來給個參考
疑惑
外獅佬 iT邦大師 1 級 ‧ 2015-09-19 00:02:30 檢舉
q00153提到:
上次的計算結果當成下次的計算條件

這樣...沒有上次的結果....如何有下次的條件?
根據樓主的敘述...每次的計算,都依賴上一次的計算
這樣的條件下...怎麼平行運算?疑惑
cmwang iT邦大師 1 級 ‧ 2015-09-19 06:26:48 檢舉
老笑話出現了,沒人可以讓10個女性同時懷孕1個月而生出1個小baby偷笑偷笑....
newkevin iT邦高手 1 級 ‧ 2015-09-19 09:05:38 檢舉
來亂的
算全世界動植物的預估生育率
平行給相同國家的數目的電腦算
在平行給相同地區的電腦算
然後以每月當做每次計算
參查 (各種基數 變數)
然後計算後的值
在查詢歷年的實際資料
做若干調整
然後結果再回給 次月當條件
這樣需要嗎
q00153 iT邦新手 3 級 ‧ 2015-09-19 09:28:16 檢舉
如果有這種技術
電腦公司應該會倒喔 XD
出更高階的遊戲只要多買幾台PI就可以了
哈哈
q00153 iT邦新手 3 級 ‧ 2015-09-19 09:30:23 檢舉
小弟有去問了
他說是跟"多階微分方程式"有關
看了他寫的論文...ㄜ~有字天書
請恕小弟才疏學淺
毆飛汗Orz
q00153 iT邦新手 3 級 ‧ 2015-09-19 09:33:52 檢舉
小弟想說自己孤陋寡聞
可能這裡有大大知道對於這種條件
怎麼提高它的運算速度
所以上來請教一下
臉紅

難道在現實中這真的是無解的一種題目嘛,只能仰賴更高時脈的CPU
嘆氣
q00153 iT邦新手 3 級 ‧ 2015-09-19 09:37:42 檢舉
小弟忽然想到一個畫面
十個培養皿培養人類十個部位
一個月成長後再將它們縫合起來
變成科學~~~怪怪人
冷
q00153 iT邦新手 3 級 ‧ 2015-09-19 09:40:33 檢舉
或許可以平行給各國家的電腦
統計愛愛率
可以當作計算十個月之後的出生率參數之一
臉紅
買套Maple來算
會不會比自己寫來得快
疑惑
總裁 iT邦好手 1 級 ‧ 2015-09-19 12:43:19 檢舉
笨問題....是只有笨蛋會回答的問題,還是只有笨蛋才會問的問題....疑惑
q00153 iT邦新手 3 級 ‧ 2015-09-19 12:56:02 檢舉
只有笨蛋才會問
因為小弟是笨蛋XD
q00153 iT邦新手 3 級 ‧ 2015-09-19 12:57:58 檢舉
ㄝ~~雖然應該會
可是這個性質是作業
恐怕會被教授當掉吧
哈哈哈哈哈哈
q00153提到:
多階微分方程式


這東西可以分解的啊

分解之後把片段交給不同的電腦跑,跑完之後再統整結果就好

雖然我不知道這個如何解,但基本上所有的方程式都能夠分解才對

有個東西叫做佇列還有個東西叫做暫存器
你可以把方程式分成幾個區段,丟到佇列,再把佇列的工作分散到每個電腦的暫存器
當工作處理完在拋到下個階段的佇列,這樣不就是分散處理了嗎

還有也可以利用顯卡輔助運算,高階顯卡的運算能力甚至比 cpu還要強
尤其是多顯卡smp 的時候,效能會更強的
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
4
wiseguy
iT邦超人 1 級 ‧ 2015-09-19 18:38:55
最佳解答

q00153提到:
將上次的計算結果當成下次的計算條件

這不一定是遞迴,通常稱為迭代。迭代可以用遞迴或單純迴圈來解。
要分散給多台做平行處理的,是每一次迭代所要處理的工作,而不是迭代這個處理程序。理解嗎?(打一個比方,你要把一塊大蛋糕吃掉,重點是把切分的每一塊小蛋糕吃掉,而不是切那塊蛋糕這個動作)
目前最夯的分散式處理,是 map-reduce,關鍵字去 google 一下吧!

okra iT邦研究生 3 級 ‧ 2015-09-19 19:50:32 檢舉

q00153提到:
可是現實中我們沒辦法把兩台爛電腦連接起來玩高需求的電腦遊戲

跑Hadoop硬體要夠力
兩個散戶股民合夥炒股可能賠更多
Orz

wiseguy iT邦超人 1 級 ‧ 2015-09-19 21:39:36 檢舉

okra提到:
兩個散戶股民合夥炒股

哈哈哈.....這不太適合分散式處理。因為各 node 不會各懷鬼胎,但人會。

2
wwx
iT邦好手 1 級 ‧ 2015-09-19 12:52:50

q00153提到:
公式的作用是,將上次的計算結果當成下次的計算條件

感覺就跟計算簡單的階層問題是類似的...
可以透過Judge測試自己的解題方式是否正確
http://140.119.163.240/ShowProblem?problemid=d038
只要能AC(表示通過)而不會TLE(表示執行超過時間限制),
代表執行速度可以接受,不然就是設計上有問題所以速度太慢了~

例如要算 100! 如果已經有 99! 的結果 只需算 99! * 100 一次
如果從頭算一般就是迴圈99次 (((100*99)*98)*97 ... )
當然也可以作成是(A*B)遞回99次...

如果問題是要計算 1萬次 1000!
那麼有10000台電腦 各自從頭算一次1000!
當然時間會比1台電腦一值重算1000!作10000次要快
假設10000台電腦速度一樣, 後者處理時間是前者的一萬倍

但是每個相同n!的結果不論計算幾次結果都是相同的,
如果已經有1000!計算過的結果記憶,其實只需直接回應即可就不用重算了
也就是只要有台電腦 將 1!, 2!, 3!, 4!, ... 1000!
都算過一次記憶起來後, 就可以隨時回應 1 < N < 1000 的 N! 結果不用重算

當然也可以用10台或更多台每次要重算的電腦來應付這樣的需求,
將N送進閒置的電腦計算N!來獲得結果
如果全部電腦都剛好在算較大的N!所以比較慢,
就等某台先算完當前問題後才能在處理新的問題了...

wiseguy iT邦超人 1 級 ‧ 2015-09-19 18:41:06 檢舉

wwx這個階乘例子應該是叫『動態規劃』,跟分散處理無關,也不需要用到分散處理。(用分散處理,反而是叫多台電腦做同樣的事了)

wwx iT邦好手 1 級 ‧ 2015-09-20 15:44:13 檢舉

我想,可能把很簡單的事真的寫的很簡單可能造成誤會...
多台電腦可以是2台專門針對1~20!,2台針對21~100!, 6台針對101~1000! ...
1~20!可以用int64處理即可,更大的數就須透過大數運算來處理,
由於較大的階層結果值後面都是一串0,又可以用不一樣的演算技巧來增加效率, ...
10倍數的階層也可以另有設計技巧來增加效率, ...
現在又為了突顯事情所以用很笨的處理方式來描述這樣的系統,
如何map reduce,需不需要分散,各有巧思囉~
當然聰明的人在這個範圍內用現代的電腦大致上不會去思考分散處理吧!
而分散處理也是要規劃,如果採用動態規劃又常會冠上智能處理的說法,
總之,依我所見,各種行為在名詞出現之前就已經存在,
而要不要設計到那麼厲害與問題簡單與否其實是兩回事,
至於要用什麼名詞來解釋哪個部分是另一種討論的範圍了...
以前述情境,如果一個case是要獲得(3的倍數階層值所有結果)
那麼多台電腦是『動態規劃』還是『分散處理』呢? 呵~

0
player
iT邦大師 1 級 ‧ 2015-09-22 18:12:29

如果你能做到迴圈扁平化
那麼遞回就有可能做平行計算
但是只是可能而已
重點還是看你的運算式拆得開嗎?

我要發表回答

立即登入回答