Быстрое обратное преобразование бит FFT, можно ли считать обратный обратный бит?

Question

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

1) Я написал программу для генерации прямого, не зацикленного исходного кода x86, который можно вставить в мой FFT-код, который читает аудиосэмпл, умножает его на значение окна (это сама таблица поиска), а затем просто помещает результирующее значение в правильную бито-отсортированную позицию по абсолютным значениям в режимах адресации x86, таких как: movlps [edi + 1876], xmm0. Это самый быстрый способ сделать это для меньших размеров БПФ. Проблема заключается в том, что когда я пишу код напрямую для обработки значений 8192, код выходит за рамки размера кэша инструкций L1, а производительность падает. Конечно, в отличие от этого, таблица поиска с обращением 32K бит, смешанная с таблицей окон 32K, плюс другие вещи, также слишком велика, чтобы соответствовать кешу данных L1, и производительность снижается, но сейчас я так и делаю.

2) Я нашел шаблоны в последовательности обращения битов, которые можно использовать для уменьшения размера таблицы поиска, например, используя 4-разрядные числа (0..15) в качестве примера, последовательность обращения битов выглядит следующим образом: 0, 8,4,12,2,10,6,14 | 1,5,9,13,3,11,7,15. Первое, что можно увидеть, это то, что последние 8 чисел совпадают с первыми 8 +1, поэтому я могу нарезать свою половину LUT. Если я посмотрю на разницу между числами, то здесь будет больше избыточности, поэтому, если я начну с нуля в регистре и захочу добавить к нему значения, чтобы получить следующий битовый перевернутый номер, они будут: + 0, + 8, -4 , + 8, -10, + 8, -4, + 8 и то же самое для второй половины. Как видно, у меня может быть таблица поиска только 0 и -10, потому что + 8 и -4 всегда отображаются предсказуемым образом. Код будет развернут для обработки 4 значений в цикле: одно будет считано из таблицы поиска, а остальные 3 будут прямым кодом для +8, -4, +8, прежде чем снова зацикливаться. Затем второй цикл может обработать последовательность 1,5,9,13,3,11,7,15. Это здорово, потому что теперь я могу сократить свою таблицу поиска еще на 4 фактора. Это также увеличивает масштаб для FFT размером 8192. Теперь я могу обойтись LUT размером 4K вместо 32K. Я могу использовать тот же шаблон и удвоить размер моего кода, и снова сократить LUT еще на половину, как бы далеко я не хотел идти. Но чтобы полностью исключить LUT, я возвращаюсь к запрещенному размеру кода.

Для больших размеров БПФ, я считаю, что это решение № 2 является абсолютным самым быстрым на сегодняшний день, так как необходимо выполнить относительно небольшой процент операций чтения из справочной таблицы, и каждый алгоритм, который я в настоящее время нахожу в Интернете, требует слишком много последовательных / вычисления зависимостей, которые нельзя векторизовать.

Вопрос в том, существует ли алгоритм, который может увеличивать числа, чтобы MSB действовал как LSB и так далее? Другими словами (в двоичном виде): 0000, 1000, 0100, 1100, 0010 и т. Д. Я пытался придумать какой-то способ, и пока, за исключением нескольких вложенных циклов, я не могу найти путь для быстрого и простого алгоритма, который является зеркальным отображением простого добавления 1 к младшему разряду числа. И все же кажется, что должен быть способ.

Answer 1

Это самое тривиальное и простое решение (на С):

void BitReversedIncrement(unsigned *var, int bit)
{
  unsigned c, one = 1u << bit;
  do {
    c = *var & one;
    (*var) ^= one;
    one >>= 1;
  } while (one && c);
}

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

Вы можете сделать обратные приращения, работая с несколькими битами одновременно, например, 3, если целые 32-битные:

void BitReversedIncrement2(unsigned *var, int bit)
{
  unsigned r = *var, t = 0;

  while (bit >= 2 && !t)
  {
    unsigned tt = (r >> (bit - 2)) & 7;
    t = (07351624 >> (tt * 3)) & 7;
    r ^= ((tt ^ t) << (bit - 2));
    bit -= 3;
  }

  if (bit >= 0 && !t)
  {
    t = r & ((1 << (bit + 1)) - 1);
    r ^= t;
    t <<= 2 - bit;
    t = (07351624 >> (t * 3)) & 7;
    t >>= 2 - bit;
    r |= t;
  }

  *var = r;
}

Это лучше, у вас есть только 1 условная ветвь на 3 бита.

Если ваш процессор поддерживает 64-битные целые числа, вы можете работать с 4 битами одновременно:

void BitReversedIncrement3(unsigned *var, int bit)
{
  unsigned r = *var, t = 0;

  while (bit >= 3 && !t)
  {
    unsigned tt = (r >> (bit - 3)) & 0xF;
    t = (0xF7B3D591E6A2C48ULL >> (tt * 4)) & 0xF;
    r ^= ((tt ^ t) << (bit - 3));
    bit -= 4;
  }

  if (bit >= 0 && !t)
  {
    t = r & ((1 << (bit + 1)) - 1);
    r ^= t;
    t <<= 3 - bit;
    t = (0xF7B3D591E6A2C48ULL >> (t * 4)) & 0xF;
    t >>= 3 - bit;
    r |= t;
  }

  *var = r;
}

Что еще лучше. И единственная справочная таблица (07351624 или 0xF7B3D591E6A2C48) является крошечной и, вероятно, закодирована как операнд непосредственной инструкции.

Вы можете дополнительно улучшить код, если битовая позиция для обращенного «1» является известной константой. Просто разверните цикл while во вложенные if, замените константу обратной позиции в один бит.

Answer 2

Для больших БПФ уделение внимания блокировке кэша (минимизация общего количества непроизведенных циклов пропадания кэша) может оказать гораздо большее влияние на производительность, чем оптимизация счетчика циклов, взятого путем индексации обращения битов.Постарайтесь не де-оптимизировать больший эффект с помощью большего числа циклов, оптимизируя меньший эффект.Для небольших БПФ, где все умещается в кеше, LUT могут быть хорошим решением, если вы обращаете внимание на любые риски, связанные с использованием нагрузки, следя за тем, чтобы все было или может быть соответствующим образом передано.

Answer 3

Еще один подход к рассмотрению: возьмите хорошо известный алгоритм обращения битов - обычно несколько масок, сдвигов и OR - и затем реализуйте его с помощью SSE, так что вы получите, например, 8 битов по 16 бит по цене одного. Для 16 бит необходимо 5 * log2 (N) = 20 инструкций, поэтому совокупная пропускная способность будет составлять 2,5 инструкции на бит в обратном порядке.