Всегда ли оправданно распараллеливание?

OpenMP — мощная технология, позволяющая значительно повысить быстродействие приложения без переработки его архитектуры. Как и в случае с любой другой мощной технологией, знать, когда нужно её использовать не менее важно, чем уметь с этой технологией работать. В данной статье мы попытаемся показать, что распараллеливание — не панацея от всех бед, и неправильное его использование не только не улучшает производительность приложения, но и может привести к проблемам. Мы постараемся рассмотреть реализацию OpenMP на низком уровне, чтобы оценить потери производительности, связанные с издержками на управление потоками и внутреннюю синхронизацию. В конце статьи будут даны некоторые практические рекомендации по использованию OpenMP.

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

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

Технология OpenMP наиболее эффективна, если код включает длительные циклы без зависимостей (текущая итерация цикла не зависит от результатов, полученных на предшествующих итерациях) и работает с разделяемыми массивами данных [1].

Организация OpenMP в GCC/Linux

Активация поддержки OpenMP в компиляторе GCC включается путём использования ключа -fopenmp (заметим, что этот ключ должен указываться как при компиляции программы, так и при связывании). Цена использования OpenMP — зависимость от двух динамических библиотек: libpthread и libgomp. Собственно реализация OpenMP находится в библиотеке libgomp; для параллельной обработки используются POSIX-потоки.

При запуске программы инициализационный код libgomp разбирает переменные среды и инициализирует внутренние структуры данных. Так как инициализация происходит единовременно при запуске приложения, влияния на дальнейшую производительность приложения она не оказывает, поэтому мы не будем её анализировать.

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

При желании можно создать потоки заранее (например, при задании маски соответствия процессоров). В этом случае лучше сразу создавать требуемое количество потоков, ибо создание каждого дополнительного потока (например, при использовании вложенных регионов) приводит к необходимости вызова realloc() — не самой быстрой функции на свете.
Создание одного потока сводится к следующим операциям:

  • создание мьютекса, барьера и семафора, а также вызов malloc() для выделения памяти под внутренние структуры данных (функция new_team()). В зависимости от поддержки TLS может понадобиться вызов pthread_getspecific();
  • создаётся барьер (синхронизационный примитив) для пула потоков (при вхождении в самый первый параллельный регион);
  • создаётся требуемое количество потоков; потоки (если система поддерживает данную операцию) могут быть привязаны к конкретному процессору;
  • путём вызова pthread_create() создаётся необходимое количество потоков;
  • каждый из созданных потоков создаёт семафор;
  • производится внутренняя синхронизация потоков, после чего, собственно, и начинаются вычисления.

Отметим несколько особенностей, характерных для libgomp:

  • если количество создаваемых потоков оставляется на усмотрение библиотеки времени выполнения, то, например, при наличии четырёх процессоров нет гарантии, что система создаст три потока (один — главный — уже есть, это основная программа): количество создаваемых потоков определяется как разность между доступными процессорами и средней загрузкой за последние 15 минут;
  • для того, чтобы библиотека времени выполнения осуществила привязку созданных потоков к конкретным процессорам, наличия в системе функции pthread_setaffinity_np() не является достаточным условием — по умолчанию созданные потоки будут привязаны ко всем доступным процессорам. Это очень легко проверяется:
    [-]
    View Code C
    #define _GNU_SOURCE 1
    #include <unistd.h>
    #include <stdio.h>
    #include <sched.h>
    #include <omp.h>

    int main(int argc, char** argv)
    {
        #pragma omp parallel
        {
            cpu_set_t mask;
            int i;
            sched_getaffinity(0, sizeof(mask), &mask);
            for (i=0; i<CPU_SETSIZE; ++i) {
                if (CPU_ISSET(i, &mask)) {
                    printf("Thread %d: CPU %d\n", omp_get_thread_num(), i);
                }
            }
        }

        return 0;
    }

    Этот код выдаст результат, схожий с нижеприведённым:

    [-]
    View Code Text
    Thread 0: CPU 0                                        
    Thread 0: CPU 1                                        
    Thread 0: CPU 2                                        
    Thread 0: CPU 3                                        
    Thread 1: CPU 0                                        
    Thread 1: CPU 1
    Thread 1: CPU 2
    Thread 1: CPU 3
    Thread 3: CPU 0
    Thread 3: CPU 1
    Thread 3: CPU 2
    Thread 3: CPU 3
    Thread 2: CPU 0
    Thread 2: CPU 1
    Thread 2: CPU 2
    Thread 2: CPU 3
    Для того, чтобы привязать потоки к конкретному процессору, нужно правильно задать переменную среды GOMP_CPU_AFFINITY.

