Gustafson 定律

Overview

Gustafson 定律(Gustafson’s law)阐述了数据并行带来的影响。Gustafson 定律是由 John L. Gustafson 在1988年提出的。是并行计算领域除了 Amdahl 定律之后又一个重要定律。

Introduction

Amdahl 定律有一个重要前提，就是处理的数据集大小是固定的，但是这在大数据计算的领域里，这个假设并不经常能达到，因为人们总是会为了在短时间内处理更多的数据，而为了达到目的，往往会在计算集群增加更多的处理器。

Gustafson 定律的提出，始于 Gustafson 实验室的一个实验，在一个拥有1024个处理器的计算机，观察到了超线性加速比，分别获得了1021x/1020x/1016x的加速比，如果按照 Amdahl 定律，1024核，早就在某处歇菜了，哪里来1000x以上的加速。

1021 for beam stress analysis using conjugate gradients, 1020 for baffled surface wave simulation using explicit finite differences, and 1016 for unstable fluid flow using flux-corrected transport.

现在看看这个下面这个图，可以理解一下，数据规模和处理器个数以及时间的关系。

image_1e1c9239s1t3dg0u113qleqv79.png-28.4kB

Summary

image_1e1c9scvp1irjat2gsl1l065spp.png-130.5kB

所以 Gustafson 的意思就是说，如果你代码里少点串行的部分，你的代码可以在多核环境下起飞（当然也不是没有限制）。

Reference

1. Reevaluating Amdahl’s Law
2. Gustafson’s law