Пример анализа и распараллеливания алгоритма

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #5079
    @admin

    В качестве более сложного примера распараллеливания рассмотрим олимпиадную задачу на динамическое программирование. Прочитать условие задачи и ее последовательное решение можно тут: «Лесенка» [1]. Мы немного изменим условие, расширив диапазон подаваемых на вход значений чтобы программа считала дольше и оценка результатов распараллеливания была более наглядной.

    Для нас важно, что в процессе поиска решения программа перебирает множество вариантов расположения кубиков, причем эти варианты укладываются в структуру типа дерева:

    Дерево поиска решений

    Из каждого узла (кроме листьев) дерева можно сгенерировать другие варианты. Наша задача — распараллелить алгоритм такой генерации.

    При оценке результатов распараллеливания на вход программы будут подаваться большие числа, при этом может получаться результат, не умещающийся в диапазон чисел, задаваемый int. В связи с этим тип данных счетчика заменен на unsigned long. Кроме того, в приведенной выше реализации используется рекурсия, поэтому при распараллеливании нас может интересовать опция вложенного параллелизма — получить соответствующие настройки можно функцией omp_get_nested. Ниже приведена модифицированная с учетом приведенных выше соображений программа:

    #include <iostream>
    #include "omp.h"
    using namespace std;
    
    unsigned long get_count(int prev_level, int n) {
      if (0 == n)
        return 1;
      unsigned long count = 0;
      for (int level = 1; level < prev_level; ++level) {
        if ((n - level) < 0) 
          break;
        count += get_count(level, n - level);
      }
      return count;
    }
    
    int main() {
      cout << "omp_get_nested: " << omp_get_nested() << endl;
      
      for (int n = 100; n <= 200; n+=50) {
        auto start = omp_get_wtime();
        auto result = get_count(n+1, n);
        auto end = omp_get_wtime();
        cout << "n: " << n << endl;
        cout << "time: " << end - start <<  endl;
        cout << result << endl;
        cout << "------------" << endl;
      }
    }

    Результаты вычисления этой программы приведены на рисунке и используются в качестве эталона для проверки корректности работы параллельных версий программы:

    Можно попробовать распараллелить цикл for, при отключенном вложенном параллелизме потоки должны быть созданы только для цикла самого верхнего уровня. Использовать директиву parallel for в данном случае невозможно, т.к. внутри цикла используется инструкция break:

    #pragma omp parallel for reduction(+:count)
      for (int level = 1; level < prev_level; ++level) {
        if ((n - level) < 0) 
          break;
        count += get_count(level, n - level);
      }

    Решить проблему можно либо распараллеливанием вручную, либо следующей модификацией кода:

    unsigned long get_count(int prev_level, int n) {
      if (n == 0)
        return 1;
      if (n < 0)
        return 0;
        
      unsigned long count = 0;
      
    #pragma omp parallel for reduction(+:count)
      for (int level = 1; level < prev_level; ++level) {
        count += get_count(level, n - level);
      }
      
      return count;
    }

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

    Снижение производительности можно объяснить появившимися дополнительными затратами на вызов функции, а также тем, что объем задач потоков оказывается сильно разным:

    В районе отметки «40» завершилось вычисление для n=100 и началось вычисление n=150. Видно, что одно ядро чаще всего простаивает, тем не менее в системе работает два потока, добавились издержки на проверку того, нужно ли создавать новый поток в начале области parallel. Еще более плохой результат дало распараллеливание при включенном вложенном параллелизме:

    Пояснения по поводу взяты с MSDN [2]:

    При включении переменной среды может нарушить работу приложения, в противном случае оперативной поскольку потоков возрастает экспоненциально при вложении параллельных регионов. Например функция, что recurses 6 раз с количеством потоков OMP равным 4 требует 4096 байт (4 в степень 6) потоки в целом, снижается производительность приложения, если количество потоков превышает число процессоров. Единственным исключением бы ввода / вывода приложений.

    Незначительно улучшить ситуацию позволяет использование опции планирования потоков. Загрузка ядер в процессе работы программы для schedule(dynamic, 2) приведена ниже:

    Видно, что теперь нагрузка между ядрами делится значительно более равномерно, чем при статическом планировании. Время работы сократилось в 2 раза по сравнению со статическим планированием, но программа до сих пор работает значительно медленнее, чем последовательная:

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

    Решить проблему можно выносом части, отвечающей за создание потоков из рекурсивной функции так, чтобы потоки порождались единожды, а рекурсивная функция «ничего об этом не знала»:

    int main() {
      cout << "omp_get_nested: " << omp_get_nested() << endl;
      for (int n = 100; n <= 200; n+=50) {
        auto start = omp_get_wtime();
        unsigned long result = 0;
        
        #pragma omp parallel for reduction(+:result) schedule(dynamic)
        for (int level = 1; level <= n; ++level) {
          result += get_count(level, n-level);
        }
        
        auto end = omp_get_wtime();
        cout << "n: " << n
         << endl;
        cout << "time: " << end - start <<  endl;
        cout << result << endl;
        cout << "------------" << endl;
      }
    }

    Загрузка ядер при выполнении последнего варианта программы:

    Результаты и время работы:

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

    Входные данныеПоследовательнаяПараллельная (2 потока)Ускорение
    1000.0310.0171.794
    1501.5760.8801.791
    20045.29026.0311.740

    Данные о времени работы программы, приведенные в таблице наглядно показаны с помощью графика:

    Видно, что параллельная программа работает примерно в 2 раза быстрее последовательной, при этом количество работающих потоков не имеет значения. Это объясняется тем, что вычисления производились на двухъядерном процессоре: Intel® Pentium(R) CPU G2130 @ 3.20GHz × 2.

    Литература:

    1. Разбор последовательного решения задачи «Лесенка»: https://pro-prof.com/forums/topic/%D0%BB%D0%B5%D1%81%D0%B5%D0%BD%D0%BA%D0%B0
    2. вложенный параллелизм OpenMP: https://msdn.microsoft.com/ru-ru/library/sk3zt8e1.aspx
    3. Учебник по OpenMP: https://pro-prof.com/archives/4335

Для ответа в этой теме необходимо авторизоваться.