Более быстрый абс-макс массива с плавающей запятой

StackOverflow https://stackoverflow.com/questions/817604

Вопрос

Мне нужно нарисовать пиковые измерители звука в реальном времени.Минимум 44100 выборок в секунду, минимум 40 потоков.Каждый буфер содержит от 64 до 1024 выборок.Мне нужно получить максимум абс из каждого буфера.(Затем они пропускаются через своего рода фильтр нижних частот и рисуются с интервалом примерно 20 мс.)

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

Вот как я это делаю сейчас.Я бы хотел сделать это гораздо быстрее.Буферы имеют числа с плавающей запятой в диапазоне от -1 до 1, отсюда и fabs.

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

В противном случае существуют ли безветвевые функции ABS и MAX для чисел с плавающей запятой?

редактировать:Основная платформа — Linux/gcc, но планируется порт для Windows (вероятно, с mingw).

редактировать, второе:
Я дал согласие каждому из-за части, касающейся фактической структуры алгоритма, которая была центральной в вопросе.
Я попробую развернуть цикл до четырех за раз, обнулить знаковые биты, а затем получить максимум с помощью SSE (инструкция maxps) и посмотреть, не очистит ли это банан.Спасибо за предложения, я проголосовал за некоторых из вас, занявших второе место.:)

Это было полезно?

Решение

Fabs и сравнение действительно быстры для IEEE с плавающей запятой (например, в принципе, быстро с одним целым числом).

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

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

f > g   iff   *(int*)&f > *(int*)&g

Итак, как только вы это сделаете, я думаю, что максимум без ветвей для int также будет работать для float (конечно, при условии, что они одинакового размера).Здесь есть объяснение, почему это работает: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm.Но ваш компилятор уже знает все это, как и ваш процессор, поэтому это может не иметь никакого значения.

Не существует более сложного и быстрого способа сделать это.Ваш алгоритм уже O(n), и вы не можете превзойти его и при этом просматривать каждый образец.

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

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

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

Еще одна вещь, о которой следует подумать, — это сколько промахов в кэше вы получаете и можно ли уменьшить это число, давая кэшу несколько подсказок, чтобы он мог загружать нужные страницы заранее.Но у меня нет опыта в этом, и я бы не питал особых надежд.__builtin_prefetch — это волшебное заклинание gcc, и я предполагаю, что первый эксперимент будет чем-то вроде «предварительной выборки начала следующего блока перед входом в цикл для этого блока».

На каком проценте от требуемой скорости вы сейчас находитесь?Или это вариант «как можно быстрее»?

Другие советы

Существует документация о внеотраслевых фабриках. http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

Также обратите внимание, что в последних версиях GCC будет встроена внеотраслевая fabs для вас, используя инструкции MMX.А также есть fmin и fmax, но GCC не будет их встраивать (вы получите call fmin).

Что стоит попробовать:

  • fabs() может не быть встроенной функцией.
  • Специальные инструкции по сборке могут помочь.В Intel у SSE есть инструкция для одновременного вычисления максимум четырех чисел с плавающей запятой.
  • В противном случае спецификация IEEE 754 такова, что если a и b равны неотрицательный плавает, то a < b эквивалентно *(int *)&a < *(int *)&b.Более того, для любого a вы можете вычислить -a из a, перевернув старший бит.Вместе эти свойства могут позволить сделать некоторые хитроумные хаки.
  • Действительно ли вам нужен максимум от каждой выборки?Возможно, максимум может возникнуть более одного раза, что дает возможность не проверять каждый ввод.
  • Можете ли вы вычислить максимум потоковым способом?

Возможно, вы захотите посмотреть Эйген.

Это библиотека шаблонов C++, которая использует Наборы инструкций SSE (2 и более поздних версий) и AltiVec с плавным переходом к невекторизованному коду..

Быстрый.(См. тест).
Шаблоны выражений позволяют разумно удалять временные объекты и включать отложенную оценку, когда это необходимо — Eigen позаботится об этом автоматически и в большинстве случаев также обрабатывает псевдонимы.
Явная векторизация выполняется для наборов инструкций SSE (2 и более поздних версий) и AltiVec с плавным возвратом к невекторизованному коду.Шаблоны выражений позволяют выполнять эти оптимизации глобально для целых выражений.
При использовании объектов фиксированного размера избегается динамическое выделение памяти, и циклы разворачиваются, когда это имеет смысл.
Для больших матриц особое внимание уделяется удобству кэширования.

отвечать на вопрос другим вопросом - это не совсем ответ, но эй... Я тоже не разработчик C++.

Поскольку вы разрабатываете это на C++ и выполняете DSP, не можете ли вы подключиться к Matlab или Octave (с открытым исходным кодом) к математическим вычислениям и просто получить результат?

уже есть функции (такие как conv, fft,ifft, fir и функции построения графиков, такие как freqz, Stem, Graph, Plot, Mesh и т. д.), реализованный в этих частях программного обеспечения.Я заглянул в Photoshop и увидел большую папку под названием MATLAB... с несколькими файлами .m, которые получают вызовы из приложения, отправляют их в динамическую штуковину Matlab, а затем возвращают результат в приложение.

Надеюсь, поможет.

Простая оптимизация, которую я вижу:

  • перевести цикл в версию арифметики указателей (при условии, что ваш компилятор этого не видит)
  • стандарт IEEE 754 определяет его представление как знак-величину.Таким образом, установка старшего бита в 0 будет такой же, как вызов fabs().Возможно, эта функция уже использует этот трюк.

Для вашей цели вы можете возвести его в квадрат вместо того, чтобы принимать абсолютное значение;как математически | a | <| b | Если a^2 <b^2 и наоборот.На некоторых машинах умножение может быть быстрее, чем fabs() (?), я не знаю.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top