Если у меня есть 64-разрядное целое число, которое я интерпретирую как массив упакованных 8-разрядных целых чисел с 8 элементами. Мне нужно вычесть константу 1
из каждого упакованного целого числа при обработке переполнения без влияния одного элемента на результат другого элемента.
У меня есть этот код на данный момент, и он работает, но мне нужно решение, которое выполняет вычитание каждого упакованного 8-битного целого числа параллельно и не осуществляет доступ к памяти. На x86 я мог бы использовать SIMD-инструкции, подобные psubb
этим, вычитая упакованные 8-битные целые числа параллельно, но платформа, для которой я кодирую, не поддерживает SIMD-инструкции. (RISC-V в этом случае).
Поэтому я пытаюсь сделать SWAR (SIMD внутри регистра), чтобы вручную отменить перенос переноса между байтами a uint64_t
, делая что-то эквивалентное этому:
uint64_t sub(uint64_t arg) {
uint8_t* packed = (uint8_t*) &arg;
for (size_t i = 0; i < sizeof(uint64_t); ++i) {
packed[i] -= 1;
}
return arg;
}
Я думаю, что вы могли бы сделать это с побитовыми операторами, но я не уверен. Я ищу решение, которое не использует инструкции SIMD. Я ищу решение на C или C ++, которое достаточно переносимо, или просто теорию, которая стоит за ним, чтобы я мог реализовать свое собственное решение.
Ответы:
Если у вас есть процессор с эффективными инструкциями SIMD, SSE / MMX
paddb
(_mm_add_epi8
) также является жизнеспособным. В ответе Питера Кордеса также описывается векторный синтаксис GNU C (gcc / clang) и безопасность для строго псевдонимов UB. Я настоятельно рекомендую также рассмотреть этот ответ.Делать это самостоятельно с
uint64_t
полностью переносимым, но все же требует осторожности, чтобы избежать проблем с выравниванием и строгим псевдонимом UB при доступе кuint8_t
массиву с помощьюuint64_t*
. Вы оставили эту часть вне вопроса, начав с ваших данныхuint64_t
уже, но для GNU Cmay_alias
typedef решает проблему (см. Ответ Питера илиmemcpy
).В противном случае вы можете выделить / объявить ваши данные как
uint64_t
и получить к ним доступ,uint8_t*
когда вам нужны отдельные байты.unsigned char*
разрешено создавать псевдонимы, чтобы обойти проблему для конкретного случая 8-битных элементов. (Еслиuint8_t
существует вообще, вероятно, можно предположить, что этоunsigned char
.)Обратите внимание, что это изменение от предыдущего неправильного алгоритма (см. Историю изменений).
Это возможно без зацикливания для произвольного вычитания и становится более эффективным для известной константы, как
1
в каждом байте. Основная хитрость заключается в том, чтобы предотвратить перенос каждого байта путем установки старшего бита, а затем исправить результат вычитания.Мы собираемся немного оптимизировать технику вычитания, приведенную здесь . Они определяют:
с
H
определенным как0x8080808080808080U
(то есть MSB каждого упакованного целого числа). Для декрементаy
есть0x0101010101010101U
.Мы знаем, что
y
все его MSB очищены, поэтому мы можем пропустить один из шагов маски (т. Е. Такойy & ~H
же, какy
в нашем случае). Расчет происходит следующим образом:x
1, чтобы заем не мог распространяться за MSB до следующего компонента. Назовите это настроенным входом.0x01010101010101
из скорректированного ввода. Это не вызывает межкомпонентные заимствования благодаря шагу 1. Назовите это скорректированным выходом.Операция может быть записана как:
Предпочтительно, это указывается компилятором (используйте директивы компилятора, чтобы принудительно это сделать), или выражение записывается как часть другой функции.
Testcases:
Детали исполнения
Вот сборка x86_64 для одного вызова функции. Для лучшей производительности это должно быть выражено надеждой на то, что константы могут жить в регистре как можно дольше. В узком цикле, где константы живут в регистре, фактический декремент принимает пять инструкций: или + не + и + добавить + xor после оптимизации. Я не вижу альтернатив, которые бы побили оптимизацию компилятора.
С некоторыми испытаниями IACA следующего фрагмента:
мы можем показать, что на машине Skylake выполнение декремента, xor и сравнения + прыжок может быть выполнено всего за 5 циклов за итерацию:
(Конечно, на x86-64 вы просто загрузите или
movq
в регистр XMMpaddb
, так что может быть интереснее посмотреть, как он компилируется для ISA, такого как RISC-V.)источник
uint8_t
допускается для псевдонимовuint8_t
данных. Вызывающие вашу функцию (которые должны получитьuint8_t
данные вuint64_t
) должны беспокоиться о строгом псевдониме! Поэтому, вероятно, OP должен просто объявить / распределить массивы,uint64_t
потому чтоchar*
ему разрешено псевдоним в ISO C ++, но не наоборот.Для RISC-V вы, вероятно, используете GCC / clang.
Интересный факт: GCC знает некоторые из этих хитростей SWAR-трюков (показанных в других ответах) и может использовать их для вас при компиляции кода с собственными векторами GNU C для целей без аппаратных инструкций SIMD. (Но clang для RISC-V просто наивно развернет его для скалярных операций, поэтому вам придется делать это самостоятельно, если вы хотите добиться хорошей производительности на всех компиляторах).
Одно из преимуществ нативного векторного синтаксиса заключается в том, что при нацеливании на компьютер с аппаратным SIMD он будет использовать его вместо автоматической векторизации вашего битхака или чего-то ужасного в этом роде.
Это облегчает написание
vector -= scalar
операций; синтаксис Just Works, неявно транслирующий для вас скаляр.Также обратите внимание, что
uint64_t*
загрузка изuint8_t array[]
UB строго псевдонимов, так что будьте осторожны с этим. (См. Также Почему strlen glibc должен быть настолько сложным, чтобы быстро запускаться? Re: обеспечение безопасности строгих псевдонимов SWAR в чистом C). Возможно, вы захотите, чтобы что-то вроде этого объявляло,uint64_t
что вы можете приводить указатели для доступа к любым другим объектам, например, как этоchar*
работает в ISO C / C ++.используйте их, чтобы получить данные uint8_t в uint64_t для использования с другими ответами:
Другой способ выполнить безопасные с точки зрения псевдонимов нагрузки заключается
memcpy
в использовании параметраuint64_t
, который также устраняетalignof(uint64_t
требование выравнивания. Но на ISA без эффективных невыровненных нагрузок gcc / clang не встроен и не оптимизируется,memcpy
когда не может доказать, что указатель выровнен, что может иметь катастрофические последствия для производительности.TL: DR: вам лучше всего объявить ваши данные как
uint64_t array[...]
или выделить их динамически какuint64_t
, или, что желательно,alignas(16) uint64_t array[];
что обеспечивает выравнивание по крайней мере до 8 байтов, или 16, если вы укажетеalignas
.Поскольку
uint8_t
это почти навернякаunsigned char*
, это безопасный доступ к байтамuint64_t
viauint8_t*
(но не наоборот для массива uint8_t). Таким образом, для этого особого случая, когда тип элемента узкийunsigned char
, вы можете обойти проблему строгого псевдонима, потому чтоchar
она особенная.Пример синтаксиса собственного вектора GNU C:
GNU C родные векторы всегда может псевдоним с их базовым типом (например ,
int __attribute__((vector_size(16)))
может безопасно псевдоним ,int
но неfloat
илиuint8_t
или что - нибудь еще.Для RISC-V без какого-либо HW SIMD вы могли бы использовать
vector_size(8)
для выражения только степень детализации, которую вы можете эффективно использовать, и сделать в два раза больше меньших векторов.Но
vector_size(8)
для x86 очень тупо компилируется как с GCC, так и clang: GCC использует битовые хаки SWAR в целочисленных регистрах GP, clang распаковывает в 2-байтовые элементы для заполнения 16-байтового регистра XMM, а затем перепаковывает. (MMX настолько устарел, что GCC / clang даже не потрудился использовать его, по крайней мере, для x86-64.)Но с помощью
vector_size (16)
( Godbolt ) мы получаем ожидаемоеmovdqa
/paddb
. (С вектором «все единицы», сгенерированнымpcmpeqd same,same
). При этом-march=skylake
мы по-прежнему получаем две отдельные операции XMM вместо одной YMM, поэтому, к сожалению, современные компиляторы также не «автоматически векторизуют» векторные операции в более широкие векторы: /Для AArch64 это не так уж плохо в использовании
vector_size(8)
( Godbolt ); ARM / AArch64 может работать в 8- или 16-байтовых чанках с регистрамиd
илиq
.Так что вы, вероятно, захотите
vector_size(16)
на самом деле скомпилировать, если вам нужна портативная производительность для x86, RISC-V, ARM / AArch64 и POWER . Однако некоторые другие ISA выполняют SIMD в 64-битных целочисленных регистрах, например, MIPS MSA, я думаю.vector_size(8)
облегчает просмотр asm (только один регистр данных): проводник компилятора GodboltЯ думаю, что это та же самая основная идея, что и другие нецикличные ответы; предотвращение переноса и исправление результата.
Это 5 инструкций ALU, хуже, чем главный ответ, я думаю. Но похоже, что задержка критического пути составляет всего 3 цикла, с двумя цепочками по 2 инструкции, каждая из которых ведет к XOR. Ответ @Reinstate Monica - ζ - компилируется в 4-тактную цепочку dep (для x86). Пропускная способность цикла с 5 циклами является узким местом, в том числе путем наивности
sub
на критическом пути, а цикл создает узкое место с задержкой.Тем не менее, это бесполезно с лязгом. Он даже не добавляет и не хранит в том же порядке, в котором загружен, поэтому он даже не выполняет хорошую программную конвейеризацию!
источник
Я хотел бы отметить, что код, который вы написали, на самом деле векторизируется, когда вы начинаете работать с более чем одним uint64_t.
https://godbolt.org/z/J9DRzd
источник
__vector_loop(index, start, past, pad)
конструкции, которую реализация может трактовать какfor(index=start; index<past; index++)
[то есть любая реализация может обрабатывать код, используя ее, просто путем определения макроса], но которая будет иметь более слабую семантику, чтобы пригласить компилятор обрабатывать вещи в любой размер фрагмента степени дваpad
, расширяющий начало вниз и конец вверх, если они еще не кратны размеру фрагмента. Побочные эффекты в каждом чанке не были бы последовательными, и еслиbreak
в цикле возникает a , другие представители ...restrict
это полезно (и было бы более полезно, если бы Стандарт признал концепцию «по крайней мере, потенциально основанную на», а затем определил «на основе» и «по крайней мере, потенциально основанную на» напрямую, без глупых и неработающих угловых случаев) Мое предложение также позволило бы компилятору выполнять больше циклов, чем запрошено, что значительно упростит векторизацию, но для этого в стандарте не предусмотрено никаких условий.Вы можете убедиться, что вычитание не переполняется, а затем исправить старший бит:
источник
splat(0x01)
иsplat(0x80)
вместо того, чтобы получать одну от другой за смену. Даже если написать так в исходном коде, godbolt.org/z/6y9v-u не помогает компилятору создавать лучший код; это просто делает постоянное распространение.Не уверен, что это то, что вам нужно, но он выполняет 8 вычитаний параллельно друг другу:
Объяснение: Битовая маска начинается с 1 в каждом из 8-битных чисел. Мы исправим это с помощью нашего аргумента. Если у нас была 1 в этом месте, мы вычли 1 и должны остановиться. Это делается путем установки соответствующего бита в 0 в new_mask. Если у нас был 0, мы устанавливаем его в 1 и должны выполнять перенос, поэтому бит остается на 1, и мы смещаем маску влево. Вы лучше сами убедитесь, что генерация новой маски работает, как задумано, я так думаю, но второе мнение не будет плохим.
PS: Я на самом деле не уверен, что проверка на
mask_cp
ненулевое значение в цикле может замедлить работу программы. Без него код по-прежнему был бы корректным (поскольку маска 0 просто ничего не делает), и компилятору было бы намного проще выполнить развертывание цикла.источник
for
не будет работать параллельно, вас смущаетfor_each
?Вы можете сделать это с помощью побитовых операций, используя вышеизложенное, и вам просто нужно разделить ваше целое число на 8 битных частей, чтобы отправить 8 раз в эту функцию. Следующая часть была взята из раздела Как разбить 64-битное число на восемь 8-битных значений? со мной добавив в вышеупомянутой функции
Это действительно C или C ++ независимо от того, как кто-то сталкивается с этим
источник
for_each(std::execution::par_unseq,...
Не буду пытаться придумать код, но для уменьшения на 1 вы можете уменьшить на группу 8 1, а затем проверить, чтобы убедиться, что младшие биты результатов «перевернулись». Любой LSB, который не переключался, указывает, что перенос произошел из соседних 8 битов. Должна быть возможность разработать последовательность операций AND / ORs / XOR, чтобы справиться с этим, без каких-либо ветвей.
источник
Сосредоточьте работу на каждом байте в одиночку, затем верните его туда, где он был.
источник