В Linux вся синхронизация потоков в OpenMP основана на фьютексах (это отдельная тема для разговора) и атомарных инструкциях синхронизации процессора, что позволяет снизить накладные расходы. Тем не менее, создание и запуск потока являются относительно дорогими операциями.

С точки зрения ассемблера, создание параллельного региона выглядит так:

[-]
View Code ASM
        xor     edx, edx
        mov     rsi, rsp
        mov     DWORD PTR [rsp], edi
        mov     edi, OFFSET FLAT:parallel.omp_fn.0
        call    GOMP_parallel_start
        mov     rdi, rsp
        call    parallel.omp_fn.0
        call    GOMP_parallel_end

Иными словами, компилятору приходится создавать дополнительную функцию (в нашем примере это parallel.omp_fn.0). Как следствие, тратится процессорное время на организацию вызовов процедур, сохранение/восстановление регистров и т.п. Сама "параллельная" функция (в случае статического планирования) вызывает omp_get_num_threads() и omp_get_thread_num() для определения количества итераций, которые она должна выполнить.

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

Методика эксперимента

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

Процесс поиска начинается со ста итераций и идёт с переменным шагом: Δ=100 при 100≤i<1000; Δ=1,000 при 1,000≤i<10,000; Δ=10,000 при 10,000≤i<100,000; Δ=100,000 при 100,000≤i<10,000,000.

Для получения более точных временных характеристик каждая итерация выполняется 20 раз. Из полученных данных отбрасываются два худших результата и вычисляется среднее арифметическое значение.

Результаты эксперимента

Эксперимент проводился на процессоре AMD Phenom(tm) II X4 940 Processor, позволяющем программно изменять частоту каждого из ядер, на частотах 800 MHz, 1.8 GHz, 2.3 GHz и 3 GHz. Размер блока, обрабатываемого за одну итерацию, составляет 8 байт.

Данные эксперимента (text/csv, 23,688 байт)
Данные эксперимента (application/vnd.oasis.opendocument.text, 2.5 МиБ)

Используемые обозначения:

S/f
последовательное выполнение алгоритма, частота процессора f ГГц;
P/n/f
параллельное выполнение алгоритма с использованием n потоков, частота ядер процессора f ГГц.
Рисунок 1 — Результаты эксперимента
при частоте 800 МГц
Рисунок 2 — Результаты эксперимента
при частоте 1.8 ГГц
Рисунок 3 — Результаты эксперимента
при частоте 2.3 ГГц
Рисунок 4 — Результаты эксперимента
при частоте 3 ГГц

Анализ результатов

Сразу отметим, что данные, полученные в ходе эксперимента, являются весьма приблизительными: очень трудно учесть влияние других процессов, обработку прерываний и прочие вещи, характерные для многозадачных систем; кроме того, использование функции gettimeofday() для измерения промежутка времени ограничивает точность измерений до 1 мс.

В ходе проведения эксперимента были получены весьма интересные (и даже парадоксальные) результаты. В частности, при понижении тактовой частоты процессора с 3 ГГц до 2.3 или 0.8 ГГц получалось, что четыре потока работают быстрее, чем три (что, в принципе, логично), но медленнее, чем два. Парадоксальный, но вполне воспроизводимый факт.

