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

Распараллеливание цикла — разновидность параллелизма в программировании, при котором цикл разбивается на задачи, выполняемые параллельно. Обычно возможность распараллеливания циклов возникает в программах, в которых данные хранятся в структурах с произвольным доступом. В отличие от последовательного алгоритма^[англ.], который перебирал бы структуру данных и работал с индексами по одному, алгоритм с распараллеленным циклом будет использовать несколько потоков или процессов, которые работают с несколькими или всеми индексами одновременно. Такой параллелизм уменьшает общее время выполнения программы, обычно в соответствии с законом Амдала^[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;
}

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

• Разделяемая память
• Обмен сообщениями