知识卡片

普通读书笔记卡 · 3671.a

贪心调度时间不超过双下界之和

理解等级:中级

令 T₁ 为总工作量、T∞ 为依赖图最长路径即跨度、T_P 为 P 个处理器上的运行时间。理想 P 核上,贪心调度只要有至少 P 个就绪任务便同时执行 P 个,称为完整步骤;就绪任务不足 P 个时称为不完整步骤。完整步骤每次完成 P 单位工作,数量至多 T₁/P。不完整步骤会执行全部就绪任务;剩余依赖图中任何最长链的首节点都必是就绪任务,因此该步后剩余跨度至少下降 1,不完整步骤至多有 T∞ 个。两类步骤相加得到 T_P≤T₁/P+T∞。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[25000,35000))。 - 结论依据:定理26.1证明完整/不完整步骤数量;原书公式图 `OEBPS/images/Art_P831.jpg`(式26.4)给出上界。 - 公式图核读:T_P ≤ T₁/P + T∞。此处的 `T_P` 是贪心调度在 P 核上的运行时间。 - 原始内容:On an ideal parallel computer with P processors, a greedy scheduler executes a task-parallel computation with work T 1 and span T ∞ in time