Недавно я наткнулся на блог “OpenMP 3.0 tasking model: as smooth as Cilk?”. После чего я решил проверить, как хорошо распараллеливаются рекурсивные функции с OpenMP 3.0 task. Напомню, что до третьего стандарта не было поддержки динамического или иррегулярного параллелизма(к примеру, циклы с while или рекурсивные функции).
Вычислительные системы
Начну с описания вычислительных систем, которыми я пользовался.
Ниже список компьютеров, на которых результаты я могу освещать. Остальные еще не вышли в продакшэн.
Процесс распараллеливания
Для тестирования я взял пример вычисления чисел Фибоначчи . Идея распараллеливания была следующая: создавать на каждый шаг рекурсии свой асинхронный 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 установлен на удаленной машине. Что влечет к увеличению времени компиляции.
Строки для 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.
Ускорение и эффективность распараллеливания
На данном графике изображено ускорение для 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.