Программное обеспечение и параллельная революция (Часть 2)

Херб Саттер (Herb Sutter) и Джэймс Лэрус (James Larus), Microsoft.


Часть 2. Параллелизм

Программные модели

Сегодня вы можете реализовать параллелизм различными способами, каждый из которых подходит для решения своего класса задач. Во многих случаях крайне трудно, без тщательного анализа и проектирования, заранее определить какая модель подходит для решения конкретной задачи, и еще сложнее совместить несколько моделей, если ваше приложение не вписывается в рамки какой то одной парадигмы.
Все эти модели параллельного программирования различаются в основном по двум направлениям: по степени детализации параллельных операций и по степени связности задач. Эти направления задают своеобразные оси пространства, на котором каждой модели соответствует своя точка. Давайте рассмотрим их.
Операции, исполняемые параллельно могут варьироваться от отдельных инструкций, таких как сложение или умножение, до сложных программ, которые могут исполняться часы или дни. Очевидно, что для мелких операций накладные расходы параллельной инфраструктуры очень важны, например, параллельное исполнение инструкций обычно требует наличия аппаратной поддержки. Многоядерные процессоры снижают расходы на взаимодействие и синхронизацию по сравнению с обычными многопроцессорными системами, которые также способны снизить бремя накладных расходов для малых порций кода. В целом, более мелкие параллельные задачи требуют большего внимания в вопросах разделения задач, а также их синхронизации и коммуникации.
Другое измерение это степень связности в области синхронизации и взаимодействия между операциями. Идеал - нулевая связность: операции выполняются полностью независимо и производят независимые результаты. В этом случае операции могут выполняться в произвольном порядке, не требуют синхронизации и взаимодействия, легко программируются без угрозы возникновения «гонок данных» (data races). Такое положение дел встречается крайне редко, и большинство параллельных программ разделяют свои данные между операциями. Сложность обеспечения правильной и эффективной работы возрастает, по мере того, как операции становятся более разнообразными. В простейшем случае исполняется один и тот же код в каждой операции. Этот тип параллелизма часто называют регулярным, и он может быть достаточно просто проанализирован. Более сложен нерегулярный параллелизм, при котором операции разнообразны, а шаблоны реализации гораздо более сложны для понимания.

Независимый параллелизм.

Пожалуй, наиболее простая модель параллельных вычислений, это независимый параллелизм (в англоязычной среде для нее существует термин “embarrassingly parallel tasks”), в которой одна или несколько операций независимо применяются к каждому элементу в коллекции данных.
Параллельная обработка гранулярных данных основана на независимости операций выполняемых параллельно. Они не должны разделять исходные данные и результаты и могут выполняться без общей координации. Например:
double A[100][100];
…A = A * 2;
умножение каждого элемента массива размерностью 100 х 100 на 2 и сохранение результатов в этом же массиве. Каждое из 10000 умножений может быть выполнено независимо друг от друга. Это вероятно будет даже «слишком параллельно» для большинства компьютеров, более практичный подход состоит в разделении матрицы на блоки размерностью n x m и выполнение операций над этими блоками параллельно.
На другом конце рассматриваемой нами оси детализации, располагаются приложения, такие как поисковики, которые разделяют одну большую базу данных только для чтения, поэтому параллельная обработка поисковых запросов не требует взаимной координации. Другой класс приложений с независимым параллелизмом, это приложения имитационного моделирования, которые требуют многократных прогонов на огромных массивах вариантов входных параметров.

Регулярный параллелизм

Следующим шагом после независимого параллелизма будет выполнение повторяющихся операций над коллекцией данных при том, что вычисления взаимно зависимы. Операция над определенной порцией данных зависит от другой операции, если существует определенная связь или необходимость синхронизации между двумя операциями.
Например, рассмотрим трафаретное вычисление (stencil computation) которое замещает значение каждого элемента двумерного массива средним арифметическим значений четырех соседних элементов:
A[i, j] = (A[i-1, j] + A[i, j-1] + A[i+1, j] + A[i, j+1]) / 4;
Такой алгоритм требует тщательной координации для обеспечения того, что значение массива будет прочитано его соседями, до того как оно будет замещено средним арифметическим. Если нет ограничений по размеру, то значения могут быть помещены в новый массив. В целом, другие, более структурированные стратегии вычислений, такие как диагональное рассечение массива (traversing the array in a diagonal wavefront) дадут такой же результат, но с лучшими показателями кэширования и меньшим потреблением памяти.
Программы с регулярным параллелизмом могут потребовать тщательной синхронизации и оркестрации для получения корректных результатов, однако в отличие от обобщенного параллелизма, код таких операций может быть проанализирован на предмет того, как его можно исполнить параллельно и какие данные он будет разделять. Это преимущество часто оказывается призрачным, потому что программный анализ не является точной дисциплиной, и компиляторы не способны разобрать и реструктуризировать достаточно сложные программы.
На другом конце оси детализации расположены вычисления на web сайтах, которые являются независимыми за исключением обращений к общей базе данных. Вычисления выполняются параллельно без существенной координации, которая сосредоточена в основном в рамках SQL транзакций. Таким образом, обеспечивается согласованный конкурентный доступ к разделяемым данным в базе.

Неструктурированный параллелизм

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