думаю, начать стоит с

_mm256_shuffle_ps
_mm256_permute_ps
_mm256_blend_ps

Отдельные «И» можно заменить на побитовое «И» между двумя регистрами. «ИЛИ» можно заменить на сранение регистра с нулём, т.к. если есть хоть один ненулевой бит, «ИЛИ» даст 1. Больше всего времени займёт расположение битов в нужном порядке.

Они же все работают со столбцами действительных чисел. А ТСу нужны биты (полагаю, что операнды у него в «упакованном» виде, т. е. затраты на преобразование будут сравнимы с затратами на вычисление)...

сдвиги

Сколько разных «формул» ожидается? Известны ли все используемые «формулы» на момент запуска алгоритма? Если нет, то как часто они будут меняться (сколько пар операндов будет обработано по одной формуле до её смены)?

К чему я клоню: к табличке из всех возможных результатов операции. Для двух полубайт табличка займёт всего 256 байт, а для двух байт — 64K. Последнее, конечно, в L1 не влезает, но в L2 точно. Бегло посмотрел на MMX/SSE — там ничего подобного нет, потому что оно создавалось для другого (для работы со столбцами из floating-point чисел, а у тебя биты; см. пред. ответ). prischeyadro прав, сложнее всего с выборкой/перемешиванием отдельных битов.

Подсказка:

   b1  b2  b3  b4
-0-
a1  .   .   .   .
a2  .   .   .   *
a3  .   .   *   .
a4  .   .   *   *
-1-
a1  .   *   .   *
a2  .   *   *   .
a3  .   *   *   *
a4  *   .   .   .
...
-F-
a1  *   *   .   .
a2  *   *   .   *
a3  *   *   *   .
a4  *   *   *   *

Имеем 4 (аргумент a) + 4 (аргумент b) + 16 (результат) = 24 бит. Столько бит достаточно, что бы закодировать любую твою операцию. Теперь разработай метод получения операции по конкретному числу и будет тебе щастье.

Ах да, я дегенерат: поскольку у тебя результат операции — это один бит, табличку тоже можно упаковать, и тогда в L1 она спокойно влезет даже для операндов байтового размера.

Сколько разных «формул» ожидается? Известны ли все используемые «формулы» на момент запуска алгоритма? Если нет, то как часто они будут меняться (сколько пар операндов будет обработано по одной формуле до её смены)?

Формулы заранее неизвестны. Они определяются входными данными (типа обучение).
Вообще хочется сделать реализацию логических схем по типу такого: https://ru.wikipedia.org/wiki/Карта_Карно (не лучшее описание, если надо расскажу короче). Я только упростил задачу полагая что в перемножении (логическое И) лишь два аргумента. Ну, и формулы не упрощаются, иначе алгоритм совсем усложнится.

Ну, и еще фишка в том, что данных обрабатывать нужно много, потому нужна скорость.

Для двух полубайт табличка займёт всего 256 байт, а для двух байт — 64K.

Это первое что мне пришло в голову. Потенциально длинна входного блока больше, так что не подходит.

prischeyadro прав, сложнее всего с выборкой/перемешиванием отдельных битов.

Впринципе, алгоритм реалиуется парой логических операций. Не пробовал, но по идее так:

b*bm1*a*am1 + b*bm2*a*am2 + b*bm3*a*am3 + b*bm4*a*am4

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

Еще по идее можно разложить на операции с матрицами (эх, матан, пока не смог вспомнить, но уверен что есть).

Бегло посмотрел на MMX/SSE — там ничего подобного нет

Странно, мне казалось, что это типовая задача. А операций с битовыми матрицами тоже нет?

Бегло посмотрел на MMX/SSE — там ничего подобного нет

Странно, мне казалось, что это типовая задача. А операций с битовыми матрицами тоже нет?

Есть там битовая арифметика, это intelfx слишком уж бегло смотрел. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ - выбирай слева «Bit manipulation», «Logical», «Shift» и т.п., будет видно что можно сделать

В разделе 7.1.3 у Кнута описываются битовые трюки, может будет полезно глянуть. Прямо решения задачи там не будет, но есть всякие перемешивания бит и различное комбинирование, какие-то идеи может пригодятся. Там же говорится, что в реальных процессорах в отличии от MMIX, таких инструкций, к сожалению, нет. При этом для 32- и 64-битных чисел там есть быстрые варианты ряда операций, для больших размеров сложнее.

https://software.intel.com/sites/landingpage/IntrinsicsGuide/

Забавный сайт, спасибо.

Просмотрел бегло. Вариантов с битовыми матрицами не нашел, но много инструкций AVX-512, которые могут помочь алгоритму выше. Правда, я так понял, что это не шибко популярный набор инструкций. Эх... :(

В разделе 7.1.3 у Кнута

Вопрос не в алгоритме. Придумать алгоритм не сложно. Вопрос в скорости - процессорных инструкциях.

Вопрос не в алгоритме. Придумать алгоритм не сложно. Вопрос в скорости - процессорных инструкциях.

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

Почитай что такое ДНФ (дизьюктивная нормальная форма) для булевой функции 2х аргументов, вот тебе нужно её построить для случая когда функция задана таблицей. Математика умеет искаропки.

а что, царя еще не вносили?