Какие алгоритмы больше всего выигрывают от слияния с умножением?
fma (a, b, c) эквивалентно a * b + c , за исключением того, что оно не округляет промежуточный результат.
Не могли бы вы дать Приведите несколько примеров алгоритмов, которым нетривиальная выгода от избежания этого округления?
Это не очевидно, поскольку округление после умножения, которое мы избегаем, имеет тенденцию быть менее проблематичным, чем округление после сложения, которое мы не делаем.
4 ответа
В голове не укладывается – умножение матриц, правило Ньютона, вычисление полиномов, численные методы
Единственное, что я пока нашел, это "безошибочные преобразования". Для любых чисел с плавающей запятой ошибки из a+b, ab и a*b также являются числами с плавающей запятой (в режиме округления до ближайшего, при условии отсутствия переполнения /недолив и т.д. и т.п.).
Ошибку сложения (и, очевидно, вычитания) легко вычислить; если abs(a) >= abs(b), ошибка точно равна b-((a+b)-a) (2 флопа или 4-5, если мы не не знаю, что больше). Ошибку умножения легко вычислить с помощью fma — это просто fma(a,b,-a*b). Без fma это 16 флопов довольно неприятного кода. А полностью общая эмуляция правильно округленного fma еще медленнее.
Дополнительные 16 флопов отслеживания ошибок на каждый флоп реальных вычислений — это огромное излишество, но всего с 1-5 флопами, удобными для конвейера, это вполне разумно, и для многих алгоритмов, основанных на этих 50%-200% накладных расходов на отслеживание ошибок и компенсация приводит к такой малой ошибке, как если бы все вычисления выполнялись с удвоенным количеством битов, что во многих случаях позволяет избежать плохой обработки.
Интересно, что fma никогда не используется в этих алгоритмах для вычисления результатов, а только для поиска ошибок, потому что нахождение ошибки fma происходит медленно, так как нахождение ошибки умножения без фма.
Релевантными ключевыми словами для поиска будут «компенсированная схема Хорнера» и «компенсированное скалярное произведение», причем схема Хорнера дает гораздо больше преимуществ.
Основным преимуществом FMA является то, что он может работать в два раза быстрее. Вместо того, чтобы использовать 1 такт для умножения, а затем 1 такт для сложения, FPU может выполнять обе операции в одном и том же цикле. Очевидно, что большинство алгоритмов выиграют от более быстрых операций.
Некоторые примеры: Векторные скалярные произведения. Преобразования Фурье. Цифровая обработка сигналов. Полиномы. Всякие вещи.
Это вопрос оптимизации и использования аппаратного обеспечения в большей степени, чем что-либо еще. Сумма произведений является очень распространенным требованием в численных методах, и таким образом вы можете дать компилятору явные инструкции о том, как сделать что-то быстро и, возможно, с немного большей точностью. Если я не ошибаюсь, компилятор может заменить a=b*c+d инструкцией FMA, но он также может этого не делать. (если стандарт не требует округления, но компиляторы реального мира регулярно нарушают стандарты небольшими способами).