Войти
DOPIPE parallelism - это метод выполнения параллелизма на уровне цикла путем конвейерной обработки операторы в цикле. Конвейерный параллелизм может существовать на разных уровнях абстракции, таких как циклы, функции и алгоритмические этапы. Степень параллелизма зависит от способности программистов наилучшим образом использовать эту концепцию. Это также зависит от таких факторов, как идентификация и разделение независимых задач и их параллельное выполнение.
Основная цель использования параллелизма на уровне цикла - поиск и разделение последовательных задач программы и преобразование их в параллельные задачи без какой-либо предварительной информации об алгоритме . Части данных, которые повторяются и потребляют значительное время выполнения, являются хорошими кандидатами для параллелизма на уровне цикла. Некоторые общие применения параллелизма на уровне цикла можно найти в математическом анализе, в котором используются многомерные матрицы, которые повторяются во вложенных циклах.
Существуют различные методы распараллеливания, которые используются в основу накладных расходов на хранение данных, степень распараллеливания и зависимости данных. Вот некоторые из известных методов: DOALL, DOACROSS и DOPIPE .
DOALL: Этот метод используется, когда мы можем распараллелить каждую итерацию цикла. без взаимодействия между итерациями. Следовательно, общее время выполнения сокращается с N * T (для последовательного процессора, где T - время выполнения для каждой итерации) только до T (поскольку все N итераций выполняются параллельно).
DOACROSS: Этот метод используется везде, где есть вероятность зависимости данных. Следовательно, мы распараллеливаем задачи таким образом, что все задачи, не зависящие от данных, выполняются параллельно, а зависимые - последовательно. Существует определенная степень синхронизации, которая используется для синхронизации зависимых задач между параллельными процессорами.
DOPIPE - это метод конвейерного распараллеливания, который используется в программах, где каждый элемент, созданный во время каждой итерации, потребляется на более поздней итерации. В следующем примере показано, как реализовать технику DOPIPE, чтобы сократить общее время выполнения, разбивая задачи внутри цикла и выполняя их конвейерно . Разделение на задачи происходит таким образом, что все зависимости внутри цикла являются однонаправленными, т.е. следующая итерация не зависит от предыдущей итерации.
Программа ниже показывает псевдокод для распараллеливания 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.
for (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 * (T F0 + T F1 + T F2), где T F0, T F1 и T F2 обозначают время выполнения функций F0, F1 и F2 соответственно за итерацию. Теперь, если мы распараллелим цикл путем конвейерной обработки операторов внутри цикла следующим образом:
for (j = 1; j <=N; j++) { F0: o[j] = x[j] - a[j]; // DOALL parallelism } for (j=1; j<=N; j++) { F1: z[j] = z[j-1] * 5; // DOPIPE parallelism post(j); // The result of F1 is posted and available for use } for (j=1; j<=N; j++) { wait(j); // It waits till the F1 completes and produces the value z[j] to be used by F2 F2: y[j] = z[j] * w[j]; }Поскольку F0 является независимой функцией, то есть у нее нет никакой переносимой цикла зависимости ( нет зависимости от итераций j + 1или j-1). Также он не имеет никакой зависимости от других операторов в цикле. Следовательно, мы можем полностью отделить эту функцию и запустить ее параллельно с использованием DOALL parallelism. С другой стороны, операторы F1 и F2 зависимы (объяснено выше), поэтому мы разделяем их на два разных цикла и выполняем их в конвейерный мод. Мы используем post (j)и wait (j)для синхронизации между циклами F1 и F2.
Начиная с первой итерации j, оператор F1 выполняется за время T F1. Между тем, F2 не выполняется, так как ожидает, пока F1 не выдаст значение z [j]. Когда F1 завершает выполнение итерации j, он отправляет значение с помощью post (j). После ожидания выполнения F1 с использованием wait (j), F2 начинает свое выполнение, так как имеет доступное для использования значение z [j]. Кроме того, поскольку выполнение F1 не ограничено F2, следовательно, F1 выполняет j + 1одновременно. На рисунке ниже показана шкала времени выполнения всех операторов.
Пример DOPIPE Из рисунка видно, что общее время выполнения F0 равно T F0, поскольку все итерации F0 выполняются параллельно. В то время как для F1 и F2 общее время выполнения равно N * T F1 + T F2 (с учетом незначительного времени синхронизации).
Это значительно меньше времени, полученного при последовательном выполнении.
DOALL параллелизм в основном работает по принципу разделяй и властвуй. Здесь все задачи выполняются в разных итерациях с использованием уникального набора данных. Таким образом, проблема с этой реализацией заключается в том, что когда большой объем данных вычисляется вместе, требуется большое пространство кэша для работы для разных потоков. Поскольку в потоках нет зависимостей, нет накладных расходов на межпотоковое взаимодействие.
В режиме DOPIPE между потоками возникают накладные расходы на синхронизацию. Но из-за своей конвейерной структуры он требует меньше места в кэше, поскольку производимые данные немедленно потребляются потребителем.
