高性能编程的三个目标：

尽量先实现一个最简单的解决方案，之后对其扩展以提高性能。

Balancing the workload

理想情况下，所有处理器在整个程序执行期间都忙于计算。

根据Amdahl定律，程序中的串行部分的比例对最大加速比有很大影响：

静态分配

上节lecture中提到了静态分配和动态分配，静态分配适用于哪种情况呢？

如果任务的执行时间是可预测的，那么静态分配时一种好办法，下图中，每个任务的执行时间都是大概相同的，每个处理器都执行三个任务。

如果任务的执行时间是可预测的，即使各任务的执行时间相差很大，这时也可以采用动态分配，下图中，虽然各任务执行时间不同，但是四个处理器的负载是均衡的。

这里还提到了半静态分配，这是一种介于静态分配和动态分配之间的方法。半静态分配在一个时间间隔后，对任务重新分配。

当任务执行时间不可预测时，程序会在运行时动态分配，下图展示了一个动态分配的例子，x数组内容是不可预测的，在运行时才能确定test_primality的时长。

上图中的程序有一个潜在的问题，如果各元素test_primality的执行时间都不长，那么counter就会存在严重的数据竞争问题。

一种解决方法是一次处理多个元素：

考虑通过共享工作队列的动态分配方法，可以先安排长任务，执行长任务的线程虽然完成的任务数较少，但工作量去其他线程大致相同。

之前所介绍的动态分配方法，都是基于单一共享工作队列，而当线程增加时，对工作队列同步的开销就会增加，因此引入分布式工作队列这一概念。下图中每个线程都有单独的工作队列。如果一个队列为空，线程可以从其他队列steal任务。

这里介绍了Cilk Plus中的两条语句：

Clik Plus运行时会维护线程池，当程序开始，线程池中的线程被创建：

现在假设Thread 0在执行foo时，Thread 1空闲了，那么Thread 1可以从Thread 0的工作队列steal bar。每个工作队列会放置线程接下来要做的任务。

Clik Plus采用child优先，线程在执行任务时，会把接下来的任务放进工作队列中，其他线程则可以steal这些任务。

从队列的哪一头steal？

每一个线程的工作队列都是双端的，本地线程对任务的push和pop是在队尾进行的，其他线程对任务的steal是在队头进行的，这也降低了不同线程对工作队列的竞争。

Clik Plus采用greedy policy实现sync同步，简单来说就是不要让线程空闲，只要任一工作队列还有任务，空闲线程就steal。