※ 引述《[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