Параллельные задачи (tasks) OpenMP

В предыдущей статье был рассмотрен параллельный цикл, однако, в OpenMP есть и другие средства распараллеливания. В настоящей статье на примере быстрой сортировки рассмотрены параллельные задачи (tasks).

Затем, описаны параллельные задачи OpenMP. В конце статьи показано распараллеливание быстрой сортировки с использованием механизма задач OpenMP.

1. Быстрая сортировка на C++

Суть алгоритма быстрой сортировки выражается в двух шагах:

  1. разделить массив на 2 новых – в первый входят элементы меньше заданного, во второй – остальные;
  2. рекурсивно отсортировать каждый из новых массивов.

Для разделения массива в С++ можно использовать 2 индекса (i, j):

i = 0, 1, ..n-1
j = n-1, n-2, ..0
n - размер массива
pivot - опорный элемент

Всякий раз, когда i-тый элемент оказывается больше pivot, выполняется поиск j-того элемента меньше pivot. Найденные элементы обмениваются местами. Эта операция выполняется до тех пор, пока i(очевидно, что при i>j массив будет отсортирован). В качестве pivot можно выбрать любой элемент массива.

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

/*!
* quickSort - реализация алгоритма быстрой сортировки
* @param a сортируемый массив
* @param n индекс последнего элемента массива (не размер массива!)
*/
void quickSort(float* a, const long n) {
  long i = 0, j = n;
  float pivot = a[n / 2]; // выбор опорного элемента

  do {
    while (a[i] < pivot) i++;
    while (a[j] > pivot) j--;

    if (i <= j) {
      std::swap(a[i], a[j]);
      i++; j--;
    }
  } while (i <= j);

  if (j > 0) quickSort(a, j);
  if (n > i) quickSort(a + i, n - i);
}

Займемся распараллеливанием этого алгоритма, но начнем, с обзора подходящих средств OpenMP.

2. Параллельные задачи (tasks) и некоторые другие средства OpenMP

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

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

Можно отметить, что директива omp task имеет необязательную опцию if, задающую условие. Если условие истинно – будет создана задача и добавлена в пул, как описано выше, если же условие ложно – задача создана не будет, а ассоциированный с ней блок операторов будет немедленно выполнен в текущем потоке. В примерах статьи опция if не используется.

int main() {
  #pragma omp parallel num_threads(2)
  {
    std::cout << omp_get_thread_num();
    std::cout << "hello ";
  } // #pragma omp parallel
  std::cout << "\nfinish\n";
}

Листинг 2 показывает, что все потоки параллельной области выполняют один и тот же код. Если этот код будет содержать директиву task, то задача будет создана (и добавлена в пул) столько раз, сколько потоков породила параллельная область.

int main() {
  #pragma omp parallel num_threads(2)
  {
    #pragma omp task
    {
      std::cout << omp_get_thread_num();
      std::cout << "hello ";
    } // #pragma omp task
  } // #pragma omp parallel
  std::cout << "\nfinish\n";
}

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

рис. 1 директивы omp parallel и omp task

рис. 1 директивы omp parallel и omp task

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

int main() {
  #pragma omp parallel
  {
    #pragma omp task
    {
      std::cout << "hello ";
    } // #pragma omp task
    std::cout << "world ";
    #pragma omp taskwait
    std::cout << "bye ";
  } // #pragma omp parallel
  std::cout << std::endl;
}

Итак, в строке 2 порождается некоторое количество потоков. Каждый поток помещает в пул задачу (строки 4-7), выводит на экран слово “world” (строка 8), ожидает завершения задачи (строка 9), выводит на экран слово “bye” (строка 10). Таким образом, каждый поток гарантированно выведет по по очереди слова “world”, “hello”, “bye”, но т.к. параллельно работает несколько потоков, на экране может быть смазанная картина (рис. 2).

рис. 2 директива omp taskwait

рис. 2 директива omp taskwait

Кроме средств, описанных выше, для распараллеливания быстрой сортировки нам потребуется директива omp single, которая выделяет блок операторов, который будет выполнен лишь одним потоком.

int main() {
  #pragma omp parallel
  {
    #pragma omp single
    {
      #pragma omp task
      {
        std::cout << "hello ";
      } // #pragma omp task
      std::cout << "world ";
      #pragma omp taskwait
      std::cout << "bye ";
    } // #pragma omp single
  } // #pragma omp parallel
  std::cout << std::endl;
}

рис. 3 директива omp single

рис. 3 директива omp single

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

3. Параллельная реализация быстрой сортировки средствами OpenMP

В алгоритме быстрой сортировки, исходный массив разбивается на 2 части, обработка которых ведется не зависимо (поэтому может выполняться параллельно). Задачами у нас будут строки 20 и 21 из листинг 1:

if (j > 0) quickSort(a, j);
if (n > i) quickSort(a + i, n - i);

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

#pragma omp parallel shared(a)
{
  #pragma omp single nowait
  {
    quickSort(a, n - 1);
  } // #pragma omp single
} // #pragma omp parallel

На листинг 6 показано, что функция быстрой сортировки вызывается из параллельной области. Обрабатываемый массив (a) является общим для всех потоков. Функция должна быть вызвана только один раз – поэтому вызов помещен в область omp single.

И так, поток, выполнивший область omp single добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Каждый поток после порождения своих задач, должен дождаться из завершения как показано в листинг 7.

#pragma omp task shared(a) firstprivate(i, j)
  if (j > 0) quickSort(a, j);
#pragma omp task shared(a) firstprivate(i, j)
  if (n > i) quickSort(a + i, n - i);
#pragma omp taskwait

На рисунке 4 приведены диаграммы загрузки ядер процессора при сортировке большого массива.

