Как сделать вычисления с плавающей запятой детерминированными?
Вычисление с плавающей запятой не является ни ассоциативным, ни распределительным на процессорах. Так,
(a + b) + c не равно a + (b + c)
а также a * (b + c) не равно a * b + a * c
Есть ли способ выполнить детерминированный расчет с плавающей запятой, который не дает разных результатов. Это было бы детерминировано для однопроцессорного конечно, но это не было бы детерминировано в многопоточных программах, если потоки добавляют к сумме, например, так как могут быть различные чередования потоков.
Итак, мой вопрос: как можно достичь детерминированных результатов для вычислений с плавающей запятой в многопоточных программах?
6 ответов
Плавающая точка является детерминированной. Одни и те же операции с плавающей точкой, выполняемые на одном и том же оборудовании, всегда дают один и тот же результат. Там нет черной магии, шума, случайности, размытости или каких-либо других вещей, которые люди обычно приписывают плавающей точке. Зубная фея не появляется, возьмите низкие биты своего результата и оставьте четверть под подушкой.
Тем не менее, некоторые заблокированные алгоритмы, которые обычно используются для крупномасштабных параллельных вычислений, являются недетерминированными с точки зрения порядка, в котором выполняются вычисления с плавающей запятой, что может привести к не точным в битах результатам при выполнении.
Что вы можете с этим поделать?
Во-первых, убедитесь, что вы на самом деле не можете жить с ситуацией. Многое из того, что вы можете попытаться навести порядок в параллельных вычислениях, снизит производительность. Вот только как это.
Я также хотел бы отметить, что хотя заблокированные алгоритмы могут вносить некоторую степень недетерминированности, они часто дают результаты с меньшими ошибками округления, чем наивные неблокированные последовательные алгоритмы (удивительно, но это правда!). Если вы можете жить с ошибками, вызванными наивным последовательным алгоритмом, вы, вероятно, можете жить с ошибками параллельного заблокированного алгоритма.
Теперь, если вам действительно нужна точная воспроизводимость при разных запусках, вот несколько советов, которые не слишком сильно влияют на производительность:
Не используйте многопоточные алгоритмы, которые могут переупорядочивать вычисления с плавающей точкой. Задача решена. Это не означает, что вы не можете использовать многопоточные алгоритмы вообще, просто вам нужно убедиться, что каждый отдельный результат затрагивается только одним потоком между точками синхронизации. Обратите внимание, что это может реально улучшить производительность на некоторых архитектурах, если все сделано правильно, за счет снижения конкуренции за D$ между ядрами.
В операциях редукции вы можете сделать так, чтобы каждый поток сохранял свой результат в индексируемом месте в массиве, ожидал завершения всех потоков, собирал элементы массива по порядку. Это добавляет небольшое количество памяти, но обычно довольно терпимо, особенно когда число потоков "мало".
Найдите способы поднять параллелизм. Вместо вычисления 24 матричных умножений, каждое из которых использует параллельные алгоритмы, параллельно вычисляют 24 матричных произведения, каждое из которых использует последовательный алгоритм. Это тоже может быть полезно для производительности (иногда очень сильно).
Есть много других способов справиться с этим. Все они требуют мысли и заботы. Параллельное программирование обычно делает.
Изменить: я удалил свой старый ответ, так как я, кажется, неправильно понял вопрос ОП. Если вы хотите увидеть его, вы можете прочитать историю редактирования.
Я думаю, что идеальным решением было бы переключиться на использование отдельного аккумулятора для каждого потока. Это позволяет избежать всех блокировок, что должно существенно повлиять на производительность. Вы можете просто суммировать аккумуляторы в конце всей операции.
В качестве альтернативы, если вы настаиваете на использовании одного аккумулятора, одним из решений является использование "с фиксированной запятой", а не с плавающей запятой. Это можно сделать с помощью типов с плавающей точкой, включив гигантский термин "смещение" в свой аккумулятор, чтобы зафиксировать показатель в фиксированном значении. Например, если вы знаете, что аккумулятор никогда не превысит 2^32, вы можете запустить аккумулятор в 0x1p32, Это приведет к 32-битной точности слева от радиуса и 20-битной дробной точности (при условии, что double). Если это не достаточно точно, вы можете использовать меньший уклон (при условии, что аккумулятор не станет слишком большим) или переключиться на long double, Если long double это расширенный формат 80 бит, смещение 2 ^ 32 даст 31 бит дробной точности.
Затем, когда вы хотите "использовать" значение аккумулятора, просто вычтите смещение.
Даже использование высокоточного типа данных с фиксированной точкой не решило бы проблему определения результатов для указанных уравнений (за исключением некоторых случаев). Как отметил Кит Томпосон в комментарии, 1/3 является тривиальным контрпримером значения, которое не может быть правильно сохранено в стандартном представлении с плавающей точкой base-10 или base-2 (независимо от точности или используемой памяти).
Одним из решений, которое, в зависимости от конкретных потребностей, может решить эту проблему (оно все еще имеет ограничения), является использование типа данных Rational number (тот, который хранит как числитель, так и знаменатель). Кит предложил GMP в качестве одной из таких библиотек:
GMP - это бесплатная библиотека для арифметики произвольной точности, работающая со целыми числами со знаком, рациональными числами и числами с плавающей запятой. Там нет практического ограничения на точность...
Подходит ли он (или адекватен) для этой задачи - это другая история...
Удачного кодирования.
Используйте десятичный тип или библиотеку, поддерживающую такой тип.
Попробуйте сохранить каждый промежуточный результат в энергозависимом объекте:
volatile double a_plus_b = a + b;
volatile double a_plus_b_plus_c = a_plus_b + c;
Это может иметь неприятные последствия для производительности. Я предлагаю измерять обе версии.
РЕДАКТИРОВАТЬ: цель volatile заключается в запрете оптимизаций, которые могут повлиять на результаты даже в однопоточной среде, таких как изменение порядка операций или сохранение промежуточных результатов в более широких регистрах. Это не решает проблемы многопоточности.
РЕДАКТИРОВАТЬ 2: Что-то еще, чтобы рассмотреть это
Плавающее выражение может быть сжато, то есть вычислено так, как если бы оно было атомарной операцией, тем самым исключая ошибки округления, подразумеваемые исходным кодом и методом оценки выражения.
Это может быть заблокировано с помощью
#include <math.h>
...
#pragma STDC FP_CONTRACT off
Ссылка: стандарт C99 (большой PDF), разделы 7.12.2 и 6.5, параграф 8. Это специфично для C99; некоторые компиляторы могут не поддерживать это.