Параллельная версия цикла не быстрее, чем последовательная версия
Я пишу программу в C++ для выполнения моделирования конкретной системы. В течение каждого такта самая большая часть выполнения поднимает единственным циклом. К счастью, это смущающе параллельно, таким образом, я решил использовать Потоки Повышения для параллелизации его (я работаю на 2 базовых машинах). Я ожидал бы в ускорении близко к 2 раза последовательной версии, так как нет никакой блокировки. Однако я нахожу, что нет никакого ускорения вообще.
Я реализовал параллельную версию цикла следующим образом:
- Разбудите два потока (они заблокированы на барьере).
Каждый поток затем выполняет следующее:
- Атомарно выберите и увеличьте глобальный счетчик.
- Получите частицу с тем индексом.
- Выполните вычисление на той частице, храня результат в отдельном массиве
- Ожидайте на законченном барьере задания
Основной поток ожидает на законченном барьере задания.
Я использовал этот подход, так как он должен обеспечить хорошее выравнивание нагрузки (так как каждое вычисление может занять отличающееся количество времени). Мне действительно любопытно относительно того, что могло возможно вызвать это замедление. Я всегда читал, что атомарные переменные быстры, но теперь я начинаю задаваться вопросом, есть ли у них свои затраты на производительность.
Если у кого-либо есть некоторые идеи, что искать или любые подсказки, я был бы очень признателен за его. Я колотил голову на нем в течение недели, и профилирование не показало много.
Править: Проблема решена! Я собираюсь детализировать, как я решил эту проблему. Я использовал gprof снова, но на этот раз скомпилировал без флага оптимизации (-O3). Сразу, профилировщик указал, что я проводил невероятное количество времени в функции, которая выполняет вычисление на каждой отдельной частице: намного больше, чем в последовательной версии.
Эта функция является виртуальной и получена доступ полиморфно. Я изменил код для доступа к нему непосредственно, а не через vtable, и вуаля' параллельная версия произвела ускорение почти 2! То же изменение на последовательной версии имело мало эффекта.
Я не уверен, почему это так и было бы интересно, если кто-либо знает!
Благодаря всем плакатам. Вы все помогли в некоторой степени, и будет очень трудно принять один ответ.
5 ответов
Выполните вычисления над этой частицей, сохранив результат в отдельном массиве
Насколько тяжелы вычисления?
- Вообще говоря, атомный счетчик может стоить сотни тактовых циклов, и очень важно следить, чтобы вы не только инкрементировали счетчики.
- Также попробуйте посмотреть, какой объем работы выполняет каждый поток - хорошо ли они взаимодействуют (т.е. на каждом цикле каждый выполняет примерно половину частицы).
- Попробуйте разделить задание на большие куски, а затем на одну частицу (допустим, 100 частиц и так далее).
- Посмотрите, сколько работы выполняется вне потоков.
Честно говоря... похоже, что то, о чем вы говорите, является ошибкой.
Ваш язык как бы откровенен:
Подождите xxx
, это может быть ваша проблема.
Кроме того, вы замедляетесь при повторном добавлении в одну очередь результатов - вы можете добавить результаты только в конце обработки в одну очередь, если это возможно. Основной поток не должен ждать, покупайте проверяйте глобальный счетчик после каждого обновления.
Вместо профилирования я бы добавил счетчики производительности, которые вы регистрируете в конце. Вы можете поместить их в условную ошибку компиляции, чтобы они не добавлялись в ваш производственный код.
Вы говорите, что профилирование мало что показало, и это (к сожалению) типично.
Вот что я бы сделал:
Вернуться к однопоточному.
Сделайте этот единственный поток как можно быстрее, используя этот метод профилирования, который работает на любом языке и в любой среде . Причина в том, что профилировщики (большинство, но не все) хороши только для измерения изменений , а не для точного определения того, что вам следует исправить .
Затем вернитесь к 1 потоку на ядро и повторите процесс снова. Если вы обнаружите, что один или другой поток тратит много времени на межпроцессное взаимодействие, вам необходимо переделать это.
Могу я предложить вам найти OpenMP проще для этого вид параллелизма? Поскольку вы просто хотите сделать цикл параллельным, вы действительно не хотите работать с потоками явно, и это именно та вещь, в которой OMP может быть действительно эффективным.
В любом случае стоит попробовать.
профилирование не выявило многого
Это неясно. У меня есть опыт профилирования многопоточного приложения на HP-UX, и там их профилировщик говорит о проценте времени выполнения каждой функции. Так что если у вас есть одна или несколько спорных точек в ваших функциях, вы получите увеличение времени, которое приложение проводит в этих функциях. В моем случае я получил значительное увеличение в pthread_mutex_unlock(). Когда я изменил свой код, он стал намного быстрее.
Так что не могли бы вы выложить здесь ту же статистику для одного потока и для двух/четырех потоков. И количество вычислений в каждом тесте.
Также я рекомендую вам (если это возможно) установить точку останова на глобальной функции, блокирующей мьютекс. Вы можете обнаружить, что где-то в вашем алгоритме вы случайно заблокировали глобальный мьютекс.