Re: [請益] 那些語言或程式用上 多核心 CPU
※ 引述《rightson.bbs@bbs.cs.nctu.edu.tw (@++@)》之銘言：
: ※ 引述《somi.bbs@ptt.cc (SoMiMi FaReRe)》之銘言：
: > 判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
: > 正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
: > 因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
: > 但已知 Halting Problem在Turing Machine上是undecidable
: > 所以(判斷程式花多少時間)也是 undecidable.
: 感謝補充
: 其實原po沒有講"錯"
: 只是敘述方式讓我覺得他重新定義了halting problem
: =======
: 這段非常怪，Compiler也許可以回答你每個指令要花多少週期做完，但無法回答你這程式
: 要花多少時間才能跑完，事實上，只要是圖靈機（Turing Machine，目前的機器皆是），
: 是無法回答這個問題的，因為這是所謂的Halting Problem.
===
多重程式, 多工, 多處理機, 平行計算, 多核心等等, 針對特定 AP 是可以讓
Compiler 來分析一個程式, 找出前後次序無關與相關的片段. 假設前後 A,B
兩片斷是相關的, 兩個 CPU 或 核心 C1, C2 被派來做這兩個片段, 因為 C2
要等 C1 做完 A, 才可以接續著做 B, 如果 C2 知道 C1 大概需做多久時間 T,
就可以離開一段時間 T 再回來檢查 C1 做完沒. 如果是這樣, 片段 A 讓 C1
做是可以事先依 A 的程式指令類別與數量估出所需 Cycle 數, 再依 C1 的
Clock 速率預估出所需時間, 就能決定大概該等多久. 只估片段而不涉及整個
大程式最終會不會(或該不該)停, 那還是可以估算的.
1.現在的 Compiler 似乎不做較長片段執行時間的估算. 但還是可以估, 未必
準確就是.
2.時延等候讓 cpu 或 core 去做別的事或都不做事, 就不必不停叫 CPU 去檢
試, 造成對 instruction pipeline 或 cache 的干擾, 固然是一種方法, 但
也不是很困難做不到的問題, 至少, 不會升級到 Halting Problem .
假如是這種狀況, 似乎事情還不是那麼難纏 ! 不過, Intel 因此被 AMD 拼過去,
那一定還有更大條的才是.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.6.234
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
