OpenMP (параллельный для) в g++ 4.7 не очень эффективен? 2,5x при 5x процессоре

Question

Я пытался использовать OpenMP с одним #pragma omp parallel forи это привело к тому, что моя программа перешла из режима работы 35 с (99,6% ЦП) в 14 с (500% ЦП), работая на процессоре Intel® R Xeon® E3-1240 v3 @ 3,40 ГГц. В этом разница между компиляцией с g++ -O3 а также g++ -O3 -fopenmpкак с gcc (Debian 4.7.2-5) 4.7.2 на Debian 7 (wheezy).

• Почему он использует максимум 500% ЦП, тогда как теоретический максимум составляет 800%, поскольку ЦП состоит из 4 ядер / 8 потоков? Разве это не должно достигать минимум 700-х?

• Почему я получаю только 2,5-кратное улучшение общего времени, но при этом загрузка процессора увеличивается в 5 раз? Кэш побеждает?

Вся программа основана на C++ string манипулирование, с рекурсивной обработкой (используя много .substr(1) и некоторую конкатенацию), где указанные строки непрерывно вставляются в vector из set,

Другими словами, в принципе, в одной параллели для цикла, работающего на vectorи каждый из них может сделать два рекурсивных вызова сам с некоторыми string.substr(1) а также + char конкатенация, а затем рекурсия заканчивается set.insert либо одной строки или конкатенации двух строк, и сказал set.insert также заботится о значительном количестве дубликатов, которые возможны.

Все работает правильно и в рамках спецификации, но я пытаюсь увидеть, может ли он работать быстрее.:-)

Answer 1

На основании вашего описания вы можете сделать следующие выводы:

^{Я предполагаю, что OpenMP действительно использует 8 потоков (проверьте} export OMP_NUM_THREADS=8 ⁾

1. 500% CPU означает, что в барьерах много времени. Это связано с плохим балансом нагрузки: разные итерации занимают разное количество времени. Следовательно, планирование по умолчанию (статическое) неэффективно, попробуйте различные виды планирования цикла, например dynamic ,

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

   • Наиболее распространенным общим ресурсом является пропускная способность памяти. Влияет ли это на вас, зависит от того, вписывается ли ваш рабочий набор в локальные кэши. Учитывая многие иерархии памяти и свойства NUMA в современных системах, это может стать очень сложным для понимания. Ничего фундаментального, что вы можете сделать против реструктуризации доступа к данным для более эффективного использования кэшей (блокирование).

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

   • HyperThreading - ядро, являющееся общим ресурсом между двумя аппаратными потоками.

     используя 5x ресурсы

     Это фундаментальное недоразумение. Дополнительный аппаратный поток предоставляет мало дополнительных ресурсов каждому ядру. Если два потока работают на одном и том же ядре, они будут совместно использовать вычислительные ресурсы и пропускную способность памяти, в основном единственным преимуществом является скрытая задержка ввода-вывода. Вы никогда не увидите 2-кратное ускорение, несмотря на 2-кратное время процессора. Иногда это даст вам ускорение на 10%, иногда будет медленнее.

     Теперь рассмотрим 5 активных потоков, работающих на 4 ядрах. 2 потока, совместно использующие ядро, будут работать только на скорости ~50%, замедляя все. Попробуйте уменьшить количество потоков до количества ядер (export OMP_NUM_THREADS=4).

Answer 2

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

1. Ложное совместное использование: если массив не разделен должным образом, строка кэша может конфликтовать между двумя ядрами, обычно две половины строки кэша записываются двумя потоками, в результате чего строка кэша перемещается из кэша L2 одного ядра в Другой. Совместное использование кэша также может произойти, если вы используете много shared переменные. В этом случае рассмотрите возможность использования private или же firstprivate чтобы избежать синхронизации.
2. Планирование OpenMP: если не указано, OpenMP будет разделять итерации цикла равным образом среди потоков в системе и назначать поддиапазон каждому из них. Однако, если объем работы для каждого индекса варьируется, вы можете оказаться в ситуации, когда большинство потоков завершают свою работу, и они блокируются на барьере в конце параллельной области, ожидая более медленный поток (тот, который получил больше работы). Это зависит от типа алгоритма, который вы реализовали в цикле, но OpenMP дает вам возможность изменить политику планирования, используя schedule() директивы. Рассмотреть возможность dynamic по крайней мере.