эффективность в многопоточности

Question

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

for(i = 0; i < i_max; i++)
  for(j = 0; j < j_max; j++)
     // do something

и я хочу сделать это, используя разные потоки (предполагая, что задачи // делать что-то не зависят друг от друга, подумайте, например, о симуляции Монте-Карло). Мой вопрос таков: обязательно ли лучше создавать поток для каждого значения i, чем создавать поток для каждого значения j? Как то так

for(i = 0; i < i_max; i++)
  create_thread(j_max);

дополнительно: какое будет подходящее количество потоков? Должен ли я просто создать потоки i_max или, возможно, использовать семафор с k <потоками i_max, работающими одновременно в любой момент времени. </p>

Спасибо,

Answer 1

Лучший способ распределения рабочей нагрузки зависит от рабочей нагрузки.

В широком смысле - для распараллеливаемой рабочей нагрузки используйте OpenMP; для разнородной рабочей нагрузки используйте пул потоков. Избегайте управления своими собственными потоками, если можете.

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

Кстати, если вы работаете в Visual C ++, в Visual C ++ v10 есть интересная новая среда выполнения с параллелизмом , предназначенная именно для этого типа проблемы. Это несколько похоже на библиотеку параллельных задач, которая была добавлена ​​в .Net Framework 4 для упрощения реализации многоядерного / многопроцессорного кода.

Answer 2

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

Во-первых, создайте 1 поток на процессор / ядро.Это ваши рабочие темы.Они бездействуют, пока им не скажут что-то сделать.

Теперь разделите свою работу так, чтобы работать так, чтобы данные, которые необходимы одновременно, были близко друг к другу.Под этим я подразумеваю, что если бы вы обрабатывали массив из десяти элементов на двухпроцессорном компьютере, вы бы разбили его так, чтобы одна группа составляла элементы 1,2,3,4,5, а другая - 6,7, 8,9,10.Возможно, у вас возникнет соблазн разделить его на 1,3,5,7,9 и 2,4,6,8,10, но тогда вы вызовете еще больше ложного обмена (http://en.wikipedia.org/wiki/False_sharing) в вашем кеше.

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

Так что в вашем случае я бы сделалчто-то вроде этого.

for (int t=0;t<n_processors;++t)
{
  thread[t]=create_thread();
  datamin[t]=t*(i_max/n_processors);
  datamax[t]=(t+1)*(i_max/n_processors);
}

for (int t=0;t<n_processors;++t)
  do_work(thread[t], datamin[t], datamax[t], j_max)

//wait for all threads to be done

//continue with rest of the program.

Конечно, я пропустил такие вещи, как работа с вашими данными, которые не являются целым кратным числом процессоров, но это легко исправить.

Кроме того, еслиВы не противостоите сторонним библиотекам, Intel TBB (многопоточные строительные блоки) отлично справляется с абстрагированием от вас и позволяет вам приступить к реальной работе, которую вы хотите сделать.

Answer 3

Избегайте создания потоков, если вы не можете их занять!

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

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

Answer 4

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

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

Тем не менее, наилучшее распараллеливание зависит от вашей реальной проблемы. В зависимости от этого может иметь смысл вместо этого распараллелить внутренний цикл.

Answer 5

Зависит от задач и на какой платформе вы собираетесь имитировать.Например, в архитектуре CUDA вы можете разделить задачи так, чтобы каждый i, j, 1. выполнялся индивидуально.

У вас все еще есть время для загрузки данных на карту для рассмотрения.

Используя циклы for и что-то вроде OpenMP / MPI / ваш собственный механизм потоков, вы можете выбрать.В одном сценарии параллельные потоки разрываются, и j последовательно зацикливается на каждом потоке.В другом случае цикл обрабатывается последовательно, и цикл прерывается при каждом распараллеливании.

Распараллеливание (разбиение потоков) является дорогостоящим.Помните, что у вас есть стоимость настройки n потоков, а затем синхронизации n потоков.Это представляет стоимость c сверх времени выполнения подпрограмм, которое само по себе может сделать общее время для параллельной обработки больше, чем в однопоточном режиме.Это зависит от рассматриваемой проблемы;часто есть критический размер, за пределами которого параллель быстрее.

Я бы посоветовал пробиться в параллельную зону в первом цикле for, который был бы быстрее.Если вы делаете это во внутреннем цикле, вы должны разветвляться / присоединяться при каждом запуске цикла, добавляя большие накладные расходы к скорости кода.В идеале вы хотите создавать потоки только один раз.