Некоторые выводы из закона Густавсона-Барсиса

Статья является косметически измененным переводом этой записи

По счастливой случайности мне представилась возможность лично встретить Джона Густавсона, во время его посещени Остина в 2009 году. Заметка ниже -- некоторые мои мысли, возникшие после общения с ним.

Закон Густавсона -- это очень простое понятие, которое должны понимать все программисты параллельных систем и архитекторы многоядерных компьютеров. На мой взгляд, существуют две основы закона Густавсона. Ниже я опишу их своими словами.

Лемма 1. Некоторые нагрузки подобны газу: они расширяются для заполнения всей доступной вычислительной мощности.

Такие программы встречаются чаще, чем вы думаете. Я приведу несколько примеров:

1) Добыча BitCoin. Если добавить вычислительных мощностей, вы не закончите раньше. Вместо этого вы намайните больше монет.

2) Графика. Если добавить вычислительных мощностей, вы просто увеличите разрешение или количество деталей на экране.

3) Численные методы, например вычисление пи. Если добавить вычислительных мощностей, вы посчитаете большее количество цифр после запятой.

4) Погодные предсказания. Если увеличить количество компьютеров, вы получите более точные предсказания.

Подобное свойство так же наблюдается у некоторых последовательных алгоритмов.

Лемма 2. Когда размер задачи увеличивается, параллельная часть расширяется быстрее последовательной.

В качестве примера рассмотрим задачу умножения матриц. Время задания (инициализации) матрицы растет линейно (прим. переводчика: на самом деле квадратично)  с размером матрицы, в то время, как сам алгоритм требует O(n^3) времени.

Главный недостаток закона Густавсона в том, что подобно закону Амдала, он воспринимает мир бесконечно параллельным или полностью последовательным. Также, он не учитывает дополнительных расходов на создание/уничтожение потоков. Кроме того, различные типы последовательных участков, например критические секции, не берутся в расчет. Таким образом, закон Густавсона применим только если (а) к задаче применим закон Амдала и (б) к задаче применимы две леммы, сформулированные выше.

Что с этим могут поделать программисты? По-прежнему пытаться избавиться от последовательной части. Если вы не можете исключить последовательную часть, по крайней мере постарайтесь сделать так, чтобы последовательная часть росла медленнее параллельной при увеличении размеров входных данных. Более того, стремитесь сделать время в последовательной части константным и независящим от количества потоков (я понимаю, что в большинстве случаев это сделать невозможно)

Что делать архтекторам? Держать закон Густавсона в уме и смотреть за тем, чтобы задачи попадающие под его действие не получали штрафов при выполнении. В том числе следить, чтобы задачи, которые расширяются на много ядер не ограничивались системой памяти. (Я только и требую, что сбалансированную архитектуру)

如需更全面地了解编译器优化,请参阅优化注意事项