知识卡片
贪心调度时间不超过双下界之和
令 T₁ 为总工作量、T∞ 为依赖图最长路径即跨度、T_P 为 P 个处理器上的运行时间。理想 P 核上,贪心调度只要有至少 P 个就绪任务便同时执行 P 个,称为完整步骤;就绪任务不足 P 个时称为不完整步骤。完整步骤每次完成 P 单位工作,数量至多 T₁/P。不完整步骤会执行全部就绪任务;剩余依赖图中任何最长链的首节点都必是就绪任务,因此该步后剩余跨度至少下降 1,不完整步骤至多有 T∞ 个。两类步骤相加得到 T_P≤T₁/P+T∞。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
On an ideal parallel computer with P processors, a greedy scheduler executes a task-parallel computation with work T1 and span T∞ in time
参考来源
- 位置:《算法导论(第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