Плохое ускорение с быстрой сортировкой в ​​параллельном режиме libstdc++

Я не могу получить ускорение выше 2 с алгоритмами сортировки на месте (быстрая сортировка и сбалансированная быстрая сортировка; QS/BQS) из параллельной реализации libstdС++ (параллельный режим). Я пробовал запускать код на множестве разных систем, состоящих из 16-24 ядер. Я также пробовал компиляторы GNU и Intel C++, даже в разных версиях, всегда с одинаковыми результатами. Ускорение около 2 одинаково для любого количества ядер от 2 до макс.

Напротив, многосторонняя сортировка слиянием (MWMS) хорошо масштабируется (ускорение около 10 при использовании 16 потоков на 16-ядерной машине). Согласно презентации Дж. Синглера "Параллельный режим GNU libstdc++: преимущества многоядерного использования STL", их измеренное ускорение для BQS почти такое же, как для MWMS (см. стр. 18, http://ls11-www.cs.uni-dortmund.de/people/gutweng/AD08/VO11_parallel_mode_overview.pdf); они наблюдали ускорение более чем в 20 раз при использовании BQS с 32 потоками.

Любая идея, почему это происходит или что я не так?


c++ parallel-processing quicksort c++-standard-library libstdc++
person Daniel Langr    schedule 21.04.2015    source источник
comment
Вы вызываете omp_set_num_threads(), чтобы установить количество потоков, которые он должен использовать? gcc.gnu.org/onlinedocs/libstdc++/manual/   -  person NathanOliver    schedule 21.04.2015
comment
Да, есть (иначе и с MWMS не было бы ускорения).   -  person Daniel Langr    schedule 21.04.2015
comment
Это может быть очевидно, но проверили ли вы, чтобы поставить флаг openmp?   -  person coincoin    schedule 21.04.2015
comment
@coincoin: вы имеете в виду флаг компилятора? Да, у меня есть. Я использую один и тот же исходный код и одну и ту же процедуру сборки во всех трех случаях (QS, BQS и MWMS). Более того, без флага openmp, вероятно, не было бы ускорения, но я наблюдаю, что ускорение равно 2.   -  person Daniel Langr    schedule 21.04.2015
comment
@NathanOliver: Спасибо, что напомнили мне руководство. Я видел это много раз, но до сих пор мне не приходило в голову попытаться позвонить omp_set_nested().   -  person Daniel Langr    schedule 21.04.2015

Ответы (1)


arrow_upward
2
arrow_downward

Я, казалось бы, решил проблему, просто позвонив:

omp_set_nested(1);

Документация немного неясна в отношении этого требования. Более того, я бы ожидал, что библиотека сама сможет выполнить вызов. Надеюсь, это поможет и кому-то еще.

person Daniel Langr    schedule 21.04.2015