Не удалось улучшить производительность во вложенном цикле for в openmp

Question

Я делаю алгоритм Эратосфена, чтобы найти простые числа до n. Идея состоит в том, чтобы выделить все кратные простого числа. Однако это не привело к увеличению производительности при увеличении количества потоков.

Это стоило 0,009 секунд, используя 100 потоков, и 0,006 секунд, используя 1 поток, чтобы найти простые числа до 100000.

#pragma omp parallel num_threads(t)
{
    #pragma omp for
    for (int index = 2; index <= N; index++) {
        list_of_nums[index - 2] = index;
    }

    #pragma omp for
    for (int loop_index = 2; loop_index <= num_to_stop; loop_index++) {
        if (list_of_nums[loop_index - 2] != -1) {
            for (int mark_index = loop_index - 2; mark_index < N - 1; mark_index += loop_index) {
                if (mark_index != loop_index - 2) {
                    if (list_of_nums[mark_index] % loop_index == 0) {
                        list_of_nums[mark_index] = -1;
                    }
                }
            }
        }
    }
}

Answer 1

Прежде всего, несмотря на все остальное, распараллеливание не гарантирует повышения скорости вашей программы. Управление несколькими потоками увеличивает накладные расходы на вычисления, и это может сокрушить ускорение, полученное при одновременном выполнении нескольких вычислений.

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

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

        if (list_of_nums[loop_index - 2] != -1) {

Это проверяет, был ли loop_index уже определен как составной, чтобы пропустить избыточное просеивание его кратных чисел. Ключевое слово там "уже". Если loop_index является составным, а потоки, отличные от текущего, были назначены для проверки его основных факторов, то вы не можете быть уверены, что loop_index уже был помечен составным.

У вас возникли бы проблемы, если бы вы в этот момент выбирали простые числа и хранили их в отдельном списке, как это часто бывает в реализациях SofE. С другой стороны, ваша конкретная реализация, скорее всего, сделает много ненужной работы, отсеивая множество композитов. Таким образом, не только у вас возникают накладные расходы, связанные с управлением несколькими потоками, но вы, вероятно, будете выполнять больше общей работы. В этом смысле это не Сито Эратосфена.

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

Обновление: возможные альтернативы

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

• просто используйте последовательную версию вашего алгоритма. Согласно вашим измерениям, это сокращает время работы на 33%, что совсем не плохо.

• предварительно вычисляйте список сит / прайм вместо того, чтобы вычислять его на лету. Тогда производительность вычислений не будет влиять на производительность вашего более крупного сервиса.

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

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