Как расчеты с плавающей запятой могут быть детерминированными?

Ответ 1

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

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

Что вы можете сделать с этим?

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

Я также хотел бы отметить, что хотя блокированные алгоритмы могут вводить некоторое количество недетерминированности, они часто дают результаты с меньшими ошибками округления, чем наивные разблокированные последовательные алгоритмы (удивительно, но верно!). Если вы можете жить с ошибками, вызванными алгоритмом наивного последовательного алгоритма, вы, вероятно, можете жить с ошибками параллельного алгоритма блокировки.

Теперь, если вы действительно нуждаетесь в точной воспроизводимости во всех прогонах, вот несколько советов, которые не слишком сильно влияют на производительность:

• Не используйте многопоточные алгоритмы, которые могут переупорядочивать вычисления с плавающей запятой. Задача решена. Это не означает, что вы не можете использовать многопоточные алгоритмы вообще, просто для того, чтобы каждый отдельный результат касался только одного потока между точками синхронизации. Обратите внимание, что это может фактически повысить производительность на некоторых архитектурах, если все сделано правильно, за счет уменьшения конкуренции D $между ядрами.

• В операциях сокращения вы можете каждый поток сохранять свой результат в индексированное местоположение в массиве, дожидаясь завершения всех потоков, аккумулировать элементы массива по порядку. Это добавляет небольшой объем накладных расходов памяти, но, как правило, довольно переносимо, особенно когда количество потоков является "маленьким".

• Найдите способы подъема parallelism. Вместо вычисления 24 матричных умножений, каждый из которых использует параллельные алгоритмы, параллельно вычисляет 24 матричных произведения, каждый из которых использует последовательный алгоритм. Это тоже может быть полезно для производительности (иногда это чрезвычайно важно).

Есть много других способов справиться с этим. Все они нуждаются в мысли и заботе. Параллельное программирование обычно выполняется.

Ответ 2

Изменить: Я удалил свой старый ответ, так как я, похоже, неправильно понял вопрос OP. Если вы хотите его увидеть, вы можете прочитать историю изменений.

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

В качестве альтернативы, если вы настаиваете на использовании одного аккумулятора, одним из решений является использование "фиксированной точки", а не плавающей точки. Это можно сделать с помощью типов с плавающей точкой, включив в свой аккумулятор гигантский термин "смещение", чтобы заблокировать экспонента с фиксированным значением. Например, если вы знаете, что аккумулятор никогда не будет превышать 2 ^ 32, вы можете запустить аккумулятор на 0x1p32. Это блокирует вас с точностью до 32 бит слева от точки счисления и 20 бит дробной точности (при условии double). Если этого недостаточно, вы можете нам уменьшить смещение (при условии, что аккумулятор не станет слишком большим) или переключиться на long double. Если long double - это 80-битный расширенный формат, смещение в 2 ^ 32 даст 31 бит дробной точности.

Затем, когда вы хотите фактически "использовать" значение аккумулятора, просто вычтите термин смещения.

Ответ 3

Даже использование высокоточного фиксированного точечного типа данных не решило бы проблему получения результатов для указанных уравнений детерминированными (за исключением некоторых случаев). Как указал Кит Томпосон в комментарии, 1/3 представляет собой тривиальный примерный пример значения, которое нельзя сохранить правильно в стандартном представлении с плавающей запятой стандартного base-10 или base-2 (независимо от точности или использования памяти).

Одно решение, которое в зависимости от конкретных потребностей может решить эту проблему (оно все еще имеет ограничения), заключается в использовании Rational number типа данных (который хранит как числитель, так и знаменатель). Кейт предложил GMP как одну из таких библиотек:

GMP - свободная библиотека для произвольной арифметики точности, работающая со знаками целых чисел, рациональных чисел и чисел с плавающей запятой. Практически не предел точности...

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

Счастливое кодирование.

Ответ 4

Используйте десятичный тип или библиотеку, поддерживающие такой тип.

Ответ 5

Попробуйте сохранить каждый промежуточный результат в летучем объекте:

volatile double a_plus_b = a + b;
volatile double a_plus_b_plus_c = a_plus_b + c;

Вероятно, это негативное влияние на производительность. Я предлагаю измерить обе версии.

EDIT. Цель volatile - запретить оптимизацию, которая может повлиять на результаты даже в однопоточной среде, такие как изменение порядка операций или сохраняя промежуточные результаты в более широких регистрах. Он не учитывает проблемы многопоточности.

EDIT2: что-то еще, чтобы рассмотреть, что

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

Это может быть заблокировано с помощью

#include <math.h>
...
#pragma STDC FP_CONTRACT off

Ссылка: стандарт C99 (большой PDF), разделы 7.12.2 и 6.5 п. 8. Это C99-специфическое; некоторые компиляторы могут не поддерживать его.

Ответ 6

Используйте упакованный десятичный символ.