Использование задач вместо потоков

Using Tasks Instead of Threads [Eng., PDF 190KB]

Введение

Использование задач является достойной альтернативой потокам, которая позволяет реализовать более быстрый запуск и завершение, лучший баланс нагрузки, эффективное использование имеющихся ресурсов и высокий уровень абстракции. Три модели программирования, используюцие задачи, это Intel® Threading Building Blocks (Intel® TBB), Intel® Cilk++, и OpenMP*. В данной статье приводится краткий обзор программирования на основе задач и даются некоторые рекомендации, помогающие определиться, когда лучше использовать потоки, а когда – задачи.

Описание проблемы

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

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

Некоторые модели параллельного программирования, такие как Intel TBB, Intel Cilk++ и OpenMP API, дают разработчикам использовать преимущества пула потоков без необходимости явного управления им. Используя эти модели, разработчики выражают логический параллелизм приложений с помощью задач, а динамические библиотеки назначают эти задачи своему внутреннему пулу рабочих потоков. Таким образом, разработчик может сфокусироваться в своей программе на логическом параллелизме, при этом не беспокоясь об управлении этим параллелизмом. К тому же, поскольку задачи весят гораздо меньше, чем потоки, то параллелизм можно выражать с гораздо более низкой гранулярностью.

Простой пример использования задач приведён ниже. Функция fibTBB рассчитывает nth число Фибоначчи с помощью TBB task_group.При каждом вызове, если n >= 10, создается группа задач и запускаются две из них. В данном примере выражение lambda, описывающее каждую задачу, передается функции run. Эти вызовы запускают задачи, что делает их доступными для выполнения потоками в пуле потоков. Последующий вызов функции wait блокирует выполнение, пока все задачи в группе не завершаться.

int fibTBB(int n) {
  if( n<10 ) {
    return fibSerial(n);
  } else {
    int x, y;
    tbb::task_group g;
    g.run([&]{x=Fib(n-1);}); // spawn a task
    g.run([&]{y=Fib(n-2);}); // spawn another task
    g.wait();                // wait for both tasks to complete
    return x+y;
  }
}

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

Существуют и другие библиотеки, поддерживающие задачи, например, Intel Cilk++ и OpenMP API. В отличие от Intel TBB, обе эти модели используют поддержку компилятора, что упрощает их интерфейс, но делает их менее переносимыми. Например, тот же пример с числами Фибоначчи, показанный выше и использующий задачи ТВВ, ниже реализован уже как fibOpenMP. Так как OpenMP требует поддержки компилятора, для обозначения задач можно применять простые прагмы. Однако понять эти прагмы смогут только компиляторы, поддерживающие OpenMP API.

int fibOpenMP( int n ) {
  int i, j;
  if( n < 10 ) {
  return fibSerial(n);
  } else {
    // spawn a task
  #pragma omp task shared( i ), untied
    i = fib( n - 1 ); 
    // spawn another task
  #pragma omp task shared( j ), untied
    j = fib( n - 2 );
    // wait for both tasks to complete
  #pragma omp taskwait
  return i + j;
  }
}

Intel TBB, Intel Cilk++ и OpenMP API управляют распределением задач с помощью метода похищения работы. В этом методе каждый поток в пуле имеет свой локальный пул задач, организованный в виде очереди с двумя концами. Поток использует свой пул задач как стек, помещая новые задачи на верх стека. Когда поток оканчивает выполнение задачи, он сначала пытается снять другую задачу с верха своего локального стека. Задача наверху стека является самой свежей и, следовательно, скорее всего будет обращаться к тем горячим данным, которые лежат в кэше. Если в локальном пуле задач нет ни одной задачи, то поток пытается похитить задачу у другого потока. При похищении поток использует очередь жертвы как обычную очередь и берет самую старую задачу. В рекурсивных алгоритмах эти старые задачи являются узлами, находящимися высоко на дереве задач и, следовательно, представляют собой большие куски работы, как правило такой, которая не имеет горячих данных в кэше потока-жертвы. Следовательно, похищение работы является эффективным механизмом баланса нагрузки при поддержке локальности кэша.

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

Указания по применению

Хотя использование задач обычно является самым лучшим методом добавления многопоточности для повышения производительности, бывают случаи, когда использование задач не рекомендуется. Планировщики задач, используемые в Intel TBB, Intel Cilk, и OpenMP API не являются вытесняющими. То есть, задачи предназначены для неблокирующих высокопроизводительных алгоритмов. Они также нормально работают, если задачи применяют блокировки редко. Однако если задачи блокируются часто, то производительность падает из-за того, что при блокированной задаче поток не может работать ни с какой другой задачей. Блокировка обычно происходит при долгом ожидании ввода/вывода или мьютекса. Если потоки долго держат мьютексы, то код выполняется неэффективно, независимо от того, сколько потоков используется. Для блокирующихся задач лучше всего использовать не задачи, а потоки.

Даже в случаях, когда использование задач является лучшим вариантом, иногда не обязательно реализовывать модель задач с нуля. Библиотека Интел ТВВ предоставляет не только задачный интерфейс, но также и алгоритмы высокого уровня, которые реализуют некоторые самые распространенные функции, такие как parallel_invoke, parallel_for, parallel_reduce и pipeline. Intel Cilk++ предлагает параллельные циклы, то же самое делает OpenMP API. Поскольку эти функции были протестированы и отлажены, то при любой возможности лучше использовать эти алгоритмы высокого уровня.

Приведенный ниже пример показывает простой последовательный цикл и его параллельную версию, в которой используется алгоритм tbb::parallel_for:

// serial loop
for (int i = 0; i < 10000; ++i)
  a[i] = f(i) + g(i);

// parallel loop
tbb::parallel_for( 0, 10000, [&](int i) { a[i] = f(i) + g(i); } );

В приведенном примере parallel_for создает задачи, которые применяют тело цикла, в данном случае a[i] = f(i) + g(i), к каждому элементу в диапазоне [0,10000). Символ & в выражении lambda означает, что переменная a должна передаваться в виде ссылки. При использовании parallel_for, библиотека TBB выбирает подходящее количество итераций, группируемых вместе в единую задачу, чтобы минимизировать издержки наряду с созданием объемных задач для баланса нагрузки.

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