负载平衡技术

　　并行算法设计中使用的负载平衡技术可以分为两类：静态负载平衡与动态负载平衡。静态负载平衡技术在算法的实际执行前将计算任务分配给处理器；而动态负载平衡在算法的实际执行过程中将计算任务分配给处理器。能够采用静态负载平衡的算法通常都比较容易设计和实现，而需要采用动态负载平衡的算法则相对要复杂一些。

　　在算法中究竟采用静态负载平衡方法还是动态负载平衡方法可以从下面的两点来考虑：

　　☆ 计算中的任务是在算法执行过程中动态生成的，还是在算法设计的时候就已经给出的。比如对矩阵乘法来说，计算任务在算法执行前就可以静态的确定下来并分配给处理器；而快速排序算法中的子任务在程序执行的过程中才能完全的确定（下层的子任务由上层的子任务生成）。另外，前面讨论的15-puzzle问题也在执行过程中动态产生任务。对任务在算法执行前就可以确定的问题的任务图称为静态任务图，而对于任务在算法执行时产生的问题的任务图称为动态任务图。

　　☆ 另外的一个判断依据是任务规模，即解决任务所需要的时间。如果所有任务的规模都是已知的，那么可以用这个知识来有效的指导任务的分配，这时静态的方法就足够了。但有些问题的任务的计算规模是无法事先精确知道的，比如光线追踪算法和很多的搜索问题。这样的问题需要采用动态负载平衡的方法。

　　下面的图对上面的情形作了一个简单的小结：