Быстрее абс-макс массива поплавка

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Какой процент требуемой скорости вы сейчас используете? Или это случай "как можно быстрее"?

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

Легких оптимизаций я вижу:

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

Answer 7

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

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

уже есть функции (например, функции conv, fft, ifft, fir и plot, такие как freqz, stem, graph, plot, mesh и т. Д.), Реализованные в этих частях программного обеспечения. Я заглянул в Photoshop, и там есть большая папка с именем MATLAB ... с некоторыми файлами .m, которые получают вызовы из приложения, отправляют его в динамический пакет matlab и затем возвращают результат в приложение.

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