6 / 9
наиболее эффективен с точки зрения использования аппаратных ре-
сурсов каждого узла многопроцессорной системы.
При написании программы авторы воспользовались открытым
стандартом OpenMP для реализации взаимодействия потоков, рабо-
тающих на одном узле. Реализация взаимодействий между узлами
свелась к назначению каждому узлу своего отрезка натурального ряда
и сбору данных, поступающих после обработки.
Другие подходы к модификации индексного алгоритма.
1.
Предпросев
: выполняется для заранее известных малых простых
чисел.
2.
Блочный подход
: для значительного ускорения работы алгоритма
происходит разбивка заданного отрезка натурального ряда на сегмен-
ты таким образом, чтобы при работе над одним из них занимаемая
память не превышала размеров кэша процессора 1-го уровня.
3.
Битовые массивы
: в таблице кольцевой факторизации третьего
порядка ровно 8 ячеек, и очень удобно одну строку кодировать одним
байтом, а для того чтобы отметить какое-либо число в строке как
составное, нужно эту строку умножить на байт, состоящий из единиц
и нуля на соответствующем месте.
4.
Использование специализированных алгоритмов
для чисел раз-
ных порядков: больше размера сегмента (встречаются один раз или
не встречаются вообще), порядка размера сегмента (встречаются не-
сколько раз), и все остальные, т.е. меньшие, чем размер сегмента.
Изложенный алгоритм реализован на языке программирования
C/C++ с использованием открытого исходного кода проекта
http://primesieve.org, в котором авторы использовали оптимизирован-
ное решето Эратосфена. Далее алгоритм модифицирован до индексно-
го и проведено его исследование на быстродействие на вычислитель-
ном кластере в МГТУ им. Н.Э. Баумана, располагающем 25 узлами
Intel Xeon 5120 1.86 GHz с 4 ядрами каждый.
На рисунке приведены результаты о времени работы алгоритма для
отрезков натурального ряда от единицы до значения на оси абсцисс
при различных числах потоков на одном узле. На рисунке видно, что
для исследованной части натурального ряда до
10
12
при увеличении
числа ядер время работы индексного алгоритма сокращается соответ-
ственно на 46% для двух, на 58% — для трех и на 63% — для четырех
ядер.
Результаты следующие: для вычисления всех простых чисел до
10
15
потребовалось 504 ч работы в пересчете на один узел, до
2
∙
10
15
—
1032 ч, а до
3
∙
10
15
— 1584 ч. При вычислениях на всех доступных 25
узлах вычислительных ресурсов потребовалось соответственно 20, 42
и 64 ч реального времени.
Выводы.
Индексный алгоритм в его текущей реализации пред-
ставляет собой принципиально новый подход к поиску простых чисел.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6 87