Nano Hash - криптовалюты, майнинг, программирование

Вычитание по диапазонам бит

У меня есть набор из 22 5-битных значений (0-31), которые упакованы вместе как 110 бит в два 64-битных целых числа без знака (т.е. последние 18 бит всегда равны нулю). Я хочу разработать функцию, которая для каждого сегмента из 5 бит будет выполнять разность абсолютных значений.

Мне известны методы вычитания с использованием побитовых операторов для одного числа, но здесь я не хочу беспокоиться о переполнении между 5-битными сегментами. Я ищу решение, использующее побитовые операторы и / или операции сборки x86, желательно без каких-либо циклов.

РЕДАКТИРОВАТЬ: Чтобы уточнить, у меня будут пары из этих 110 бит, над которыми я хочу выполнить эту операцию разницы. Любые предложения приветствуются.

РЕШЕНИЕ: Спасибо @EOF за предложение инструкции VPSADBW. Вместо этого я собираюсь использовать 8-битные числа в пользу более быстрого (и более читаемого) кода.

c x86-64 x86 optimization bit-manipulation
10.05.2017

  • Не могли бы вы прояснить - в чем разница по абсолютной величине одного значения? (Я знаю только разницу между двумя значениями.) 10.05.2017
  • Также это похоже на код для моего запроса. 10.05.2017
  • Я подозреваю, что самой неприятной частью будет 5-битное число, охватывающее два uint64_t. 10.05.2017
  • @EOF, возможно, способ обойти это - разместить 18 свободных битов ближе к концу каждого uint64s, а не собирать их вместе. 10.05.2017
  • @AjayBrahmakshatriya: Да, сделать 11 5-битных чисел в одном uint64_t и использовать два из них, очевидно, более разумно и, вероятно, более пригодно для повторного использования. 10.05.2017
  • Покажите свою попытку (немного кода C), и где она потерпела неудачу. 10.05.2017
  • Я могу разделить его на 55/55 вместо 64/46, чтобы избежать растяжения. Я не уверен, есть ли здесь какие-нибудь операции перетасовки, которые могут быть здесь полезны. Настоящая борьба в том, что я работаю с 5 битами вместо 4 ... 10.05.2017
  • @EOF Я имел в виду очень хорошую схему, но мне не хватает 1 ровно 1 бит. Я думал дать по 6 бит каждому и использовать 1 бит для переноса. Таким образом, перед вычитанием мы можем установить все переносы и вычесть. Но для этого потребуется 66 бит. У нас всего 64 + 1 (фактический перенос) = 65 бит. 10.05.2017
  • Следующий очевидный вопрос: будет ли использование 8-битных чисел на самом деле каким-либо образом снижать производительность, учитывая, что вы легко найдете подходящие инструкции SIMD для тех, кто работает на многих архитектурах, потенциально давая вам много ускорения (AVX2 может делать 32 из них одновременно, AVX512 с соответствующим расширением 64, ARM NEON 16 ...) 10.05.2017
  • У меня будет ~ 41 миллион этих 110-битных сегментов, и мне нужно проделать эту операцию с каждой парой. Использование 8-битных чисел казалось бесполезным, но на самом деле мне нужен быстрый код. Я предполагаю, что есть инструкция для абсолютной разницы значений 2 8-битных чисел? 10.05.2017
  • Если вы сначала выполните замену так, чтобы большие сегменты были в одном операнде, а затем выполните обычное вычитание, он никогда не переполнится. 10.05.2017
  • @WillCunningham: Ну, на x86 есть [V]PSADBW, который дает вам сумму абсолютных различий между двумя векторами uint8_ts. Я не думаю, что в x86 есть инструкция для самих абсолютных различий, но в ARM NEON есть: VABD. На x86 вам могут понадобиться две инструкции, [V]PSUBB и [V]PABSB. 10.05.2017
  • Да! VPSADBW - это то, что я хочу. После операции, которую я описал, мне нужно убедиться, что сумма всех 5-битных чисел меньше 3, и в зависимости от значений, которые могут принимать данные, это будет сделано. 10.05.2017
  • Небольшое предостережение: VPSADBW дает вам две или четыре частичных суммы абсолютных различий (по одной из каждой серии из 8 различий, в зависимости от того, используете ли вы 128-битную или 256-битную форму) , вам, вероятно, понадобится несколько дополнительных инструкций в конце, чтобы получить общую сумму. 10.05.2017
  • Да, добавлю горизонтальную надстройку. 10.05.2017
  • Если вы вычитаете A из B, гарантировано ли, что все 22 набора в A будут меньше, чем в B? Если нет, то каков должен быть результат? Отрицательное число в 5 битах? 10.05.2017
  • Нет, к сожалению нет. 10.05.2017

Ответы:


1

Вы можете использовать pdep с маской типа 0b000111111000111111..., чтобы разбросать ваши 5-битные целые числа по 8-битным полям и использовать побайтовую информацию SIMD, о которой говорилось в комментариях выше.

В качестве альтернативы вы можете развернуть их в 6-битные поля и с дополнительным битом, установленным на 1, и выполнить вычитание в 64-битных словах, но тогда вам нужно будет найти некоторые небрежный способ выполнить часть" абс "в стиле SWAR. Я подозреваю, что SIMD будет быстрее.

Имейте в виду, что pdep имеет ужасную производительность на процессорах AMD: пропускная способность хуже в 18 раз!

10.05.2017

2

Я думаю, что лучше всего использовать инструкцию pdep (параллельный битовый депозит) на последних процессорах x86. Вы можете использовать это, чтобы быстро преобразовать ваши 5-битные значения в 8-битные значения. Как только они являются 8-битными значениями, вы можете выполнить множество инструкций SSE.

Следующее принимает 128-битное значение в rdx:rax и выводит xmm1:xmm0 с разделением в байтах.

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

mov r8, abs 0x1F1F1F1F1F1F1F1F

pdep rcx, rax, r8
movq xmm0, rcx

shrd rax, rdx, 16
shr rax, 40 - 16
pdep rax, rax, r8
pinsrq xmm0, rax, 1

shr rdx, 16
pdep rdx, rdx, r8
movq xmm1, rdx

Обратное преобразование аналогично, с pext вместо pdep.

10.05.2017
  • Спасибо! Это будет полезно. 10.05.2017
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..