ДОПАЙП

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

Фон

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

Существуют различные методы распараллеливания, которые используются в зависимости от накладных расходов на хранение данных, степени распараллеливания и зависимостей данных . Некоторые из известных методов: DOALL , DOACROSS и DOPIPE .

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

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

Описание

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.

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 . С другой стороны, операторы F1 и F2 зависимы (пояснено выше), поэтому мы разделяем их на два разных цикла и выполняем их конвейерным способом . Мы используем post(j) и wait(j) для синхронизации между контурами F1 и F2.

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

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

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

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

DOALL Параллелизм в основном работает по принципу «разделяй и властвуй». Здесь все задачи выполняются в разных итерациях, использующих уникальный набор данных. Таким образом, проблема с этой реализацией заключается в том, что когда большой объем данных обрабатывается вместе, кэша требуется большое пространство для работы разных потоков . нет зависимостей Поскольку в потоках , накладные расходы на межпоточное взаимодействие отсутствуют.

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

См. также

Ссылки

^ Панкратий, Виктор; Адл-Табатабай, Али-Реза; Тичи, Уолтер (2011). Основы разработки многоядерного программного обеспечения . ЦРК Пресс. ISBN 9781439812747 .
^ Jump up to: ^а ^б ^с Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. ISBN 9781482211191 .

[1] Панкратий, Виктор; Адл-Табатабай, Али-Реза; Тичи, Уолтер (2011). Основы разработки многоядерного программного обеспечения . ЦРК Пресс. ISBN 9781439812747 .

[:0-2] Jump up to: ^а ^б ^с Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. ISBN 9781482211191 .

[1]

[2]