我在理解 cilk 中多线程编程中贪婪调度的完整步骤和不完整步骤时遇到问题。
这是供参考的power-point演示文稿。
我理解的问题来自幻灯片# 32 - 37。
有人可以请特别解释一下如何
Complete step>=P threads ready to run
incomplete steps < p threads ready
感谢您的时间和帮助
问问题
498 次
1 回答
2
首先，请注意幻灯片中提到的“线程”并不像人们想象的那样是操作系统线程。他们对线程的定义在幻灯片 10 中给出："a maximal sequence of instructions not containing parallel control (spawn, sync, return)"。为避免进一步混淆，让我将其称为任务。
在幻灯片 32-35 上，圆圈代表一个任务（“线程”），边代表任务之间的依赖关系。你问的句子实际上是定义：当 P 或更多任务准备好运行时（因此所有 P 处理器都可以忙于做一些工作）这种情况称为完整步骤，而如果少于 P 个任务准备好，这种情况称为不完整步骤。为了简化分析，（隐式）假设所有任务都包含相同的工作（大小为 1）。
然后幻灯片 35 上的定理提供了贪婪调度程序运行程序所需的时间上限。由于所有的执行都是一系列完整和不完整的步骤，因此执行时间是所有步骤的总和。由于每个完整的步骤恰好执行 P 工作，因此完整步骤的数量不能大于 T1（总工作）除以 P。那么，每个不完整的步骤必须执行属于关键路径的任务（因为在每个步骤中至少有一个关键路径路径任务必须准备好，不完整的步骤执行所有准备好的任务）；所以不完整步骤的总数不超过跨度T_inf（关键路径长度）。因此，T1/P 和 T_inf 之和给出了执行时间的上限。
“调度理论”部分的其余幻灯片相当简单。
于 2011-06-20T19:05:31.713 回答