本文主要是这篇论文的一些观点摘录。
摘要
本论文研究了在并行计算机上调度完全严格（结构良好）的多线程计算问题。work stealing 是一种流行且实用的调度此类 MIMD 风格计算的方法。通信约束证明了 folk wisdom ，work-stealing 调度比工作共享调度具有更强的通信效率。
1. 介绍
调度算法必须确保有足够的线程同时处于活跃状态，以保证处理器处于繁忙状态。
确保并发活跃线程的数量保持在合理的范围内，这样可以保证内存需求不会太大。
调度器还应该尽可能维护同一处理器上的相关线程，以便最小化他们之间的通信。
两种调度模式来解决调度多线程计算的问题。
每当处理器生成新线程时，调度器尝试将其中一些迁移到其他进程，希望将工作分配给未充分利用的处理器。
在工作窃取中，未充分利用的处理器采取主动:它们试图从其他处理器窃取“线程”。
再次阐述这篇论文要干什么事情，提出并分析一个用于调度完全严格的(结构良好的)多线程计算的工作窃取算法。
本篇论文主要贡献：一个完全严格的多线程计算的随机工作窃取调度算法。它在时间、空间和通信方面被证明是有效的。
多线程计算的图论模型，为分析调度器提供了理论基础。
中央队列的简单调度算法。
使用边界和延迟序列参数来分析工作窃取算法的执行时间和通信成本。
2. 一个多线程计算的模型
这些指令由依赖关系边连接，这些依赖关系边提供了一个部分排序，其中的指令必须在其他指令之前执行。
activation frame 线程的指令可以使用它来存储他们所计算的值。
决定 P-处理器并行计算机的哪个处理器在每一步执行哪条指令。
依赖特定的多线程计算和P 处理器的数量。
spawn 衍生，在多线程处理中很高频的一个词。
执行计划通常会考虑除了继续和衍生边缘之外的其他依赖关系。
为了执行顺序，可能需要其他的依赖边（也称为连接边）。
首先假设每个指令最多有一个固定数量的连接边。
第二个假设是没有连接边在衍生之后立即进入指令。
这个假设意味着当父线程生成子线程时，父线程不能立即停止。
它继续准备执行至少一条指令。
在给定时间内执行计算所使用的空间是当时所有活动线程所使用的所有帧的总大小，而执行计算所使用的总空间是执行过程中该值的最大值。
3. Busy-Leaves 属性
Busy-Leaves 算法是工作窃取算法的基础。
如果池中有足够多的就绪线程来满足所有空闲处理器，那么每个处理器都有一个就绪线程来处理。
busy-leaves 算法计算出的调度保持了 busy-leaves 属性：在执行的每一个时间步，派生子树中的每一个叶子都有一个处理器。
4. 一个随机的工作窃取算法
未完待续。。。
看了前面3章准备的 Slides
阅读起来确实比较吃力，所以在这里先来占个坑，看看有没有人有兴趣的，可以相互交流（指导一下）。