Параллелизм на уровне цикла - Loop-level parallelism

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

Описание

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

пример

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

для (int i = 0; i 
Каждая итерация цикла берет значение из текущего индекса L, и увеличивает его на 10. Оператор if S1 берет Т время для выполнения, тогда цикл требует времени п * т выполнять последовательно, игнорируя время, затрачиваемое на конструкции цикла. Теперь рассмотрим систему с п процессоры, где p> n. Если п потоки выполняются параллельно, время выполнить все п шаги сводятся к Т.
Менее простые случаи приводят к противоречиям, т. Е. несериализуемый результаты. Рассмотрим следующий цикл, работающий с тем же списком L.
for (int i = 1; i 
Каждая итерация устанавливает текущий индекс равным предыдущему плюс десять. При последовательном запуске каждая итерация гарантирует, что предыдущая итерация уже будет иметь правильное значение. С несколькими потоками, планирование процессов и другие соображения не позволяют порядку выполнения гарантировать, что итерация будет выполняться только после того, как будет соблюдена ее зависимость. Это вполне может случиться раньше, что приведет к неожиданным результатам. Сериализуемость можно восстановить, добавив синхронизацию, чтобы сохранить зависимость от предыдущих итераций.
Зависимости в коде









В коде можно найти несколько типов зависимостей.[1][2]
Тип
Обозначение
Описание
Истинная (поток) зависимость
S1 -> Т S2
Истинная зависимость между S1 и S2 означает, что S1 записывает в место, которое позже считывает S2.
Анти-зависимость
S1 -> А S2
Анти-зависимость между S1 и S2 означает, что S1 читает из места, в которое позже записывается S2.
Выходная зависимость
S1 -> O S2
Выходная зависимость между S1 и S2 означает, что S1 и S2 записывают в одно и то же место.
Входная зависимость
S1 -> Я S2
Входная зависимость между S1 и S2 означает, что S1 и S2 читают из одного и того же места.
Чтобы сохранить последовательное поведение цикла при параллельном запуске, необходимо сохранить истинную зависимость. С антизависимостью и зависимостью от выпуска можно справиться, предоставив каждому процессу его собственную копию переменных (так называемая приватизация).[1]
Пример истинной зависимости
S1: int a, b; S2: a = 2; S3: b = a + 40;
S2 -> Т S3, что означает, что S2 имеет истинную зависимость от S3, потому что S2 записывает в переменную а, откуда S3 читает.
Пример антизависимости
S1: int a, b = 40; S2: a = b - 38; S3: b = -1;
S2 -> А S3, что означает, что S2 имеет анти-зависимость от S3, потому что S2 читает из переменной б до того, как S3 напишет ему.
Пример зависимости от выпуска
S1: int a, b = 40; S2: a = b - 38; S3: a = 2;
S2 -> O S3, что означает, что S2 имеет выходную зависимость от S3, потому что оба пишут в переменную а.
Пример зависимости от ввода
S1: int a, b, c = 2; S2: a = c - 1; S3: b = c + 1;
S2 -> I S3, что означает, что S2 имеет входную зависимость от S3, потому что S2 и S3 оба читают из переменной c.
Зависимость в петлях









Зависимость с переносом от петли и независимая от петли
Циклы могут иметь два типа зависимости:
Петлевая зависимость
Независимая от петли зависимость
В зависимости от цикла, циклы имеют зависимость между итерациями, но не имеют зависимости между итерациями. Каждую итерацию можно рассматривать как блок и выполнять параллельно без других усилий по синхронизации.
В следующем примере кода, который используется для обмена значениями двух массивов длиной n, существует независимая от цикла зависимость S1 -> T S3.
для (int я = 1; я <п; я ++) {S1: tmp = a [я]; S2: a [i] = b [i]; S3: b [i] = tmp;}
В зависимости с переносом цикла операторы в итерации цикла зависят от операторов в другой итерации цикла. Зависимость с циклическим переносом использует модифицированную версию обозначения зависимости, которую мы видели ранее.
Пример петлевой зависимости, где S1 [i] -> T S1 [i + 1], где я указывает текущую итерацию, а я + 1 указывает следующую итерацию.
for (int i = 1; i 
График зависимости с циклическим переносом
График зависимостей, переносимых по циклам, графически показывает зависимости, переносимые по циклам, между итерациями. Каждая итерация указана как узел на графе, а направленные ребра показывают истинную, антивирусную и выходную зависимости между каждой итерацией.
Типы









Существует множество методологий распараллеливания циклов.
РАСПРЕДЕЛЕННЫЙ ЦИКЛ
DOALL Параллельность
DOACROSS Параллелизм
HELIX [3]
DOPIPE Параллелизм
Каждая реализация немного отличается в том, как потоки синхронизируются, если это вообще происходит. Кроме того, параллельные задачи нужно каким-то образом сопоставить с процессом. Эти задачи могут быть распределены статически или динамически. Исследования показали, что балансировка нагрузки может быть лучше достигнута с помощью некоторых алгоритмов динамического распределения, чем когда выполняется статически.[4]
Процесс распараллеливания последовательной программы можно разбить на следующие отдельные шаги.[1] Каждое конкретное распараллеливание цикла ниже неявно выполняет их.
Тип
Описание
Разложение
Программа разбита на задачи, наименьшую возможную единицу согласования.
Присвоение
Задачи назначаются процессам.
Оркестровка
Доступ к данным, связь и синхронизация процессов.
Картография
Процессы привязаны к процессорам.
РАСПРЕДЕЛЕННАЯ петля
Когда цикл имеет зависимость с переносом цикла, один из способов его распараллеливания - разделить цикл на несколько разных циклов. Операторы, которые не зависят друг от друга, разделяются, так что эти распределенные циклы могут выполняться параллельно. Например, рассмотрим следующий код. 
для (int i = 1; i 
Цикл имеет петлевую зависимость S1 [i] -> T S1 [i + 1] но S2 и S1 не имеют независимой от цикла зависимости, поэтому мы можем переписать код следующим образом. 
loop1: for (int i = 1; i 
Обратите внимание, что теперь loop1 и loop2 могут выполняться параллельно. Вместо того, чтобы одна инструкция выполнялась параллельно с разными данными, как при параллелизме уровня данных, здесь разные циклы выполняют разные задачи с разными данными. Допустим, время выполнения S1 и S2 будет ${displaystyle Ts1}$ и ${displaystyle Ts2}$ тогда время выполнения для последовательной формы приведенного выше кода равно ${displaystyle n*(Ts1+Ts2)}$, Теперь, поскольку мы разделили два оператора и поместили их в два разных цикла, время выполнения составляет ${displaystyle n*Ts1+Ts2}$. Мы называем этот тип параллелизма параллелизмом функций или задач.
DOALL параллелизм
DOALL-параллелизм существует, когда операторы внутри цикла могут выполняться независимо (ситуации, когда нет зависимости, переносимой циклом).[1] Например, следующий код не читает из массива а, и не обновляет массивы до н.э. Никакие итерации не зависят от других итераций.
for (int i = 0; i 
Скажем, время одного выполнения S1 будет ${displaystyle Ts1}$ тогда время выполнения для последовательной формы приведенного выше кода равно ${displaystyle n*Ts1}$, Теперь, поскольку параллелизм DOALL существует, когда все итерации независимы, ускорение может быть достигнуто путем параллельного выполнения всех итераций, что дает нам время выполнения ${displaystyle Ts1}$, время, затрачиваемое на одну итерацию при последовательном выполнении.
В следующем примере с использованием упрощенного псевдокода показано, как можно распараллелить цикл для независимого выполнения каждой итерации.
begin_parallelism (); для (int i = 0; i 
DOACROSS параллелизм
DOACROSS Parallelism существует, когда итерации цикла распараллеливаются путем извлечения вычислений, которые могут выполняться независимо, и их одновременного выполнения.[5]
Синхронизация существует для обеспечения зависимости с переносом по петле.
Рассмотрим следующий синхронный цикл с зависимостью S1 [i] -> T S1 [i + 1].
for (int i = 1; i 
Каждая итерация цикла выполняет два действия
Рассчитать a [i - 1] + b [i] + 1
Присвойте значение а [я]
Расчет стоимости a [i - 1] + b [i] + 1, а затем выполнение присваивания можно разложить на две строки (операторы S1 и S2):
S1: int tmp = b [i] + 1; S2: a [i] = a [i - 1] + tmp;
Первая строка, int tmp = b [я] + 1;, не имеет петлевой зависимости. Затем цикл можно распараллелить, вычислив значение temp параллельно, а затем синхронизируя присвоение с а [я].
сообщение (0); для (int я = 1; я <п; я ++) {S1: int tmp = b [я] + 1; ждать (я - 1); S2: a [i] = a [i - 1] + tmp; post (i);}
Скажем, время выполнения S1 и S2 будет ${displaystyle Ts1}$ и ${displaystyle Ts2}$ тогда время выполнения для последовательной формы приведенного выше кода равно ${displaystyle n*(Ts1+Ts2)}$, Теперь, поскольку существует параллелизм DOACROSS, ускорение может быть достигнуто путем выполнения итераций конвейерным способом, что дает нам время выполнения ${displaystyle Ts1+n*Ts2}$.
DOPIPE параллелизм
DOPIPE Parallelism реализует конвейерный параллелизм для зависимости с переносом цикла, когда итерация цикла распределяется по нескольким синхронизированным циклам.[1] Цель DOPIPE - действовать как сборочная линия, где один этап запускается, как только для него будет доступно достаточно данных с предыдущего этапа.[6]
Рассмотрим следующий синхронный код с зависимостью S1 [i] -> T S1 [i + 1].
для (int i = 1; i 
S1 должен выполняться последовательно, но S2 не имеет зависящей от петли зависимости. S2 может выполняться параллельно с использованием DOALL Parallelism после последовательного выполнения всех вычислений, необходимых S1. Однако при этом ускорение будет ограничено. Лучшим подходом является распараллеливание таким образом, чтобы S2, соответствующий каждому S1, выполнялся, когда указанный S1 завершается.
Реализация конвейерного параллелизма приводит к следующему набору циклов, где второй цикл может выполняться для индекса, как только первый цикл завершит свой соответствующий индекс.
для (int i = 1; i 
Скажем, время выполнения S1 и S2 будет ${displaystyle Ts1}$ и ${displaystyle Ts2}$ тогда время выполнения для последовательной формы приведенного выше кода равно ${displaystyle n*(Ts1+Ts2)}$, Теперь, поскольку существует параллелизм DOPIPE, ускорение может быть достигнуто путем выполнения итераций конвейерным способом, что дает нам время выполнения ${displaystyle n*Ts1+(n/p)*Ts2}$, где p - количество параллельно подключенных процессоров.
Смотрите также









Параллелизм данных
Параллелизм задач
Параллелизм с использованием различных типов моделей памяти, таких как общий и распределен и Сообщение передается
использованная литература









 Солихин, Ян (2016). Основы параллельной архитектуры. Бока-Ратон, Флорида: CRC Press. ISBN  978-1-4822-1118-4.
 Гофф, Джина (1991). «Практическое тестирование зависимости». Материалы конференции ACM SIGPLAN 1991 по проектированию и реализации языков программирования - PLDI '91. С. 15–29. Дои:10.1145/113445.113448. ISBN  0897914287.
 Мерфи, Найл. «Обнаружение и использование параллелизма в циклах DOACROSS» (PDF). Кембриджский университет. Получено 10 сентября 2016.
 Кави, Кришна. «Распараллеливание циклов DOALL и DOACROSS - обзор». 
 Унникришнан, Прия (2012), «Практический подход к распараллеливанию DOACROSS», Euro-Par 2012 Параллельная обработка, Конспект лекций по информатике, 7484, стр. 219–231, Дои:10.1007/978-3-642-32820-6_23, ISBN  978-3-642-32819-0
 «DoPipe: эффективный подход к распараллеливанию моделирования» (PDF). Intel. Получено 13 сентября 2016.