Участник:Vvnikolaev/Решето Эратосфена
Автор статьи: Николаев Владимир
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа [math]n[/math]. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от [math]2[/math] до [math]n[/math] и на каждом шаге убирает часть из них, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии).
1.2 Математическое описание алгоритма
Пусть требуется найти все простые числа от [math]2[/math] до [math]n[/math]. Алгоритм состоит из следующих шагов:
- Выписываются подряд все натуральные числа от [math]2[/math] до [math]n[/math]
- Берется [math]p = 2[/math]
- Зачеркиваются числа от [math]p^2[/math] до [math]n[/math] с шагом [math]p[/math] (то есть все числа от [math]2[/math] до [math]n[/math], кратные [math]p[/math], кроме него самого)
- Ищется первое не зачеркнутое число в списке, превышающие [math]p[/math], и это значение присваивается переменной [math]p[/math]
- Повторяются шаги 3 и 4 пока возможно
Соответственно алгоритм заканчивает свою работу при [math]p^2 \gt n[/math].
1.3 Вычислительное ядро алгоритма
Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность алгоритма составляет [math]O(nlog(log(n)))[/math].
1.4 Макроструктура алгоритма
Алгоритм можно разбить на 2 части:
- Первая часть — создается и заполняется единицами булев массив длины [math]n[/math]
- Вторая часть — последовательно рассматривается каждое, еще не помеченное число, и с помощью него производится фильтрация бо́льших чисел
1.5 Схема реализации последовательного алгоритма
Псевдокод вычислительного ядра алгоритма:
Вход: натуральное число n Пусть A — булев массив, индексируемый числами от 2 до n, изначально заполненный значениями true. для i := 2, 3, 4, ..., пока i2 ≤ n: если A[i] = true: для j := i2, i2 + i, i2 + 2i, ..., пока j ≤ n: A[j] := false Выход: числа i, для которых A[i] = true.
1.6 Последовательная сложность алгоритма
Сложность алгоритма складывается из двух составляющих. Первое — выписывание всех чисел от [math]2[/math] до [math]n[/math]. Это, очевидно, делается за [math]O(n)[/math]. Вторая составляющая — повторение шагов 3 и 4 — вычислительное ядро алгоритма. Сложность этой части составляет [math]O(nlog(log(n)))[/math]. Строгое доказательство этого факта можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[1].
1.7 Информационный граф
Информационный граф рассматриваемого алгоритма:
1.8 Ресурс параллелизма алгоритма
Вычислительное ядро алгоритма можно распараллелить, но не полностью. Разобьем все натуральные числа [math]\{2, \dots, n\}[/math] на 2 множества — [math]\{2, \dots, \sqrt n\}[/math] и [math]\{\sqrt n + 1\dots, n\}[/math]. Поиск простых чисел на первом множестве распараллелить нельзя, а на втором — можно (различия заключаются в том, что числа из второго множества не будут проверяться в качестве делителей — они все больше [math] \sqrt n [/math]). Поэтому проверка на простоту для первого множества будет выполняться на каждом потоке, а второе можно разбить на [math]p[/math] частей ([math]p[/math] — количество процессов) и проверять каждую часть на простоту отдельно. Так как первая часть при больших [math]n[/math] значительно меньше второй, то можно предположить, что параллельное выполнение даст хороший прирост к скорости.
1.9 Входные и выходные данные алгоритма
Входные данные алгоритма — одно число [math]n[/math], до которого нужно найти все простые числа. На выходе алгоритм выдает либо булев массив длины [math]n[/math], отражающий для каждого натурального числа, является ли оно простым, либо список простых чисел от [math]2[/math] до [math]n[/math] (что конкретно — зависит от реализации и не имеет особого значения).
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Исследование проводилось на суперкомпьютере "Ломоносов"[2] Суперкомпьютерного комплекса Московского университета.
График сильной масштабируемости:
Число, до которого нужно искать простые числа, [math] n = 10^7 [/math]. По графику видно, что распараллеливание дает выигрыш в скорости выполнения, но с увеличением числа используемых ядер, этот выигрыш все меньше. Это связано с лишними накладными расходами.
График слабой масштабируемости:
При одном процессе, число [math] n \approx 5000000 [/math]. Видно, что при фиксированном отношении сложности задачи к числу процессов, время решения задачи растет. Это связано с тем, что при распараллеливании появляются дополнительные накладные расходы, а так же с тем, что задача распараллеливается не полностью. При увеличении сложности задачи в [math] 64 [/math] раза (и одновременно числа процессов, потому что производилось исследование слабой масштабируемости), время выполнения увеличилось в [math] 5 [/math] раз.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Однопоточные реализации с различными улучшениями:
- Однопоточная реализация: http://e-maxx.ru/algo/eratosthenes_sieve
- Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear
Многопоточные реализации:
- https://github.com/keyfunda/primes-parallel-sieve
- https://github.com/Heliosmaster/BSPEratosthenes
- https://github.com/marius92mc/sieve-of-eratosthenes-with-MPI
3 Литература
- ↑ Hardy and Wright "An Introduction to the Theory of Numbers, p. 349
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.