рис. 4 диграммы загрузки процессора. быстрая сортировка. OpenMP

рис. 4 диграммы загрузки процессора. быстрая сортировка. OpenMP

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

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

Последним был запущен оптимизированный вариант быстрой сортировки. По прежнему оба ядра работают параллельно, сортировка выполняется быстрее.

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

Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно. Исходный код этого варианта приведен на листинг 8.

/*!
* quickSort - параллельная реализация алгоритма быстрой сортировки
* @param a сортируемый массив
* @param n индекс последнего элемента массива (не размер массива!)
*/
void quickSort(float* a, const long n) {
  long i = 0, j = n;
  float pivot = a[n / 2]; // опорный элемент

  do {
    while (a[i] < pivot) i++;
    while (a[j] > pivot) j--;

    if (i <= j) {
      std::swap(a[i], a[j]);
      i++; j--;
    }
  } while (i <= j);

  if (n < 100) { // если размер массива меньше 100
    // сортировка выполняется в текущем потоке
    if (j > 0) quickSort(a, j);
    if (n > i) quickSort(a + i, n - i);
    return;
  }

  #pragma omp task shared(a)
    if (j > 0) quickSort(a, j);
  #pragma omp task shared(a)
    if (n > i) quickSort(a + i, n - i);
  #pragma omp taskwait
}

рис. 5 сравнение реализаций быстрой сортировки

рис. 5 сравнение реализаций быстрой сортировки

Очередность запуски программы сортировки рис. 5 соответствует диаграммам рис. 4. Оптимизированная реализация быстрой сортировки работает на двух ядрах в полтора раза быстрее последовательного варианта.

Исходный код оптимизированного варианта, дополненный выводом информации, полезной для отладки можно скачать: быстрая сортировка [OMP].

Полезные ссылки

  1. введение в OpenMP / https://software.intel.com/ru-ru/blogs/2011/11/21/openmp-c
  2. Антонов А.С. Технологии параллельного программирования MPI и OpenMP: Учеб. пособие. Предисл.: В.А.Садовничий. – М.: Издательство Московского университета, 2012.-344 с.-(Серия “Суперкомпьютерное образование”). ISBN 978-5-211-06343-3.
  3. Распараллеливание рекурсивных функций, используя OpenMP 3.0 task / https://habrahabr.ru/company/intel/blog/99823/

7 thoughts on “Параллельные задачи (tasks) OpenMP

    1. admin Post author

      Если поток один, значит либо:
      – явно задано, что программа выполняется в одном потоке (в приведенном коде не делается этого);
      – у вас одноядерный компьютер – из за этого по умолчанию количество потоков в программе выставляется равным одному, но если даже явно указано иное число потоков, то выполняться они будут на одном ядре по очереди;
      – Вы не подключили OpenMP – в этом случае все директивы распараллеливания игнорируется и программа выполняется последовательно.

      Почти уверен что дело именно в неправильном подключении библиотеки. В предыдущей статье я писал какой ключ нужно добавить для сборки программы с использованием библиотеки OpenMP компилятором gcc (или mingw).
      Как и каким компилятором Вы собираете свою программу?

      1. Артем

        Использую компилятор от Intel, который поддерживает 3 стандарт. Работаю в среде Visual Studio 2012. Четырёхядерный компьютер.

        Добавлено: Да. Действительно потерял параметр при настройке компилятора. Спасибо.

        Добавлено: Пишет, что у меня 9 потоков. Сравниваю с последовательной по времени – никакой разницы нет.

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

        1. admin Post author

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

          1. Артем

            Слышал про такой закон. Только пока не особо вникал в него.
            Исследую пока сортировки.
            Для ограничения количества потоков использую
            omp_set_dynamic(0);
            omp_set_num_threads(4);
            чтобы определить время выполнения

            PS: как у Вас на блоге время настроено? Что-то с моими часами не совпадает

  1. t0n

    > Создание потока – очень сложная операция, требующая значительных вычислительных затрат.

    У Антонова наоборот:
    > В отличие от полноценных процессов, порождение нитей является относительно быстрой операцией, поэтому частые порождения и завершения нитей не так сильно влияют на время выполнения программы.

    1. admin Post author

      Если сравнивать с процессами – то да, поток – легковесная операция. Но полноценный поток (операционной системы) – это все равно очень сложный объект. Лучше по этой теме заглянуть в книжки Таненбаума, но подумайте сами:
      1) каждый поток выполняется независимо от других, значит его состояние должно содержать регистры (в т.ч. регистр программного счетчика, указывающий на текущую выполняемую потоком команду) и стек (хотя бы для того, чтобы внутри потока можно было независимо от других потоков вызывать функции);
      2) локальную память.
      Затем, операционная система должна управлять потоками (она должна принимать решения о том, какой поток вытеснить, а какой запустить). Поэтому:
      1) новые потоки осложняют управление операционной системе. Так например, когда поток запросит ввод, операционная система может снизить ему приоритет. Если таких потоков много – операционной системе тяжело;
      2) каждый поток должен содержать таймер для вычисления кванта времени, по окончанию которого операционная система вытеснит его.

      Важно еще и то, что переключение потоков выполняется более менее быстро только в рамках одного процесса. Если процесс в данный момент вытеснен, то передача кванта времени одному из его потоков – очень долгая операция, т.к. при этом в память нужно загрузить информацию обо всех открытых процессом файлах, объектах синхронизации, глобальные переменные.

      Конкретно в статье я имел ввиду то, что OpenMP работает с потоками операционной системы, которые достаточно тяжеловесны и несколько сотен потоков могут сильно загрузить систему. Однако в противовес им есть, так называемые, легковесные потоки. В то же время Антонов пишет книжки по OpenMP и MPI и говорит в ином контексте.

Добавить комментарий