Распараллеливание больших циклов и улучшение доступа к кешу - PullRequest
Новая
       4

Распараллеливание больших циклов и улучшение доступа к кешу

1 голос
/ 12 сентября 2011

У меня есть код, подобный следующему, который я использую для нахождения простых чисел (используя сито Эратосфена) в диапазоне и использую OpenMP для распараллеливания.Перед этим у меня есть этап предварительной обработки, на котором я отмечаю все четные числа и кратные 3 и 5, так что на этом этапе мне приходится выполнять меньше работы.Общий кэш L3 тестового стенда составляет 12 МБ, а физическая память - 32 ГБ.Я использую 12 потоков.Массив flag равен unsigned char. 

#pragma omp parallel for
for (i = 0; i < range; i++)
{
     for (j = 5; j < range; j+=2)
     {
         if( flag[i] == 1 && i*j < range )
             if ( flag[i*j] == 1 )
                 flag[i*j] = 0;
      }
 }

. Эта программа хорошо работает для диапазонов менее 1 000 000 ... но после этого время выполнения увеличивается для больших диапазонов;Например, для range = 10,000,000 эта программа занимает около 70 минут (не помещается в кэш?).Я изменил вышеупомянутую программу, чтобы включить мозаику циклов, чтобы она могла использовать кэш для любого диапазона циклов, но даже подход с блокировкой кажется трудоемким.Чередование циклов также не помогает для больших диапазонов.

Как изменить приведенный выше код для работы с большими диапазонами?И как я могу переписать код, чтобы сделать его полностью параллельным (range и flag [так как массив flag довольно большой, поэтому я не могу объявить его закрытым] является общим)?

1 Ответ

2 голосов
/ 12 сентября 2011

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

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

Я предлагаю это, потому что вы упомянули, что это займет 70 минут.на (довольно мощной) машине для запуска N = 10,000,000.Это выглядело неправильно, так как моя собственная тривиальная реализация может выполнить N = 2^32 менее чем за 20 секунд на ноутбуке - однопоточное, без оптимизации на уровне источника.Тогда я заметил, что вы пропустили несколько основных оптимизаций.

Вот эффективное решение.Но для этого нужно проделать определенную работу.

Ключ в том, чтобы понять, что сите Эратосфена нужно только подняться до sqrt (N) вашего целевого размера.Другими словами, вам нужно только запустить сито на всех простых числах до sqrt (N), прежде чем вы закончите.

Таким образом, хитрость заключается в том, чтобы сначала запустить алгоритм на sqrt (N).Затем выведите все простые числа в плотную структуру данных.Предварительно вычисляя все необходимые простые числа, вы нарушаете зависимость от внешнего цикла.

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

Чтобы быть эффективным, это должно быть сделано с использованием "мини" сит на блоках, которые помещаются в кэш.Чтобы быть еще более эффективным, вы должны вычислить и кэшировать взаимные значения всех простых чисел в таблице.Это поможет вам эффективно найти «начальные смещения» каждого простого числа при заполнении каждого «мини-сита».

Начальный шаг запуска алгоритма, последовательного для sqrt (N), будет очень быстрым, так как онтолько sqrt (N).Остальная часть работы полностью распараллеливается.

В полностью общем случае этот алгоритм может быть применен рекурсивно к начальному сите, но это, как правило, излишне.

...