知识卡片

普通读书笔记卡 · 3669.a.1.b

随机并行加速比取期望时间之比

理解等级:高级

原书问题26-6(b)提出以 E[T₁]/E[Tₚ] 而非 E[T₁/Tₚ] 定义随机算法加速比,要求读者论证。

按题设:1% 时 T₁=10⁴、T₁₀₀₀₀=1;其余99% 时两者均为10⁹。

前者约1,后者100.99;罕见的极高逐次加速会放大后者。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第26章 并行算法 · 查看原书依据

      b. Consider a randomized parallel algorithm for which 1% of the time, T1 = 104 and T10,000 = 1, but for the remaining 99% of the time, T1 = T10,000 = 109. Argue that the speedup of a randomized parallel algorithm should be defined as E[T1]/E[TP], rather than E[T1/TP].

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[90000,95000))。 - 结论依据:问题26-6(b)的待证命题及题中两种运行情形;数值比较是依题设自行推导,原书没有在此给出证明。E[T₁]=990000100,E[T₁₀₀₀₀]=990000000.01,所以 E[T₁]/E[T₁₀₀₀₀]≈1.000000101;E[T₁/T₁₀₀₀₀]=100.99。 - 原始内容:b. Consider a randomized parallel algorithm for which 1% of the time, T 1 = 10 4 and T 10,000 = 1, but for the remaining 99% of the time, T 1 = T 10,000 = 10 9 . Argue that the speedup of a randomized parallel algorithm should be defined as E [ T 1 ]/ E [ T P ], rather than E [ T 1 / T P ].