Prime sieving

[Hamster]

Не столько головоломка, сколько задача для кодеров-оптимизаторов на познавание аппаратуры, с которой вы работаете.

Задача 1.1. Найти все простые числа в интервале от 10^16 до 10^16+10^11.
Задача 1.2. То же самое, в интервале от 10^19 до 10^19+10^11.

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

Можно предположить, что у нас есть файл, содержащий все простые числа в интервале от 0 до 2^32.

У меня есть код, который решает 1.1 за 500 секунд и 1.2 за 840 секунд на Intel Core i7 920 с 8 гигабайтами стандартной памяти triple-channel DDR1066. Можете ли вы написать программу, которая будет работать быстрее?

[venco]

Дык, скорость от процессора сильно зависит.

[venco]

Моя 32-битная программа на Core 2 Duo (2.6 GHz) считает 1.1 быстрее 500 секунд. Точное время сейчас сказать не могу, т.к. машина слегка загружена, а размер доступного кеша существенно влияет на скорость (почти линейно). Кстати, у меня кеш 4 МБ, а у Вас - 8МБ.
Чтобы посчитать 1.2 надо переписать программу на 64-бита, а я подозреваю, что для этого и ось 64-битная нужна. Отставить. 10^19 влезают в 64 бита.
Но программу всё равно модифицировать надо, т.к. сейчас для 1.2 ей нужно больше 1 GB памяти - ограничение CygWin.

[Hamster]

Быстрее 500 секунд на двух ядрах? Интересно. Или у меня неоптимально выбраны константы (все 8 МБ L3 я не использую, вроде видел замедление при выходе за пределы L2, которого 256 КБ на ядро), или кто-то из нас потерял (нашел) лишний ноль. Сейчас посмотрим...

Если есть свободное место на диске и USB drive, 64-битная ось под названием Ubuntu ставится за 15 минут. Потом можно тестировать одну и ту же программу на разных машинах, просто копируя бинарник на тот же USB drive и загружаясь с него.

[venco]

У меня на одном ядре, оптимальный блок - 3.5 МБ (весь кеш 4 МБ).

[venco]

Можно сравнить результаты. В диапазоне 1.1 - 2714336584 простых.

[Hamster]

Можно сравнить результаты. В диапазоне 1.1 - 2714336584 простых.

Да.

[Hamster]

ОК, нашел одну пропущенную оптимизацию, получается 475 секунд на одном ядре и 170 на четырех ядрах.

Что касается размера блока: дело в том, что ваши 4 мегабайта это L2, а мои 8 мегабайт это L3, к которым скорость доступа (latency) в архитектуре Core i7 в 2-3 раза ниже. Хитро...

[Hamster]

Все аспекты задачи 1.2 для района 10^19 мы так и не раскрыли.

Тонкость в 10^19 в том, что корень квадратный из 10^19 заметно больше и L2, и L3, а значит, работа с 4 мб блоками означает большое число ненужных операций (каждое простое число нужно индивидуально проверить в каждом 4 мб блоке), а работать с блоками в sqrt(10^19)=4 гигабайта оказывается очень медленно. Почему?

Во-первых, системная память не отличается большой скоростью. Даже Core i7 с его супербыстрым трехканальным контроллером памяти на практике дает 20 гигабайт в секунду (без overclocking), причем эти 20 гигабайт в секунду получаются при только последовательном доступе. В теории, DDR3 1066 должен давать 25.6 GB/s, но я еще не видел комбинации платформы и кода, которые бы достигли этого теоретического лимита. Мой собственный i7 920 дает где-то 18 GB/s, и получить даже это значение нужны определенные ухищрения. Более старые интеловские платформы (и все современные AMD'шные) в лучшем случае дают 8-10 GB/s.

Что существеннее - наша задача, в наивной реализации (а для простых чисел больше ~10^6 - и в более продвинутых реализациях), не требует последовательного доступа, она требует произвольный доступ. А скорость произвольного доступа к памяти в последние 5-10 лет практически не менялась. Время произвольного доступа к байту DDR3-1066 с timing 7-7-7 = 21 такт частоты 533 мегагерц, или 40 наносекунд: больше 100 циклов процессора.

Что делать? Выход есть. Но правильный ответ немного подождет ...

[venco]

У меня пока получилось 406 секунд на 1.1, и 1119 секунд на 1.2 (тот же процессор, одно ядро).
Для проверки, в 1.2 2285693139 простых.

[dB13]

Хорошая задачка, дайте несколько дней на мой вариант.

[flip_flop]

Хорошая задачка, дайте несколько дней недель (лет?) на мой вариант

[flip_flop]

1.1
196 sec, prime# 2714336584, Laptop Compaq 8510w, Core2Duo T7700 2 Cores 2 Threads, 2.40 GHz, 4.0 GB RAM, 4 MB L2, Win7-64b (large overhead from IT)

1.2 - 0 0 ... :х

1.2' [10^18...10^18+10^11]
605 sec, prime # 2412731214

[dB13]

Вы все круты, а я тормоз.
10^16 до 10^16+10^9 (10^11 будет в 100 раз медленнее)
6.8 сек. (2x Xeon E5530 / i7, 2.4GHz, 8 MB L3) -- 6 MB sieve tile size
7.3 сек. (Core2 Duo T9300, 2.5 GHz, 6MB L2) -- 4 MB sieve tile size

Ладно, сейчас поплотнее утрамбую решето и распараллелю.

[flip_flop]

10^16 до 10^16+10^9 (10^11 будет в 100 раз медленнее)

Неа - у меня всего лишь в ~50 раз медленнее. Даже число простых чисел не в 100 раз больше а "всего" в 99.9637642775503 раза

Работайте, уже хочется послушать автора о том, как ему удается сгладить потери (1.1 -> 1.2) при ворочании длинными числами.

[venco]

Исправил переполнение в одном месте и попробовал на 64-бит.
Процессор X5260 3.33GHz в одну нитку.
1.1: 229 сек
1.2: 510 сек

[venco]

Ещё соптимизировал.
Процессор X5260 3.33GHz в одну нитку.
1.1: 198 сек
1.2: 446 сек

[flip_flop]

Как обещалось, задачка отличная и на года.

"Заимствовал" чужие идеи и подрихтовал чуток под мой уже старенький десктоп. Линукс, RHEL 6.1, I7-975, 4 ядра/потока, 3.3 GHz, 12 GB RAM

Последние цифры:

Code: Select all

[me on Linux]$ bin/primesieve 10^16 10^16+10^11 -t4
START      = 10000000000000000
STOP       = 10000100000000000
Sieve size = 32 kilobytes
Threads    = 4
100%
Prime numbers : 2714336584
Time elapsed  : 23.57 sec
[me on Linux]$ bin/primesieve 10^19 10^19+10^11 -t4
START      = 10000000000000000000
STOP       = 10000000100000000000
Sieve size = 32 kilobytes
Threads    = 4
100%
Prime numbers : 2285693139
Time elapsed  : 74.7427 sec

Есть еще куда расти - через год попробую перейти барьер в 1 секунду на десктопе для 1.1. Как ни странно, у меня осталось мнение что иерархия памяти еще не до конца оптимально использована для этой задачи доступными методами - век живи век учись.

Отличная задача, особенно на фоне "детских" вопросов типа Гугло-Интервьювера по Жабе (http://forum.privet.com/viewtopic.php?f ... 0&start=55)