Время выполнения увеличивается, чем больше потоков я использую OpenMP, что не так?

Question

Я написал программу, которая берет словарь и находит все слова в словаре, которые являются палиндромами. Я попытался распараллелить прохождение этого словаря и выполнение логики c, которая проверяет, является ли слово палиндромом, используя OpenMP. Однако, когда я заметил, что время выполнения увеличивается, я позволяю программе использовать все больше и больше потоков. Что может быть объяснением этого? Есть ли ошибка в моем коде?

#pragma omp parallel    //block of code that we want to execute using multiple threads
#pragma omp single  //we only want one thread to iterate through the foor loop and spawn tasks for the other threads
{
    #pragma omp task untied     /* iterating through the for loop is the main task, so 
                     * burden should be shared if execution is suspended
                     */
    {
        for (set<string>::iterator i = wordList.begin(); i != wordList.end(); ++i){
        #pragma omp task    //spawn the tasks of evaluating whether each word should be inserted into palindrome list
            {
                if (isPalindrome(*i)){  //if the word is by itself a palindrome, insert
                    palindromes.insert(*i);
                }
                /* if the reverse of the current word is in the wordlist and it hasn't already been inserted,
                 * insert them both into set of palindromes
                 */ 
                else if (wordList.find(reverseWord(*i)) != wordList.end()){
                    if(palindromes.find(*i) == palindromes.end()){
                        palindromes.insert(*i);
                        palindromes.insert(reverseWord(*i));
                    }
                }
            }
        }
    }
}

Я использую вызов omp_set_num_threads (Argv [1]) для изменения максимально допустимых потоков времени выполнения. Я выполняю эту программу на суперкомпьютере, поэтому не думаю, что проблема в том, что мой компьютер перегружен или что-то в этом роде. Что дает? Я неправильно понял, как использовать OpenMP? Я использую два вызова omp_get_wtime () прямо перед и после этого блока кода для измерения времени выполнения.

РЕДАКТИРОВАТЬ: и палиндромы, и wordList являются std :: set, isPalindrome проверяет, является ли слово палиндромом, посредством манипулирования указателем , reverseWord возвращает слово обратный символ для символа (для этой задачи палиндром также является словом, обратное слово которого находится в списке слов, например, saw - was.

Answer 1

Компенсирует ли количество вычислений (циклов ЦП), которое выполняет каждая задача, работу, выполненную для их порождения?

Я мог бы предложить использовать #pragma omp parallel for для задач здесь, поскольку ваш набор слов имеет фиксированный размер в течение всей операции. Однако проблема заключается в критических сеансах при вставке слова в список palindromes.

Answer 2

На основании описания (в настоящее время) отсутствующего кода проблема заключается в том, что вы постоянно создаете новые string объекты для передачи в isPalindrome и другие места. Каждая копия строки приводит к выделению памяти (и последующему освобождению), а стандартный распределитель памяти не является реентерабельным и блокирует один поток, если другой в настоящее время выделяет.

Одним частичным решением является передача параметра в isPalindrome как const std::string &, что позволит избежать копирования. reverseWord будет немного более проблематичным c в этом отношении, так как он должен вернуть измененную строку, но параметр все еще может быть передан по ссылке.