Что может привести к тому, что детерминированный процесс будет генерировать ошибки с плавающей запятой

Question

Уже прочитав это вопрос Я вполне уверен, что данный процесс, использующий арифметические операции с плавающей запятой с одним и тем же вводом (на том же оборудовании, скомпилированный одним и тем же компилятором), должен быть детерминированным.Я рассматриваю случай, когда это неправда, и пытаюсь определить, что могло стать причиной этого.

Я скомпилировал исполняемый файл и передаю ему те же самые данные, работая на одной машине (немногопоточной), но получаю ошибки примерно 3.814697265625e-06, которые после тщательного поиска в Google фактически равны 1. /4^9 = 1/2^18 = 1/262144.что довольно близко к уровню точности 32-битного числа с плавающей запятой (около 7 цифр согласно Википедии)

Я подозреваю, что это как-то связано с оптимизацией, примененной к коду.Я использую компилятор Intel C++ и сделал спекуляции с плавающей запятой быстрыми, а не безопасными или строгими.Может ли это сделать процесс с плавающей запятой недетерминированным?Существуют ли другие оптимизации и т. д., которые могут привести к такому поведению?

РЕДАКТИРОВАТЬ:По предложению Пакса я перекомпилировал код, сделав предположения с плавающей запятой безопасными, и теперь получаю стабильные результаты.Это позволяет мне прояснить этот вопрос: что на самом деле делают спекуляции с плавающей запятой и как это может привести к тому же двоичному файлу (т.одна компиляция, несколько запусков) для получения разных результатов при применении к одному и тому же входному сигналу?

@Бен, я компилирую с использованием Intel(R) C++ 11.0.061 [IA-32] и работаю на четырехъядерном процессоре Intel.

Answer 1

Практически в любой ситуации, где есть быстрый и безопасный режим, вы найдете тот или иной компромисс.В противном случае все будет работать в быстро-безопасном режиме :-).

И если вы получаете разные результаты при одних и тех же входных данных, ваш процесс нет детерминирован, независимо от того, насколько вы в это верите (несмотря на эмпирические данные).

Я бы сказал, что ваше объяснение наиболее вероятно.Переведите его в безопасный режим и посмотрите, исчезнет ли недетерминизм.Это скажет вам наверняка.

Что касается того, есть ли другие оптимизации, если вы компилируете на том же оборудовании с тем же компилятором/компоновщиком. и те же параметры для этих инструментов, он должен генерировать идентичный код.Я не вижу никакой другой возможности, кроме быстрого режима (или подгнивания памяти из-за космических лучей, но это маловероятно).

После вашего обновления:

У Intel есть документ здесь который объясняет некоторые вещи, которые им не разрешено делать в безопасном режиме, включая, помимо прочего:

• реассоциация: (a+b)+c -> a+(b+c).
• нулевое складывание: x + 0 -> x, x * 0 -> 0.
• взаимное умножение: a/b -> a*(1/b).

Хотя вы утверждаете, что эти операции определяются во время компиляции, чипы Intel чертовски умны.Они могут изменить порядок инструкций, чтобы конвейеры были заполнены в многопроцессорных конфигурациях, поэтому, если код специально не запрещает такое поведение, все может измениться во время выполнения (не во время компиляции), чтобы все работало на полной скорости.

Это описано (кратко) на странице 15 связанного документа, в котором говорится о векторизации ("Проблема:разные результаты при повторном запуске одного и того же двоичного файла с теми же данными на одном и том же процессоре").

Мой совет — решить, нужна ли вам чистая производительность или полная воспроизводимость результатов, а затем выбирать режим на основе этого.

Answer 2

Если ваша программа распараллелена, например, на четырехъядерном процессоре, то она вполне может быть недетерминированной.

Представьте, что у вас есть 4 процессора, добавляющих значение с плавающей запятой в одну и ту же ячейку памяти.Тогда вы можете получить

(((InitialValue+P1fp)+P2fp)+P3fp)+P4fp

или

(((InitialValue+P2fp)+P3fp)+P1fp)+P4fp

или любой другой возможный порядок.

Черт возьми, ты можешь даже получить

 InitialValue+(P2fp+P3fp)+(P1fp+P4fp)

если компилятор достаточно хорош.

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

Из-за этого параллельные вычисления FP часто недетерминированы.«Часто», потому что программы, похожие на

  on each processor
    while( there is work to do ) {
       get work
       calculate result
       add to total 
    }

будет недетерминированным, поскольку количество времени, которое занимает каждая операция, может сильно различаться — вы не можете предсказать порядок операций.(Хуже, если потоки взаимодействуют.)

Но не всегда, поскольку существуют детерминированные стили параллельного программирования.

Конечно, многие люди, которые заботятся о детерминизме, работают с целыми числами или с фиксированной точкой, чтобы избежать проблемы.Мне особенно нравятся супераккумуляторы, 512-, 1024- или 2048-битные числа, к которым можно добавлять числа с плавающей запятой без ошибок округления.

---

Что касается однопоточного приложения:компилятор может изменить код.Разные сборники могут давать разные ответы.Но любой конкретный двоичный файл должен быть детерминированным.

Пока не...вы работаете на динамическом языке.При этом выполняются оптимизации, которые изменяют порядок вычислений FP, который меняется со временем.

Или если...очень длинный план:У Itanium были некоторые особенности, такие как ALAT, которые делали недетерминированным даже однопоточный код.На вас это вряд ли повлияет.