Один из наших постоянных читателей Peter Levchenko провел собственное расследование о причинах столь высокой эффективности программы Prime95 как инструмента для оценки стабильности системы. Приводим его письмо целиком.

Я вот тут прочитал ваши сообщения по поводу Prime95 и исследовать почему программа дает такую эффективную оценку стабильности...

Разберемся в устройстве программы.

Как вы могли разобраться, программа занимается итерациями (повторными применениями фиксированного числа математических операций) теста Лукаса-Лемера (Lucas-Lehmer test). Он гласит, что для P > 2, число 2^P-1 является простым (делящимся только на себя и на единицу) тогда и только тогда, когда S_p-2 равно нулю в последовательности: S₀ = 4, S_N = (S_N-1² - 2) mod (2^P-1) . Ну например докажем что число 2⁷ - 1 простое:

S₀ = 4
S₁ = (4 * 4 - 2) mod 127 = 14
S₂ = (14 * 14 - 2) mod 127 = 67
S₃ = (67 * 67 - 2) mod 127 = 42
S₄ = (42 * 42 - 2) mod 127 = 111
S₅ = (111 * 111 - 2) mod 127 = 0

(Надеюсь вы знаете что такое конгруэнтность и что значит mod. Если x конгруэнтно y по модулю N, т.е. x ≡y mod N, это значит, что выражение y - x / N "возвращает" целое число. Например:  3 ≡23 mod 10 так как (23 - 3) / 10 = 2. Конгруэнтность - основа Теории Чисел).

Очевидно, что в компьютационных целях задача программы применять Lucas-Lehmer test наиболее эффективно (а главное ведь скорость !), следовательно, она сокращает время тем что просто возводит в квадрат числа по модулю 2^P-1 выше упомянутой последовательности S. Это и есть суть проекта GIMPS (Great Internet Mersenne Primes Search), который занимается поиском простых чисел Мерсенна, т.е. простых чисел формы 2^P-1, впервые предложенных французским монахом Марином Мерсенном. (Кстати, самое большое на данный момент известное простое число было найдено этим самым проектом в Ноябре 2003, это число, 2( в степени 20996011)-1, является простым числом Мерсенна (уже сороковым известным).

Что-то я отвлекся, так что же это за самый быстрый метод, который использует программа?

Алгоритм состоит из следующих операций:

1. разбитие числа на секции и сложение их в массив;
2. применение быстрого преобразования Фурье (Fast Fourier Transform - FFT);
3. возведение в квадрат;
4. применение ОБРАТНОГО быстрого преобразования Фурье (Inverse Fast Fourier Transform - IFFT).

А что же такое это FFT ?

Быстрое преобразование Фурье (FFT) это дискретный алгоритм который сокращает число компьютаций (вычислений) аргумента в порядке  N₀²   к   N₀ log N₀ . Короче говоря, дан аргумент x, и необходимое число вычислений этого аргумента равно может быть выражено в форме z = N₀² . Тогда использование этого алгоритма сокращает число вычислений до N₀ log N₀ . 

Здесь, log - это логарифм. Чаще выбирают основание логарифма 2, но это необязательно... Отсюда IFFT вы я думаю разгадаете сами !

А этот "дискретный алгоритм" называется DFT (Discrete Fourier Transform) и используется вместо FT (Fourier Transform) потому, что компьютер работает только с дискретными числами, а значит численные компьютации обыкновенных преобразований Фурье (они в своей основе разлагают или разделяют функцию на синусоиды различной частоты, сумма которых равна начальной функции) требуют только дискретные числа функции (назовем ее f(t)). Кроме того, компьютер может только вычислить преобразование f(t) для дискретных значений t. Таким образом, обычная трансформация Фурье была переопределена и модифицирована в дискретную трансформацию для использования компьютерами. Ее алгоритм и использован FFT (Fast Fourier Transform).

Так для чего же все это ?

А вот здесь нам и чисто компьютерные знания процессора помогут !

Для двоичных чисел (помните основание 2 логарифма используемого FFT ?) этот тест идеален поскольку деление на 2^p-1 в двоичном коде может быть осуществлено ТОЛЬКО с использованием побитного смещения и сложения !!! (Т.е. здесь чисто нагружается CPU да еще только простыми операциями!)

Кроме того, Prime95 использует FFT с плавающей запятой, написанные на ассемблере в конвейерной организации (специально сделанная под дополнительные архитектурные особенности процессоров).

Так как такие вычисления неточны, после каждой итерации числа с плавающей запятой округлены (до нижнего барьера) в целые. Отклонение (неточность) между полученными целым числом и числом с плавающей запятой называется сверточной ошибкой (или ошибкой свертки). Когда ошибка превышает 0.5, округление приводит к неверным результатам, т.е. большая FFT должна быть использована!

Вот в чем заключается мощность Prime95!

Те же 3DMark2001, CPU Stability test, SiSoft Sandra (насчет Hot CPU Tester сказать нечего - я за эту программу еще не садился...) проводят итерации FFT вида "а выдержит ли процессор", т.е. тесты на точность у них работают по методу проверки. На некоторых вообще используются целочисленные FFT (!), другие же не проверяют на свертку (я имею ввиду сверточную ошибку - convolution error) и таким образом просто переходят на другую итерацию. Т.е. если эта сверточная ошибка действительно допущена, вас ожидает либо BSOD (Blue Screen Of Death), либо рестарт, в то время как 3DMark 2001 и т. п. скажет вам что test passed!

А вот если Prime95 комп протестирует, за поставленный диагноз можно ручаться (во всяком случае, уверенности намного больше)....

Для гарантии можно запустив CPU Torture Test на хотя бы от 6 до 24 часов !!! (чтобы провести итерацию большего числа блоков и различной длины).

Конечно, FFT - это не весь CPU, но он, я бы осмелился сказать, нагружает одновременно CPU, память, кеш L1 и L2, и также побочно тестирует охлаждение CPU и кейса гораздо сильнее любых других алгоритмов вроде комплексной матрицы или ассемблирования (причины перечислены выше) и эффективно оценивается Prime95.

Убедительно ?

С наилучшими пожеланиями, M@je$+c

www.htworld.0catch.com

Если у вас уже появилось необратимое желание испробовать Prime95, скачивайте ее из нашего файлового архива:

• Prime95 23.8 (1,0 МБ, Windows 9x/ME/NT/2000/XP).