Параллелизм на уровне цикла

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

Описание [ править ]

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

Пример [ править ]

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

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

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

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

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

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

Зависимости в коде [ править ]

В коде можно найти несколько типов зависимостей. ^[1]^[2]

Тип	Обозначения	Описание
Истинная (поточная) зависимость	`S1 ->T S2`	Истинная зависимость между S1 и S2 означает, что S1 записывает в место, которое позже будет прочитано S2.
Антизависимость	`S1 ->A S2`	Антизависимость между S1 и S2 означает, что S1 читает из места, куда позже запишет S2.
Выходная зависимость	`S1 ->O S2`	Зависимость вывода между S1 и S2 означает, что S1 и S2 записывают в одно и то же место.
Входная зависимость	`S1 ->I S2`	Входная зависимость между S1 и S2 означает, что S1 и S2 считывают из одного и того же места.

Чтобы сохранить последовательное поведение цикла при параллельном запуске, необходимо сохранить истинную зависимость. С антизависимостью и зависимостью от выпуска можно справиться, предоставив каждому процессу собственную копию переменных (так называемая приватизация). ^[1]

Пример истинной зависимости [ править ]

S1: int a, b;
S2: a = 2;
S3: b = a + 40;

S2 ->T S3, что означает, что S2 действительно зависит от S3, поскольку S2 записывает в переменную a, из которого читает S3.

Пример борьбы с зависимостью [ править ]

S1: int a, b = 40;
S2: a = b - 38;
S3: b = -1;

S2 ->A S3, что означает, что S2 не зависит от S3, поскольку S2 читает переменную b прежде чем S3 напишет в него.

Пример зависимости от вывода [ править ]

S1: int a, b = 40;
S2: a = b - 38;
S3: a = 2;

S2 ->O S3, что означает, что S2 имеет выходную зависимость от S3, поскольку оба записывают в переменную a.

Пример зависимости от ввода [ править ]

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.

for (int i = 1; i < n; ++i) {
    S1: tmp = a[i];
    S2: a[i] = b[i];
    S3: b[i] = tmp;
}

В зависимости, переносимой циклом, операторы в итерации цикла зависят от операторов в другой итерации цикла. Зависимость, переносимая в цикле, использует модифицированную версию обозначения зависимости, рассмотренную ранее.

Пример циклической зависимости, где S1[i] ->T S1[i + 1], где i указывает текущую итерацию, а i + 1 указывает на следующую итерацию.

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

График зависимости, передаваемый по циклу [ править ]

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

Типы [ править ]

Существует множество методологий распараллеливания циклов.

РАСПРЕДЕЛЕННЫЙ цикл
ДОЛЛ Параллелизм
ДОАКРОСС Параллелизм
СПИРАЛЬ ^[3]
ДОПИП Параллельность

Каждая реализация немного различается в том, как синхронизируются потоки, если вообще синхронизируется. Кроме того, параллельные задачи должны каким-то образом быть сопоставлены с процессом. Эти задачи могут распределяться статически или динамически. Исследования показали, что балансировку нагрузки можно лучше достичь с помощью некоторых алгоритмов динамического распределения, чем при статическом распределении. ^[4]

Процесс распараллеливания последовательной программы можно разбить на следующие отдельные этапы. ^[1] Каждое конкретное распараллеливание цикла, приведенное ниже, неявно выполняет их.

Тип	Описание
Разложение	Программа разбита на задачи — наименьшую единицу параллелизма, которую можно использовать.
Назначение	Задачи назначаются процессам.
оркестровка	Доступ к данным, связь и синхронизация процессов.
Картирование	Процессы привязаны к процессорам.

РАСПРЕДЕЛЕННЫЙ цикл [ править ]

Если цикл имеет зависимость, переносимую циклом, один из способов его распараллеливания — разделить цикл на несколько разных циклов. Операторы, которые не зависят друг от друга, разделены, чтобы эти распределенные циклы могли выполняться параллельно. Например, рассмотрим следующий код.

for (int i = 1; i < n; ++i) {
    S1: a[i] = a[i-1] + b[i];
    S2: c[i] += d[i];
}

Цикл имеет зависимость, переносимую циклом S1[i] ->T S1[i+1] но S2 и S1 не имеют зависимости, независимой от цикла, поэтому мы можем переписать код следующим образом.

loop1: for (int i = 1; i < n; ++i) {
    S1: a[i] = a[i-1] + b[i];
}
loop2: for (int i = 1; i < n; ++i) {
    S2: c[i] += d[i];
}

Обратите внимание, что теперь цикл 1 и цикл 2 могут выполняться параллельно. Вместо того, чтобы одна инструкция выполнялась параллельно с разными данными, как при параллелизме на уровне данных, здесь разные циклы выполняют разные задачи с разными данными. Допустим, время выполнения S1 и S2 будет $T_{S_{1}}$ и $T_{S_{2}}$ тогда время выполнения последовательной формы приведенного выше кода равно $n*(T_{S_{1}}+T_{S_{2}})$ , Теперь, поскольку мы разделили два оператора и поместили их в два разных цикла, время выполнения составит $n*T_{S_{1}}+T_{S_{2}}$ . Мы называем этот тип параллелизма либо параллелизмом функций, либо параллелизмом задач.

DOALL-параллелизм [ править ]

Параллелизм DOALL существует, когда операторы внутри цикла могут выполняться независимо (ситуации, когда нет зависимости, переносимой в цикле). ^[1] Например, следующий код не читает из массива aи не обновляет массивы b, c. Ни одна итерация не зависит от какой-либо другой итерации.

for (int i = 0; i < n; ++i) {
    S1: a[i] = b[i] + c[i];
}

