Как найти компромисс между точностью и скоростью, чтобы оценить произведение знака двух векторов в C ++? (Не зависит от оборудования) - PullRequest
Новая
       29

Как найти компромисс между точностью и скоростью, чтобы оценить произведение знака двух векторов в C ++? (Не зависит от оборудования)

7 голосов
/ 13 июня 2019

Скажем, у меня есть два вектора с плавающей точкой A и B. Мне нужно найти точечное произведение A и B, т.е.знак (AB) - если он положительный или отрицательный или равен 0. Размер векторов мал, меньше 100. Однако мне нужно сделать это очень быстро!
Можно предположить, что все элементы в A являются плавающими в диапазоне [0,1], а элементы B равны [-500, + 500].Я искал точное решение, но приблизительные решения тоже подойдут, если практически не дают много неправильных ответов (я знаю, «много» субъективно, но я не могу поставить точное число на нем, не говоря об аппаратном обеспечении или реализации)

Я изучил директивы компилятора Pragma, используя -O4, который работал быстрее всего.Я исследовал еще несколько улучшений в реализации, чтобы сделать его парализуемым на основе поддержки автовекторизации базового процессора.Как и для набора инструкций avx, сохраните 8 независимых переменных и найдите точечное произведение, чтобы использовать все 8 регистровых мощностей.Но я думаю, что мы все еще можем быть намного быстрее!Основная идея заключается в том, что нам нужно только определить знак точечного произведения, поэтому есть много возможностей для компромисса между точностью и скоростью.Поэтому я пытаюсь найти какое-то математическое или алгоритмическое решение, чтобы это произошло.У меня есть идея использовать FFT (быстрое преобразование Фурье), чтобы уменьшить количество умножений.Еще одна идея, которую я пытался исследовать, была побитовые уловки, но реализована побитовая для плавающего не представляется возможным.(Стандарты IEEE не гарантируются, когда вы используете быструю прагму, такую ​​как Ofast или O3)

Вы можете подумать, почему это так важно оптимизировать для такой незначительной задачи, но я думаю, что это может быть очень полезным вопросом: -

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

1 Ответ

1 голос
/ 13 июня 2019

На современных архитектурах вычисление числа с плавающей точкой уже очень быстро, 1 цикл будет потрачен на сложение и 1-2 цикла на умножение.

  1. Я думаю, что производительность может иметь значение только тогда, когда рассчитывается много точечных продуктов.
  2. Как правило, это означает, что много данных нужно будет прочитать
  3. Это означает, что во время выполнения будет преобладать пропускная способность памяти.
  4. Это означает, что большой прирост производительности можно получить только при использовании меньших типов с плавающей запятой, т. Е. 32-битных или 16-битных чисел с плавающей запятой.
...