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

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

6 голосов
/ 09 июня 2009

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

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

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

EDIT : В соответствии с предложением Пакса я перекомпилировал код с предположениями с плавающей запятой, которые стали безопасными, и теперь я получаю стабильные результаты. Это позволяет мне прояснить этот вопрос - что на самом деле делает спекуляция с плавающей запятой и как это может привести к тому, что один и тот же двоичный файл (то есть одна компиляция, несколько прогонов) генерирует разные результаты при применении к одному и тому же входу?

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

Ответы [ 2 ]

13 голосов
/ 09 июня 2009

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

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

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

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

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

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

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

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

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

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

0 голосов
/ 02 мая 2012

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

Представьте, что у вас есть 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, которые делали даже однопоточный код недетерминированным. Это вряд ли повлияет на вас.

...