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

StackOverflow https://stackoverflow.com/questions/2636746

Вопрос

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

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

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

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

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

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

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

Другие советы

profiling has not revealed much

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

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

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

Ваш язык является родом раскрытия:

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

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


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

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

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

  1. Вернитесь к однотонному.

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top