Распараллеливание цикла

Из Википедии, бесплатной энциклопедии

Распараллеливание цикла — разновидность параллелизма в программировании, при котором цикл разбивается на задачи, выполняемые параллельно. Обычно возможность распараллеливания циклов возникает в программах, в которых данные хранятся в структурах с произвольным доступом. В отличие от последовательного алгоритма[en], который перебирал бы структуру данных и работал с индексами по одному, алгоритм с распараллеленным циклом будет использовать несколько потоков или процессов, которые работают с несколькими или всеми индексами одновременно. Такой параллелизм уменьшает общее время выполнения программы, обычно в соответствии с законом Амдала[1].

Описание[править | править код]

Для простых циклов, где каждая итерация независима от других, распараллеливание цикла может быть чрезвычайно параллельной задачей, поскольку для этого требуется только выделение отдельных процессов для обработки каждой итерации[2] . Однако большинство алгоритмов используют последовательные вычисления и не могут быть распараллелены сразу из-за внутренних зависимостей и, как следствие, возникающего состояния гонки. Последовательные алгоритмы обычно доступны для распараллеливания, однако требуют модификации, например, синхронизации[3]. Синхронизация может быть либо неявной, посредством обмена сообщениями, либо явной, посредством примитивов синхронизации, таких как семафоры.

Пример[править | править код]

Рассмотрим следующий код, работающий со списком L длины n: 

for (int i = 0; i < n; ++i) {      S1: L[i] += 10; }

При каждой итерации цикл берет значение из текущего индекса L и увеличивает его на 10. Если оператору S1 требуется время для выполнения T, то циклу требуется время для последовательного выполнения n * T без учёта времени, затрачиваемого конструкциями самого цикла. Теперь рассмотрим систему с p процессорами, где p > n. Если n потоков выполняются параллельно, время выполнения всех n шагов сокращается до T.

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

for (int i = 0; i < n; ++i) {      S1: L[i] = L[i-1] + 10; }

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

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Д.И. Черемисинов. Закон Амдала и границы параллельных вычислений (pdf). Шестая Международная научно-практическая конференция «BIG DATA and Advanced Analytics. BIG DATA и анализ высокого уровня» (2020). Дата обращения: 23 марта 2023. Архивировано 27 апреля 2022 года.
  2. ↑ В. В. Воеводин. Параллелизм в сложных программных комплексах (Почему сложно создавать эффективные прикладные пакеты) (pdf). Чебышевский сборник. Том 18 Выпуск 3 (2017). Дата обращения: 23 марта 2023. Архивировано 23 марта 2023 года.
  3. ↑ Р.К. Газизов, С.Ю. Лукащук, К.И. Михайленко. Параллельный полуявный алгоритм численного решения задач динамики жидкости (pdf). Высокопрозводительные параллельные вычисления на кластерных системах (2002). Дата обращения: 23 марта 2023. Архивировано 21 сентября 2018 года.
Источник — https://ru.wikipedia.org/w/index.php?title=Распараллеливание_цикла&oldid=134181327