Закон Амдала

Джин Амдал сформулировал в 1967 году закон, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений.

«В случае, когда программа разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длительного фрагмента».

Если p – доля последовательных (не распараллеливаемых) действий в программе, а (1-p) – доля распараллеливаемых действий в программы, которые могут быть равномерно формально распределены по n ядрам, ускорение S от параллельного выполнения программы будет

.

Закон определяет теоретически возможную верхнюю границу ускорения.

На рис. 33.2 представлены графики зависимости ускорения как функции числа ядер и доли последовательных (не распараллеливаемых) действий в выполняемой программе.

Рис. 33.2. Зависимость прироста производительности от числа ядер процессора

К примеру, даже в случае, когда 90% команд программы распараллеливается на несколько ядер, использование четырехъядерного процессора позволяет получить только трехкратный прирост производительности в сравнении с одноядерной структурой процессора.

Рассмотренный пример представляет собой идеальную ситуацию, но в реальности все несколько сложнее, тем не менее основная идея остается неизменной: использование многоядерных процессоров требует внесения кардинальных изменений в программное обеспечение.

Нужно отметить, что далеко не все приложения достаточно хорошо распараллеливаются. В то же время имеется ряд приложений, которые, наоборот, позволяют получить ощутимый прирост производительности от многоядерности. К ним относятся, например, программы финального рендеринга трехмерных сцен, программы для работы с видеомонтажем и обработки звука и многие другие. Отметим, что все новые версии популярных программ оптимизируются под многоядерную структуру процессоров, поскольку за ними будущее.

До сих пор, обсуждая прирост производительности, который можно получить при переходе от одноядерной структуры к многоядерной структуре, рассматривалась ситуация, когда n ядер выполняли n потоков только одного приложения. Тем не менее, многоядерные процессоры позволяют получить существенный прирост производительности при одновременной работе нескольких приложений. В идеальном случае каждое приложение может исполняться на отдельном ядре процессора независимо от других приложений.

Можно говорить о двух заметно разнящихся между собой тенденциях в процессе увеличения числа ядер. Одна носит название мультиядерность (multi-core). В этом случае предполагается, что ядра являются высокопроизводительными и их относительно немного (в процессорах для персональных компьютеров – 2, 4, 8; в процессорах для серверов – 8, 10, 12, 16, 18), и, согласно закону Мура, их количество может периодически увеличиваться. Основных недостатков два: первый — высокое энергопотребление, второй — высокая сложность микросхемы и, как следствие, более дорогая разработка и более низкий процент выхода готовой продукции.

Другой путь — многоядерность (many-core). В этом случае на кристалле располагается на порядок большее число ядер, но имеющих более простую структуру и потребляющих небольшие мощности. Сейчас количество ядер варьируется от 40 до 200, и если закон Мура будет выполняться и дальше, то можно ожидать появления процессоров с тысячами и десятками тысяч ядер. Очевидно, что увеличение в десятки и сотни раз числа ядер на одной подложке не является панацеей. Многоядерные процессоры, если все сводится к размещению большего числа классических простых ядер на одной подложке, нельзя воспринимать как решение всех проблем. Приложения, которые должны выполняться многими ядрами, чрезвычайно сложно программировать. Множество ядер могут быть эффективны только при выполнении приложений, обладающих естественной многопоточностью. Как справиться с грядущими проблемами пока неясно.