#c #openmp
#c #openmp
Вопрос:
Я использую алгоритм сита Эратосфена, чтобы найти простые числа до n. Идея состоит в том, чтобы отметить все кратные простому числу. Однако это не привело к увеличению производительности по мере увеличения количества потоков.
Для поиска простых чисел до 100000 потребовалось 0,009 секунды при использовании 100 потоков и 0,006 секунды при использовании 1 потока.
#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;
}
}
}
}
}
}
Комментарии:
1.
pragma omp parallel for?2. Возможно, @M.K. Директивы OP
omp forуже отображаются внутри параллельного раздела.3. Я считаю, что ваш код неверен. Вы пишете
list_of_numsс несколькими потоками за пределами критической секции. Может возникнуть условие гонки, еслиloop_index = 2оно выполняется thread1 иloop_index =3другим, поскольку оба могут записывать вloop_index[6]4. Использование 100 потоков, вероятно, излишне. Для кода, который не блокируется, количество потоков, превышающее количество ядер процессора, не дает никаких преимуществ. Но у них есть накладные расходы.
5. Ваш код неверен, независимо от того, дает он правильный результат или нет. Плохая производительность на самом деле является типичным результатом условий гонки. Тем не менее, нет смысла распараллеливать фрагмент кода, который изолированно занимает 6 мс.
Ответ №1:
Прежде всего, несмотря на все остальное, распараллеливание не гарантирует повышения скорости вашей программы. Управление несколькими потоками увеличивает накладные расходы на вычисления, и это может снизить ускорение, получаемое при одновременном выполнении нескольких вычислений.
Во-вторых, возможности для ускорения ограничены количеством параллелизма, которое может быть достигнуто. В частности, для вычислений, в которых нет блокирующих операций, вы не можете ожидать улучшения от добавления большего количества потоков, чем у вас есть независимые механизмы выполнения (грубо говоря, ядра).
Но в-третьих, и здесь я сосредоточусь на остальной части этого ответа, сито Эратосфена имеет зависимости от данных, которые делают его плохо подходящим для распараллеливания. То, что вы даже получаете правильные результаты от своей параллельной версии, обусловлено особыми особенностями вашей реализации. Проблема сосредоточена здесь:
if (list_of_nums[loop_index - 2] != -1) {
Это проверяет, было ли loop_index уже определено как составное, чтобы пропустить избыточное отсеивание его кратных. Ключевое слово там «уже». Если loop_index является составным, и для проверки его простых множителей были назначены потоки, отличные от текущего, то вы не можете быть уверены, что loop_index он уже помечен как составной.
У вас были бы проблемы, если бы вы выбирали простые числа в этот момент и сохраняли их в отдельном списке, как это обычно бывает с реализациями SofE. С другой стороны, ваша конкретная реализация, скорее всего, просто выполнит много ненужной работы, отсеивая кратные составные элементы. Таким образом, у вас не только накладные расходы, связанные с управлением несколькими потоками, но и, вероятно, вы будете выполнять больше общей работы. В этом смысле это не сито Эратосфена.
Можно написать параллельную версию SofE, которая правильно учитывает его зависимости от данных, хотя я не уверен, достаточно ли OpenMP богат, чтобы описать его. Я сделал это на другом языке, и он продемонстрировал некоторое ускорение. Но правильное соблюдение зависимостей значительно ограничивает объем доступного параллелизма (и увеличивает накладные расходы), поэтому ускорение было довольно слабым.
Обновление: возможные альтернативы
По результатам измерений вы знаете, что ваш параллельный подход имеет худшую производительность, чем базовый последовательный. Вы можете попытаться настроить параметры, такие как точное количество используемых потоков, но вам, вероятно, лучше пойти в другом направлении. Среди многообещающих альтернатив:
-
просто используйте последовательную версию вашего алгоритма. Согласно вашим измерениям, это сокращает время выполнения на 33%, что совсем не плохо.
-
предварительно вычислите свой список сит / праймов вместо того, чтобы вычислять его на лету. Тогда производительность вычислений не влияет на производительность вашего более крупного сервиса.
-
предварительно заполните сито, отметив кратные нескольким малым простым числам, параллельно и приняв задействованные избыточности, затем запустите оттуда стандартный последовательный SofE. Вероятно, вы захотите настроить количество известных простых чисел и потоков для использования в процессе предварительного заполнения, выполнив соответствующие измерения производительности для разных вариантов.
Кроме того, есть некоторые микрооптимизации, которые вы могли бы реализовать, чтобы (возможно) добиться небольшого ускорения даже по сравнению с серийной версией. Это имеет непосредственное отношение к вопросу, поэтому я не буду вдаваться в подробности здесь, но вы должны легко найти примеры в сети.
Комментарии:
1. Большое спасибо за такое подробное объяснение. Я действительно ценю это. Чтобы избежать выполнения большего количества работ, чем необходимо, лучше, если я уберу строку, на которой вы сосредоточились?
2. @SkipperLin, нет, лучше не удалять эту строку. Вы получаете от этого некоторое преимущество. Я хочу сказать, что распараллеливание дает вам гораздо меньше пользы, чем могло бы, если бы у алгоритма не было зависимости от данных, представленной этой строкой. Это способствует снижению производительности сети, о котором вы спрашивали. Один из ваших лучших (действительно!) альтернативой является просто не распараллеливать. Я обновил этот ответ несколькими другими.