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

Question

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Проблема решена! Я собираюсь подробно рассказать, как я решил эту проблему. Я снова использовал gprof, но на этот раз скомпилирован без флага оптимизации (-O3). Профилировщик сразу же указал, что я потратил невероятное количество времени на функцию, которая выполняет вычисления для каждой отдельной частицы: гораздо больше, чем в серийной версии.

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

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

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

Answer 1

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

Насколько тяжелы вычисления?

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

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

Answer 2

Ваш язык как бы показателен:

Подождите, ххх

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

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

Answer 3

profiling has not revealed much

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

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

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

Answer 4

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

Стоит выстрел в любом случае.

Answer 5

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

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

1. Вернуться к однопоточности.

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

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