Допустим, время одного выполнения S1 будет $T_{S_{1}}$ тогда время выполнения последовательной формы приведенного выше кода равно $n*T_{S_{1}}$ , Теперь, поскольку параллелизм DOALL существует, когда все итерации независимы, ускорения можно достичь за счет параллельного выполнения всех итераций, что дает нам время выполнения $T_{S_{1}}$ , что представляет собой время, необходимое для одной итерации при последовательном выполнении.

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

begin_parallelism();
for (int i = 0; i < n; ++i) {
    S1: a[i] = b[i] + c[i];
    end_parallelism();
}
block();

DOACROSS-параллелизм [ править ]

DOACROSS Параллелизм существует, когда итерации цикла распараллеливаются путем извлечения вычислений, которые могут выполняться независимо, и их одновременного выполнения. ^[5]

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

Рассмотрим следующий синхронный цикл с зависимостью S1[i] ->T S1[i+1].

for (int i = 1; i < n; ++i) {
    a[i] = a[i-1] + b[i] + 1;
}

Каждая итерация цикла выполняет два действия.

Рассчитать a[i-1] + b[i] + 1
Присвойте значение a[i]

Расчет стоимости a[i-1] + b[i] + 1, и тогда выполнение присваивания можно разложить на две строки (операторы S1 и S2):

S1: int tmp = b[i] + 1;
S2: a[i] = a[i-1] + tmp;

Первая линия, int tmp = b[i] + 1;, не имеет зависимости от цикла. Затем цикл можно распараллелить, параллельно вычислив значение temp, а затем синхронизировав назначение с a[i].

post(0);
for (int i = 1; i < n; ++i) {

    S1: int tmp = b[i] + 1;
    wait(i-1);

    S2: a[i] = a[i-1] + tmp;
    post(i);
}

Допустим, время выполнения S1 и S2 будет $T_{S_{1}}$ и $T_{S_{2}}$ тогда время выполнения последовательной формы приведенного выше кода равно $n*(T_{S_{1}}+T_{S_{2}})$ , Теперь, поскольку существует параллелизм DOACROSS, ускорения можно достичь за счет выполнения итераций конвейерным способом, что дает нам время выполнения $T_{S_{1}}+n*T_{S_{2}}$ .

DOPIPE-параллелизм [ править ]

DOPIPE Parallelism реализует конвейерный параллелизм для зависимости, переносимой циклом, где итерация цикла распределяется по нескольким синхронизированным циклам. ^[1] Цель DOPIPE — действовать как сборочный конвейер, на котором один этап запускается, как только для него имеется достаточно данных с предыдущего этапа. ^[6]

Рассмотрим следующий синхронный код с зависимостью S1[i] ->T S1[i+1].

for (int i = 1; i < n; ++i) {
    S1: a[i] = a[i-1] + b[i];
    S2: c[i] += a[i];
}

S1 должен выполняться последовательно, но S2 не имеет зависимости от цикла. S2 может выполняться параллельно с использованием параллелизма DOALL после последовательного выполнения всех вычислений, необходимых для S1. Однако в этом случае ускорение будет ограничено. Лучшим подходом является распараллеливание таким образом, чтобы S2, соответствующий каждому S1, выполнялся после завершения указанного S1.

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

for (int i = 1; i < n; ++i) {
    S1: a[i] = a[i-1] + b[i];
        post(i);
}

for (int i = 1; i < n; i++) {
        wait(i);
    S2: c[i] += a[i];
}

Допустим, время выполнения S1 и S2 будет $T_{S_{1}}$ и $T_{S_{2}}$ тогда время выполнения последовательной формы приведенного выше кода равно $n*(T_{S_{1}}+T_{S_{2}})$ , Теперь, поскольку существует параллелизм DOPIPE, ускорения можно достичь за счет выполнения итераций в конвейерном режиме, что дает нам время выполнения $n*T_{S_{1}}+(n/p)*T_{S_{2}}$ , где $p$ — количество параллельно работающих процессоров.

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

Параллелизм данных
ДОАКРОСС-параллелизм
Параллелизм задач
Параллелизм с использованием различных типов моделей памяти, таких как общая и распределенная , а также передача сообщений.

Ссылки [ править ]

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

[Solihin-1] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Солихин, Ян (2016). Основы параллельной архитектуры Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4 .

[2] Гофф, Джина (1991). «Практическое тестирование на зависимость». Материалы конференции ACM SIGPLAN 1991 года по проектированию и реализации языков программирования — PLDI '91 . стр. 15–29. дои : 10.1145/113445.113448 . ISBN 0897914287 . S2CID 2357293 .

[Parallelism_in_DOACROSS_Loops-3] Мерфи, Найл. «Обнаружение и использование параллелизма в циклах DOACROSS» (PDF) . Кембриджский университет . Проверено 10 сентября 2016 г.

[4] Кави, Кришна. «Распараллеливание циклов DOALL и DOACROSS — исследование» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[5] Унникришнан, Прия (2012), «Практический подход к распараллеливанию DOACROSS», Параллельная обработка Euro-Par 2012 , Конспекты лекций по информатике, том. 7484, стр. 219–231, номер документа : 10.1007/978-3-642-32820-6_23 , ISBN. 978-3-642-32819-0 , S2CID 18571258

[6] «DoPipe: эффективный подход к распараллеливанию моделирования» (PDF) . Интел . Проверено 13 сентября 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

v т и Параллельные вычисления
Общий	Распределенные вычисления Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ PEM-модели Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Экономическая эффективность Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН НУМА ЕСТЬ Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атеджи ПХ Способствовать росту Часовня HPX Очарование++ Том Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления