Pull to refresh
0

Распараллеливание рекурсивных функций, используя OpenMP 3.0 task

Reading time 3 min
Views 13K
image
Недавно я наткнулся на блог “OpenMP 3.0 tasking model: as smooth as Cilk?”. После чего я решил проверить, как хорошо распараллеливаются рекурсивные функции с OpenMP 3.0 task. Напомню, что до третьего стандарта не было поддержки динамического или иррегулярного параллелизма(к примеру, циклы с while или рекурсивные функции).


Вычислительные системы


Начну с описания вычислительных систем, которыми я пользовался.
Ниже список компьютеров, на которых результаты я могу освещать. Остальные еще не вышли в продакшэн.
image

Процесс распараллеливания


Для тестирования я взял пример вычисления чисел Фибоначчи . Идея распараллеливания была следующая: создавать на каждый шаг рекурсии свой асинхронный task, а потом перед выходом из функции организовать синхронизацию. К сожалению, при этом подходе я не получил ускорения больше, чем 1. По причине доминирования затрат на runtime. Решение нашлось тут и оказалось простым: создавать таски только для части шагов рекурсии, а остальную часть исполнять последовательно. Другими словами, сбалансировать затраты на runtime и время исполнения. Ниже приведен кусок кода, который отвечает за балансировку:
INT_TYPE
fib( INT_TYPE n ) {
INT_TYPE i, j;
if( n < SPLITTER ) {
return fib_serial( n );
} else {
#pragma omp task shared( i )
i = fib( n - 1 );
#pragma omp task shared( j )
j = fib( n - 2 );
#pragma omp taskwait
return i + j;
}
}

В данном примере SPLITTER как раз отвечает за балансировку. Весь исходный код можно скачать тут.
Но не все так просто. Для различных значений SPLITTER эффективность распараллеливания разная. Путем метода тыка пальцем в небо, я подобрал два значения сплиттера 19 и 32 при которых эффективность распараллеливания приближается к единице.

Компиляции


Из всего ПО будут интересны только компиляторы. В моем распоряжении было три компилятора: Intel® Composer XE for Linux, Microsoft Visual C++ 2010 и GCC. Visual C++ сразу отметается, так как не поддерживает OpenMP 3.0(на данный момент есть поддержка только OpenMP2.5). GCC поддерживает OpenMP 3.0 начиная с версии 4.4, я пользовался 4.5.0.
Ниже времена компиляции и размеры исполняемых файлов как с динамическими библиотеками, так и со статическими. Но стоит заметить, что в отличии от GCC, Intel® Composer XE установлен на удаленной машине. Что влечет к увеличению времени компиляции.

image

Строки для GCC и Intel® Composer XE следующие:
# gcc ./fib_task.c -fopenmp
# gcc ./fib_task.c -fopenmp -static
# icc ./fib_task.c -openmp -static
# icc ./fib_task.c -openmp

Время исполнения и масштабируемость


Все замеры производились для поиска 50-ого числа Фибоначчи для SPLITTER=19 и SPLITTER=32.
image

Ускорение и эффективность распараллеливания


image
На данном графике изображено ускорение для SPLITTER=32. В свою очередь эффективность – это отношение количества потоков и ускорения.

Исходные и исполняемые файлы


Как уже говорилось выше исходный файл можно скачать тут. В данном примере вычисляется 41-ое число Фибоначии. Для воспроизведения замеров нужно изменить переменную n = 50 и переменную expected = 12586269025UL. Также можно сразу скачать
  • исполняемые файлы сгенерированные с Intel® Composer XE для SPLITTER=19 и SPLITTER=32;
  • исполняемые файлы сгенерированные с GCC 4.5.0 для SPLITTER=19 и SPLITTER=32.

Выводы


Собственно, графики с временами исполнения и ускорениями все сами говорят.
  • Для Composer XE эффективность распараллеливания ~1 до тех пор, пока количество потоков не превышает количества физических ядер.
  • Для GCC 4.5.0 эффективность распараллеливания ~0.5 до тех пор, пока количество потоков не превышает количества физических ядер.

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

Послесловие


На PringerLink нашел статью "An Extension to Improve OpenMP Tasking Control", в которой предлагается ввести новую клаузу final , которая выполняет роль балансировщика. С моей точки зрения, это трезвое предложение. А еще можно добавить клаузы-балансировщики, которые в realtime будут производить адаптивную балансировку.

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.
Tags:
Hubs:
+16
Comments 21
Comments Comments 21

Articles

Information

Website
www.intel.ru
Registered
Founded
Employees
5,001–10,000 employees
Location
США
Representative
Анастасия Казантаева