※ 引述《[email protected] (@++@)》之銘言： : ※ 引述《[email protected] (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