动态产生的任务图

　　更为一般的情形是，工作中的任务是在程序运行的过程中动态产生的，也就是说，这个算法具有一个动态的任务图。在任意给定的时刻，都有可以执行的任务，也有需要等待其它任务执行完以后才能开始执行的任务（任务之间存在复杂的依赖关系）。一个可执行任务的完成会导致一系列新任务的产生，其中有些可以马上执行，而有些必须等待其它的一些相关的任务完成后才能开始。当算法具有动态任务图时，一个负载平衡策略必须保证那些任务繁重的处理器上任务可以有效的转移到那些相对空闲的处理器。动态任务图的最优负载平衡方案要比静态任务图更为一般化，因此，这也是一个NP完全问题。对这类问题，通常会采用一些启发式的算法来得到一个较优的负载平衡方案。对动态任务图，一种简单的情形是，所有新产生的任务和其他的任务没有依赖关系，一旦它们产生，他们就可以立即被执行，这样，在任意时刻，都会有一组可以执行的任务，对这些任务中的任务进行执行，可以产生新的可执行任务。这种类型的计算的重要特征是总有可以并行执行的任务。但为了达到负载平衡，我们仍然需要小心的对任务进行分配。这样的计算的例子包括启发树和图搜索问题。

　　对这类问题，一种动态负载平衡的策略是采用生产者--消费者模型。为了可以采用这种模型，我们需要对计算进行重新构造，这样，一些处理器产生任务（生产者），而一些处理器来完成这些任务（消费者）。任务在生产者和消费者之间的传递可以由生产者发起，也可以由消费者发起。由生产者发起的情况下，一旦生产者产生了新的任务，它把这个任务发送给一个消费者；而在消费者发起的情况下，消费者需要新的任务时，他主动从一个生产者那里申请新的任务（这很象上面的全局任务池的模型）。这两种模型中，生产者和消费者角色的确定可以采用静态的方法，也可以采用动态的方法。静态的方法中，每个生产者都会事先为它分配几个固定的消费者处理器，而对动态的方法，每个生产者可以给任何的消费者处理器发送任务。相对来说，动态的方法可能会得到更好的负载平衡性，因为对静态的方法而言，有可能会出现这样的情形：消费者已经完成了自己手头的任务，而与它相关的生产者却没有办法及时的产生足够数量任务。另外一个需要关心的问题是系统中生产者与消费者数量的确定，如果相对来说，生产者的数目小于消费者，那么任务的传输问题很可能会造成瓶颈（因为没有足够的任务产生，或者向每个生产者申请任务的消费者过多，造成生产者的带宽不够），对于那些消费者需要频繁的向生产者申请任务的问题来说，这个问题可能会表现的更加严重。如果每个任务的计算量为M，生产者需要△的时间将它传送给消费者，那么一个生产者最多能搭配M/△个消费者。解决这个瓶颈的一个办法是提高M（也就是提高每次分配的任务的计算量，称为任务的粒度，granularity）,但这样做的潜在的危险是它可能会导致系统的负载不均衡。当系统中只有一个生产者的时候，这种模型通常被称为管理者--工作者模型（manager-worker）或者是主--仆模型(master-slave)。

　　另外一个可以完全解决这个瓶颈的方案是给处理器更大的自由，也就是说，处理器不再固定是生产者或者消费者，每个处理器都可以发送工作，也可以接受工作，和上面的方案一样，这种任务接收的发起者可以是生产者，也可以是消费者。