Отметим некоторые факты:

  • создание четырёх потоков произошло довольно быстро — в пределах точности gettimeofday() (Википедия приводит пример, что на создание 100,000 потоков уходит порядка 2 секунд на IA-32);
  • затраты на поддержание потоков нелинейны: по предварительным результатам получается, что если стоимость поддержания одного потока составляет N единиц, то для двух потоков стоимость будет равна примерно 2N, а для трёх — примерно 2.5N (N не зависит от количества итераций). Очень интересно проверить результаты на восьмипроцессорной системе;
  • при произвольно большом количестве процессоров производительность системы с памятью, разделяемой всеми процессорами, ограничена сверху пропускной способностью памяти. Особенно хорошо это видно из данных, полученных для частоты 800 МГц: максимальная производительность алгоритма достигается при использовании всего двух потоков; добавление новых потоков не улучшает ситуацию;
  • производительность приложения OpenMP очень сильно зависит от загрузки системы: в случае большого количества активных процессов, затраты на переключение между ними сводят на нет преимущества OpenMP. Отсутствие общесистемной библиотеки, координирующей все потоки OpenMP, может привести к тому, что запуск нескольких приложений OpenMP может привести к большому потреблению системных ресурсов;
  • при проектировании высокопроизводительного приложения OpenMP очень важно понимать, как работает кэш процессора. Неправильный подход к работе с данными может привести к неэффективному использованию процессорных кэшей и, как следствие, вынудить процессор тратить полезное время не на вычисления, а на относительно медленные обращения к памяти. Перед проектированием подобных приложений очень неплохо ознакомиться, например, с такими публикациями, как "Programming for tomorrow's high speed processors, today" и "Understanding CPU Caches" Ульриха Дреппера.

Рекомендации

На основании результатов, полученных в ходе эксперимента, можно дать следующие рекомендации:

  • количество потоков по возможности не должно превышать количество доступных процессоров, ибо один процессор (одно ядро) не в состоянии выполнить две задачи параллельно;
  • максимальное количество потоков (если не ограничено сверху количеством доступных процессоров) можно приблизительно рассчитать отношением средней скорости копирования блоков данных требуемого размера в памяти к средней скорости работы распараллеливаемого алгоритма. Например, если скорость копирования восьмибайтных блоков составляет 9.6 ГиБ/сек, то например, при скорости алгоритма в 5 ГиБ/сек не имеет смысла создавать более двух (возможно, трёх) потоков. Тем не менее, стоит помнить, что даже если скорость памяти позволяет увеличить скорость передачи данных в два раза, добавление еще одного вычислителя может не привести к реальному ускорению работы в два раза;
  • так как производительность приложения OpenMP зависит от загрузки системы, не стоит без необходимости явно указывать количество потоков: в идеале, планировщик операционной системы знает лучше;
  • примерное количество итераций, с которого распараллеливание имеет смысл, эмпирически можно оценить при помощи следующего выражения:

    L/(v×n)+c < L/v,

    где L — объём обрабатываемых данных, v — скорость их обработки, n — поправочный коэффициент (равный произведению количества вычислителей на процентный объём распараллеливаемых вычислений), c — время, необходимое на внутреннюю организацию потоков.
    В общем случае коэффициент n является системно-зависимым.

Добавить в закладки

Связанные записи

10
Апр
2009

Комментарии к статье «Распараллеливать или не распараллеливать — вот в чём вопрос» (1)  »

  1. [...] ранее писал, что технология OpenMP наиболее эффективна, если код [...]

Подписаться на RSS-ленту комментариев к статье «Распараллеливать или не распараллеливать — вот в чём вопрос» Trackback URL: http://blog.sjinks.org.ua/openmp/527-to-parallelize-or-not-to-parallelize/trackback/

Оставить комментарий к записи «Распараллеливать или не распараллеливать — вот в чём вопрос»

Вы можете использовать данные тэги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Оставляя комментарий, Вы выражаете своё согласие с Правилами комментирования.

Подписаться, не комментируя