Параллельная версия цикла не быстрее, чем серийная версия

Question

Я пишу программу на C++ для моделирования конкретной системы. Для каждого временного интервала большая часть выполнения занимает один цикл. К счастью, это смущает параллель, поэтому я решил использовать Boost Threads для его распараллеливания (я работаю на двухъядерном компьютере). Я ожидаю, что при ускорении будет близка к 2-кратной серийной версии, так как нет блокировки. Однако я нахожу, что ускорения вообще нет.

Я реализовал параллельную версию петли следующим образом:

• разбудить две нити (они заблокированы на барьер).

• Каждый поток затем выполняет следующие действия:

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

• Основные поток ожидает заданий законченного барьера.

Я использовал этот подход, поскольку он должен обеспечивать хорошую балансировку нагрузки (поскольку каждое вычисление может занимать разные промежутки времени). Мне очень любопытно, что может привести к этому замедлению. Я всегда читал, что атомные переменные бывают быстрыми, но теперь я начинаю задаваться вопросом, имеют ли они свои эксплуатационные издержки.

Если у кого-то есть идеи, что искать или какие-либо намеки, я бы очень признателен. Я пробивал себе голову на неделю, и профилирование не показало много.

EDIT: проблема решена! Я расскажу, как я решил эту проблему. Я снова использовал gprof, но на этот раз скомпилирован без флага оптимизации (-O3). Сразу же профайлер указал, что я проводил невероятное количество времени в функции, которая выполняет вычисления на каждой отдельной частице: намного больше, чем в серийной версии.

Эта функция является виртуальной и доступ к ней осуществляется полиморфно. Я изменил код, чтобы получить доступ к нему напрямую, а не через vtable и voila. Параллельная версия произвела ускорение почти на 2! Такое же изменение в серийной версии мало повлияло.

Я не уверен, почему это так, и было бы интересно, если кто-нибудь знает!

Спасибо всем плакатам. Вы все помогли в некоторой степени, и будет очень сложно принять один ответ.

Answer 1

Выполните вычисление на этой частицы, сохраняя результат в отдельном массиве

Как тяжелы вычисления?

• Вообще говоря атомарный счетчик может стоить сотни тактов, и это очень важно, чтобы видеть, что вы не только увеличивают значения счетчиков.
• Также попробуйте посмотреть, сколько работы выполняют каждая нить - они хорошо взаимодействуют (т. Е. На каждый цикл каждый продолжается примерно половиной частицы).
• Попробуйте разделить работу на более крупные куски, а затем на частицу (скажем, 100 частиц и т. Д.).
• Посмотрите, как много работы выполняется за пределами потоков.

Честно говоря ... похоже, что вы говорите, это ошибка.

Answer 2

profiling has not revealed much

Это неясно. У меня есть опыт профилирования многопоточного приложения на HP-UX, и там их профайлер говорит, что процент времени каждой функции работает. Поэтому, если у вас есть одна или несколько точек соперничества в ваших функциях, вы получаете увеличение времени, которое ваше приложение тратит на эти функции. В моем случае я получил значительное увеличение в pthread_mutex_unlock(). Когда я сменил код, он стал намного быстрее.

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

Также я рекомендую вам (если возможно) установить точку останова для глобальной функции, блокирующей мьютекс. Вы можете обнаружить, что где-то в вашем алгоритме вы случайно блокируете глобальный мьютекс.

Answer 3

Вы говорите, что профилирование не выявило много, и это (к сожалению) типично.

Вот что я хотел бы сделать:

1. Вернуться к Однозаходному.

2. Сделайте эту нить как можно быстрее, используя this profiling technique that works in any language and environment. Причина в том, что профилировщики (большинство, но не все) хороши только в , измеряя изменения, а не , определяя, что вы должны исправить.

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

Answer 4

Ваш язык вид выявления:

Подождите на ххх

это может быть вашей проблемой.

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

Answer 5

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

Оцените это как можно скорее.