知识卡片

普通读书笔记卡 · 3669.a

工作与跨度给并行时间下界

理解等级:中级
  • T₁ 是全部计算在单处理器上的总工作量,T∞ 是无限处理器下仍必须串行经过的最长依赖链,T_P 是用 P 个处理器的运行时间;
  • P 个处理器每单位时间至多做 P 单位工作,因此 T_P≥T₁/P;
  • 再多处理器也不能突破关键依赖链,因此 T_P≥T∞。

所以 T_P≥max(T₁/P,T∞)。补充教学演示:若 T₁=100、T∞=30、P=4,工作律给出 25,跨度律给出 30,任何调度都不可能少于 30 个时间单位。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The work and span provide lower bounds on the running time TP of a task-parallel computation on P processors: In one step, an ideal parallel computer with P processors can do at most P units of work, and thus in TP

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[20000,25000))。 - 结论依据:原文给出工作律与跨度律;Art_P829–P830补全公式。数值代入为补充教学演示。 - 原始内容:The work and span provide lower bounds on the running time T P of a task-parallel computation on P processors: In one step, an ideal parallel computer with P processors can do at most P units of work, and thus in T P