ДОПИП - DOPIPE

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

Фон

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

Существуют различные методы распараллеливания, которые используются в зависимости от накладных расходов на хранение данных, степени распараллеливания и зависимости данных. Вот некоторые из известных методов: СДЕЛАЙ ВСЕ, ДОАКРОСС и ДОПИП.

СДЕЛАЙ ВСЕ: Этот метод используется, когда мы можем распараллеливать каждую итерацию цикла без какого-либо взаимодействия между итерациями. Следовательно, общее время выполнения сокращается с N * T (для последовательного процессора, где T - время выполнения для каждой итерации) только до T (поскольку все N итераций выполняются параллельно).

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

Описание

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

Пример

Программа ниже показывает псевдокод[2] для распараллеливания DOPIPE.

В этом коде мы видим, что есть три задачи (F0, F1 и F2) внутри цикла, повторяющего j от 1 до N. Ниже приводится список зависимостей в коде:

F1 [j] → Т F1 [j + 1], следует, что оператор F1 на итерации j + 1 должен выполняться после оператора F1 в итерации j. Это также известно как истинная зависимость.

F1 [j] → Т F2 [j], следует, что оператор F2 на итерации j должен выполняться после оператора F1 в итерации j.

для (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; F1: z [j] = z [j-1] * 5; F2: y [j] = z [j] * w [j];}

Если бы этот код выполнялся последовательно, то общее затраченное время было бы равно N * (TF0 + ТF1 + ТF2), где TF0, ТF1 и тF2 обозначают время выполнения для функций F0, F1 и F2 соответственно на итерацию. Теперь, если мы распараллеливаем цикл путем конвейерной обработки операторов внутри цикла следующим образом:

для (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; // ДЕЙСТВИТЕЛЬНЫЙ параллелизм} for (j = 1; j <= N; j ++) {F1: z [j] = z [j-1] * 5; // DOPIPE parallelism post (j); // Результат F1 публикуется и доступен для использования} for (j = 1; j <= N; j ++) {wait (j); // Ожидается, пока F1 завершится, и выдает значение z [j], которое будет использоваться F2 F2: y [j] = z [j] * w [j];}

Поскольку F0 является независимой функцией, то есть у нее нет зависимости с переносом цикла (нет зависимости от j + 1 или же j-1 итераций). Также он не зависит от других операторов в цикле. Следовательно, мы можем полностью отделить эту функцию и запустить ее параллельно, используя DOALL. параллелизм. С другой стороны, операторы F1 и F2 зависимы (объяснено выше), поэтому мы разбиваем их на два разных цикла и выполняем их в конвейерный мода. Мы используем сообщение (j) и подожди (j) для синхронизации между контурами F1 и F2.

Начиная с первой итерации j, оператор F1 выполняется в TF1 время. Между тем, F2 не выполняется, так как ожидает значения z [j] будет производиться F1. Когда F1 завершает свое выполнение для итерации j, он публикует значение, используя сообщение (j). После ожидания выполнения F1, используя подожди (j), F2 начинает выполнение, поскольку имеет значение z [j] доступны для использования. Кроме того, поскольку выполнение F1 не ограничено F2, поэтому F1 выполняет j + 1 одновременно. На рисунке ниже показан график выполнения всех операторов.

Пример DOPIPE

Из рисунка видно, что общее время выполнения F0 равно TF0, поскольку все итерации F0 выполняются параллельно. В то время как для F1 и F2 общее время выполнения равно N * TF1 + ТF2 (учитывая пренебрежимо малое время синхронизации).

Это значительно меньше времени, полученного при последовательном выполнении.

Сравнение с другими моделями

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

В DOPIPE между потоками возникает служебная нагрузка на синхронизацию. Но из-за своей конвейерной структуры он требует меньше места в кеш-памяти, поскольку производимые данные немедленно потребляются потребителем.[2]

Смотрите также

Рекомендации

  1. ^ Панкратий, Виктор; Адл-Табатабай, Али-Реза; Тихи, Уолтер (2011). Основы разработки многоядерного программного обеспечения. CRC Press.
  2. ^ а б c Солихин, Ян (2016). Основы параллельной многоядерной архитектуры. Чепмен и Холл / CRC.