|
|
| (не показано 26 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| | + | Автор статьи: Николаев Владимир |
| | + | |
| | = Свойства и структура алгоритмов = | | = Свойства и структура алгоритмов = |
| | | | |
| | == Общее описание алгоритма == | | == Общее описание алгоритма == |
| − | '''Решето́ Эратосфе́на''' — алгоритм нахождения всех простых чисел до некоторого целого числа <math>n</math>. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от <math>2</math> до <math>n</math> и на каждом шаге убирает часть чисел, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии). | + | '''Решето́ Эратосфе́на''' — алгоритм нахождения всех простых чисел до некоторого целого числа <math>n</math>. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от <math>2</math> до <math>n</math> и на каждом шаге убирает часть из них, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии). |
| | | | |
| | == Математическое описание алгоритма == | | == Математическое описание алгоритма == |
| Строка 8: |
Строка 10: |
| | | | |
| | # Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math> | | # Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math> |
| − | # Положим <math>p = 2</math> | + | # Берется <math>p = 2</math> |
| − | # Зачеркиваются числа от <math>2p</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</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> | | # Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math> |
| | # Повторяются шаги 3 и 4 пока возможно | | # Повторяются шаги 3 и 4 пока возможно |
| | | | |
| − | На практике на шаге 3 зачеркивать числа можно начиная с <math>p^2</math>, и, соответственно алгоритм заканчивает свою работу при <math>p^2 > n</math>.
| + | Соответственно алгоритм заканчивает свою работу при <math>p^2 > n</math>. |
| | | | |
| | == Вычислительное ядро алгоритма == | | == Вычислительное ядро алгоритма == |
| − | Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность составляет <math>O(nlog(log(n)))</math>. | + | Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность алгоритма составляет <math>O(nlog(log(n)))</math>. |
| | | | |
| | == Макроструктура алгоритма == | | == Макроструктура алгоритма == |
| − | Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.
| + | Алгоритм можно разбить на 2 части: |
| − | | + | # Первая часть — создается и заполняется единицами булев массив длины <math>n</math> |
| − | Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
| + | # Вторая часть — последовательно рассматривается каждое, еще не помеченное число, и с помощью него производится фильтрация бо́льших чисел |
| − | Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.
| |
| | | | |
| | == Схема реализации последовательного алгоритма == | | == Схема реализации последовательного алгоритма == |
| − | Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.
| + | Псевдокод вычислительного ядра алгоритма: |
| | | | |
| − | Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.
| + | '''Вход''': натуральное число ''n'' |
| − | | + | |
| − | Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.
| + | Пусть ''A'' — булев массив, индексируемый числами от 2 до ''n'', изначально заполненный значениями '''true'''. |
| | + | |
| | + | '''для''' ''i'' := 2, 3, 4, ..., '''пока''' ''i''<sup>2</sup> ≤ ''n'': |
| | + | '''если''' ''A''[''i''] = '''true''': |
| | + | '''для''' ''j'' := ''i''<sup>2</sup>, ''i''<sup>2</sup> + ''i'', ''i''<sup>2</sup> + 2''i'', ..., '''пока''' ''j'' ≤ ''n'': |
| | + | ''A''[''j''] := '''false''' |
| | + | |
| | + | '''Выход''': числа ''i'', для которых ''A''[''i''] = '''true'''. |
| | | | |
| | == Последовательная сложность алгоритма == | | == Последовательная сложность алгоритма == |
| − | В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.
| + | Сложность алгоритма складывается из двух составляющих. Первое — выписывание всех чисел от <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»<ref>[https://archive.org/stream/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright#page/n363/mode/2up Hardy and Wright "An Introduction to the Theory of Numbers, p. 349]</ref>. |
| − | | |
| − | Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].
| |
| − | | |
| − | Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).
| |
| | | | |
| | == Информационный граф == | | == Информационный граф == |
| − | Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.
| + | Информационный граф рассматриваемого алгоритма: |
| − | | + | [[Файл:Graph_eratosthenes_sieve.png|thumb|center|]] |
| − | Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.
| |
| − | | |
| − | В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.
| |
| − | | |
| − | Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.
| |
| − | | |
| − | В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.
| |
| − | | |
| − | На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.
| |
| − | | |
| − | [[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]] | |
| − | [[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]
| |
| | | | |
| | == Ресурс параллелизма алгоритма == | | == Ресурс параллелизма алгоритма == |
| − | Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.
| + | Вычислительное ядро алгоритма можно распараллелить, но не полностью. Разобьем все натуральные числа <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.5]]) вполне может быть использован и для отражения ресурса параллелизма.
| |
| − | | |
| − | Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.
| |
| − | | |
| − | Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.
| |
| | | | |
| | == Входные и выходные данные алгоритма == | | == Входные и выходные данные алгоритма == |
| − | В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.
| + | Входные данные алгоритма — одно число <math>n</math>, до которого нужно найти все простые числа. На выходе алгоритм выдает либо булев массив длины <math>n</math>, отражающий для каждого натурального числа, является ли оно простым, либо список простых чисел от <math>2</math> до <math>n</math> (что конкретно — зависит от реализации и не имеет особого значения). |
| | | | |
| | == Свойства алгоритма == | | == Свойства алгоритма == |
| Строка 77: |
Строка 63: |
| | | | |
| | == Масштабируемость алгоритма и его реализации == | | == Масштабируемость алгоритма и его реализации == |
| − | Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.
| + | Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. |
| | | | |
| − | Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).
| + | График сильной масштабируемости: |
| | | | |
| − | Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи <ref>Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.</ref>. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.
| + | [[File:Strong_scaling_sieve.png]] |
| | | | |
| − | На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
| + | Число, до которого нужно искать простые числа, <math> n = 10^7 </math>. По графику видно, что распараллеливание дает выигрыш в скорости выполнения, но с увеличением числа используемых ядер, этот выигрыш все меньше. Это связано с лишними накладными расходами. |
| − | [[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи]] | + | |
| | + | |
| | + | График слабой масштабируемости: |
| | + | |
| | + | [[File:Weak_scaling_sieve.png]] |
| | + | |
| | + | При одном процессе, число <math> n \approx 5000000 </math>. Видно, что при фиксированном отношении сложности задачи к числу процессов, время решения задачи растет. Это связано с тем, что при распараллеливании появляются дополнительные накладные расходы, а так же с тем, что задача распараллеливается не полностью. При увеличении сложности задачи в <math> 64 </math> раза (и одновременно числа процессов, потому что производилось исследование слабой масштабируемости), время выполнения увеличилось в <math> 5 </math> раз. |
| | | | |
| | == Динамические характеристики и эффективность реализации алгоритма == | | == Динамические характеристики и эффективность реализации алгоритма == |
| Строка 92: |
Строка 84: |
| | | | |
| | == Существующие реализации алгоритма == | | == Существующие реализации алгоритма == |
| − | Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.
| + | Однопоточные реализации с различными улучшениями: |
| | + | # Однопоточная реализация: 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 |
| | | | |
| | = Литература = | | = Литература = |
Автор статьи: Николаев Владимир
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.
