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

Question

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

(a + b) + c не равно a + (b + c)

, а a * (b + c) не равно a * b + a * c

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Подходит ли (или адекватно) ли это для этой задачи - другая история ...

Удачного кодирования.

Answer 4

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

Answer 5

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

Answer 6

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

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;некоторые компиляторы могут не поддерживать его.