Модели программирования OpenMP и Intel® CilkTM Plus

Презентацию к данной лекции Вы можете скачать здесь.

Многопоточная программа

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

Поток и процесс соотносятся следующим образом:

Конкуренция за ресурсы и параллельное исполнение

Конкуренция за ресурсы (видимый параллелизм)

Реальный параллелизм

Для реализации реального параллелизма требуется соответствующая архитектура – многоядерная или многопроцессорная с общей памятью.

При разработке многопоточных приложений возникают следующие проблемы:

Гонки за данными (data races)

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

Борьба с гонками за данными:

Блокировки

Блокировка (тупик) возникает, если поток ожидает выполнение условия, которое не может быть выполнено. Обычно возникновение тупиковой ситуации является следствием конкуренции потоков за ресурс, который удерживается одним из них.

Условия возникновения тупика

Масштабируемость

Число программных потоков должно совпадать с числом аппаратных потоков. Зависимость ускорения от числа потоков для теста на 2-ядерной архитектуре:

Программные инструменты реализации многопоточного параллелизма

Программирование с OpenMP (Open MultiProcessing)

Модель программы

OpenMP

Pro

Contra

Структура

Привязка к языкам

Привязка к C/C++

В программах на языке C прагмы, имена функций и переменных окружения OpenMP начинаются с omp, omp_ или OMP_. Формат директивы:

#pragma omp директива [оператор_1[, оператор_2, :]]

В OpenMP-программе используется заголовочный файл omp.h.

Привязка к языку Fortran

В программах на языке Fortran директивы компилятора, имена подпрограмм и переменных окружения начинаются с OMP или OMP_. Формат директивы компилятора:

{!|C|*}$OMP директива [оператор_1[, оператор_2, :]]

Директива начинается в первой (фиксированный формат записи текста языка Fortran 77) или произвольной (свободный формат) позиции строки. Допускается продолжение директивы в следующей строке, в этом случае действует стандартное в данной версии языка правило для обозначения строки продолжения (непробельный символ в шестой позиции для фиксированного формата записи и амперсанд для свободного формата).

Пример

#include "omp.h"
#include <stdio.h>

double f(double x) 
{
return 4.0 / (1 + x * x); 
}
main () 
{
const long N = 100000;
long i;
double h, sum, x;
sum = 0;
h = 1.0 / N;

#pragma omp parallel shared(h) 
{
#pragma omp for private(x) reduction(+:sum)

for (i = 0; i < N; i++) 
{
x = h * (i + 0.5);
sum = sum + f(x); 
} 
}
printf("PI = %f\n", sum / N); 

Эффективность

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

Диспетчеризацией параллельной OpenMP-программы управляет программист с помощью оператора schedule. Поддерживаются три способа распределения работы между потоками: статический, динамический и "управляемый".

Модель программирования Intel® CilkTM Plus

Модель программирования Intel® CilkTM Plus основана на параллелизме задач. Программа пишется в семантике последовательного программирования. Фрагменты для распараллеливания расщепляются на подзадачи, связанные отношениями подчинения ("родитель"-"потомок"). Такая реализация параллелизма иногда называется "fork-join".

Программист, использующий CilkTM Plus должен думать о том, что следует распараллелить, а не как. В этом – одно из отличий от OpenMP-программирования.

Балансировкой занимается runtime-система. Балансировка выполняется методом захвата работы. Алгоритмы диспетчеризации таковы, что их эффективность, как правило, высока.

Удобные средства работы с массивами (расширенная индексная нотация – аналог сечений массивов в языке Fortran).

Удобное использование векторных расширений команд, векторизация функций.

Вычислительная работа разбивается на задачи. Каждая задача – это фрагмент большей задачи.

Программист

Определяет и описывает потенциальный параллелизм.

Планировщик

Отображает его на реально существующую конфигурацию потоков.

Задачи связаны между собой отношениями подчинения. Конфигурацию приложения во время его выполнения можно изобразить в виде направленного ациклического графа (DAG).

Граф задач в Cilk-программе является динамическим – он создается и изменяется в процессе выполнения программы.

В Intel® CilkTM Plus сохраняется семантика последовательной программы.

Программа может выполняться как в последовательном, так и в параллельном режимах.

Параллельное выполнение возможно, если это допускает целевая платформа (достаточное количество ядер).

Сериализация (выполнение программы в последовательном режиме) происходит, если степень параллелизма целевой платформы недостаточно велика.

Сериализация также происходит при использовании заголовочного файла

<cilk/cilk_stub.h>

и при компиляции с соответствующим ключом:

icc: -cilk-serialize
icl: /Qcilk-serialize

В Microsoft Visual Studio сериализовать Cilk-программу можно так:

Properties --> C/C++ --> Language [Intel C++] --> Replace Intel Cilk Plus Keywords with Serial Equivalent