任务集的计算规模未知的情形

　　对很多的问题，很多的任务事先就可以确定（在算法执行之前），而且它们之间相互独立，但它们的运行时间未知或者它们的运行时间差异很大。比如在并行计算机上对并行循环进行调度，在这个问题中，循环的每个迭代都是独立的，它们可以并行的执行，但是，不同迭代的运行时间的差异很大（比如由于某种条件语句）。一种可能的策略是将这个任务集（迭代集）随机的划分成p个部分，然后将每个部分分配给一个不同的处理器，显然，这种方案可能会带来负载的不平衡，因为每个任务所需要的时间是未知的。一个较好的办法是把所有的任务放到一个全局可以访问（指对所有的处理器而言）的任务池中，一旦一个处理器开始空闲（执行完了当前的任务），它可以从这个全局的任务池中取回新的任务。比如，对于并行循环的调度问题，我们可以把循环的所有迭代的循环变量值存放在一个共享的工作队列中（每个循环变量值对应着一个任务），如果一个处理器需要更多的任务，它可以访问这个队列（更好的做法是向这个队列的管理者--某个运行时函数申请），从队列中取出尚未完成的迭代的循环变量值，然后完成这些循环变量值对应的计算任务。

　　从上面的思路出发，人们开发了一些动态调度算法。最简单的称为自调度（self-scheduling）。这种算法中，每次处理器需要任务时，它直接从全局队列中得到下一个没有被分配的任务。这种一次分配给处理器一个任务的方式，对平衡计算来说是相当有效的，但全局共享队列本身却很容易成为系统的瓶颈（共享本身就通常意味着不佳的可扩展性），特别是当单个任务需要的计算时间很短的时候。

　　另外一种调度算法称为块调度（chunk scheduling）。这种调度方法是对自调度的一种简单的改进。当处理器需要新的任务时，它从全局任务队列中得到一组任务（而不是一个简单任务），任务组称为块（chunk）。在使用这种调度方法的时候，需要注意的是，每次取出的任务组中的任务量不能太大，否则有可能会导致负载不均衡（对于任务数量不够多的问题来说尤其如此）。为了在调度开销和负载平衡间找一个权衡点，可以采取下面的方法：随着程序的执行，不断的减少块的大小，也就是说，初始的块大小可以很大，当任务队列中所剩的任务数量逐渐减少时，同时也逐渐减少块的大小。根据如何降低块的大小，可以开发出一系列新的调度算法，最常见的方法分类方法是线性减少块的大小的方法和非线性减少块的大小的方法（比如块的大小成指数降低）。