Subtraindo números inteiros de 8 bits em um número inteiro de 64 bits por 1 em paralelo, SWAR sem hardware SIMD

77

Se eu tiver um número inteiro de 64 bits, estou interpretando como uma matriz de números inteiros de 8 bits compactados com 8 elementos. Preciso subtrair a constante 1de cada número inteiro compactado enquanto lida com o estouro sem que o resultado de um elemento afete o resultado de outro elemento.

Eu tenho esse código no momento e funciona, mas preciso de uma solução que faça a subtração de cada número inteiro de 8 bits em paralelo e não faça acessos à memória. No x86, eu poderia usar instruções SIMD como psubbessa subtrai números inteiros de 8 bits em paralelo, mas a plataforma pela qual estou codificando não suporta instruções SIMD. (RISC-V neste caso).

Então, eu estou tentando fazer o SWAR (SIMD dentro de um registro) para cancelar manualmente a propagação entre bytes de a uint64_t, fazendo algo equivalente a isso:

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;
}

Eu acho que você poderia fazer isso com operadores bit a bit, mas não tenho certeza. Estou procurando uma solução que não use instruções SIMD. Estou procurando uma solução em C ou C ++ que seja bastante portátil ou apenas a teoria por trás dela para que eu possa implementar minha própria solução.

cam-white
fonte
5
Eles precisam ter 8 bits ou 7 bits?
tadman 8/01
Eles devem ter 8 bits de desculpa :(
cam-white
12
As técnicas para esse tipo de coisa são chamadas de SWAR
harold
11
você espera que um byte contenha zero para quebrar em 0xff?
Alnitak

Respostas:

75

Se você possui uma CPU com instruções SIMD eficientes, o SSE / MMX paddb( _mm_add_epi8) também é viável. A resposta de Peter Cordes também descreve a sintaxe do vetor GNU C (gcc / clang) e a segurança para UB com alias estrito. Eu recomendo fortemente a revisão dessa resposta também.

Fazer você mesmo uint64_té totalmente portátil, mas ainda requer cuidados para evitar problemas de alinhamento e UB com alias estrito ao acessar uma uint8_tmatriz com a uint64_t*. Você deixou essa parte fora de questão, começando com seus dados em um uint64_tjá, mas para o GNU C um may_aliastypedef resolve o problema (consulte a resposta de Peter para isso oumemcpy ).

Caso contrário, você poderá alocar / declarar seus dados uint64_te acessá-los uint8_t*quando quiser bytes individuais. unsigned char*é permitido alias qualquer coisa para evitar o problema no caso específico de elementos de 8 bits. (Se uint8_texiste, provavelmente é seguro assumir que é um unsigned char.)


Observe que isso é uma alteração de um algoritmo incorreto anterior (consulte o histórico de revisões).

Isso é possível sem loop para subtração arbitrária e fica mais eficiente para uma constante conhecida como 1em cada byte. O principal truque é impedir a execução de cada byte, definindo o bit alto e, em seguida, corrija o resultado da subtração.

Vamos otimizar um pouco a técnica de subtração fornecida aqui . Eles definem:

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

com Hdefinido como 0x8080808080808080U(ou seja, os MSBs de cada número inteiro compactado). Para um decremento, yé 0x0101010101010101U.

Sabemos que ytodos os seus MSBs estão limpos, para que possamos pular uma das etapas da máscara (ou seja, y & ~Hé a mesma ydo nosso caso). O cálculo prossegue da seguinte forma:

  1. Definimos os MSBs de cada componente de x como 1, para que um empréstimo não possa se propagar além do MSB para o próximo componente. Chame isso de entrada ajustada.
  2. Subtraímos 1 de cada componente, subtraindo 0x01010101010101da entrada corrigida. Isso não causa empréstimos entre componentes, graças à etapa 1. Chame isso de saída ajustada.
  3. Agora precisamos corrigir o MSB do resultado. Nós realizamos a saída ajustada com os MSBs invertidos da entrada original para concluir a correção do resultado.

A operação pode ser escrita como:

#define U64MASK 0x0101010101010101U
#define MSBON 0x8080808080808080U
uint64_t decEach(uint64_t i){
      return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON);
}

De preferência, isso é incorporado pelo compilador (use as diretivas do compilador para forçar isso) ou a expressão é escrita embutida como parte de outra função.

Casos de teste:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Detalhes de desempenho

Aqui está o assembly x86_64 para uma única chamada da função. Para um melhor desempenho, ele deve ser alinhado com a esperança de que as constantes possam viver em um registro o maior tempo possível. Em um loop restrito em que as constantes vivem em um registro, o decremento real leva cinco instruções: ou + não + e + adiciona + xor após a otimização. Não vejo alternativas que superariam a otimização do compilador.

uint64t[rax] decEach(rcx):
    movabs  rcx, -9187201950435737472
    mov     rdx, rdi
    or      rdx, rcx
    movabs  rax, -72340172838076673
    add     rax, rdx
    and     rdi, rcx
    xor     rdi, rcx
    xor     rax, rdi
    ret

Com alguns testes da IACA do seguinte trecho:

// Repeat the SWAR dec in a loop as a microbenchmark
uint64_t perftest(uint64_t dummyArg){
    uint64_t dummyCounter = 0;
    uint64_t i = 0x74656a6d27080100U; // another dummy value.
    while(i ^ dummyArg) {
        IACA_START
        uint64_t naive = i - U64MASK;
        i = naive + ((i ^ naive ^ U64MASK) & U64MASK);
        dummyCounter++;
    }
    IACA_END
    return dummyCounter;
}

podemos mostrar que em uma máquina Skylake, a execução do decremento, xor e compare + jump pode ser realizada em pouco menos de 5 ciclos por iteração:

Throughput Analysis Report
--------------------------
Block Throughput: 4.96 Cycles       Throughput Bottleneck: Backend
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.5     0.0  |  1.5  |  0.0     0.0  |  0.0     0.0  |  0.0  |  1.5  |  1.5  |  0.0  |
--------------------------------------------------------------------------------------------------

(Obviamente, no x86-64 você apenas carregaria ou movqem um registro XMM paddb, portanto, pode ser mais interessante ver como ele é compilado para um ISA como o RISC-V.)

nanofarad
fonte
4
Eu preciso do meu código para rodar em máquinas RISC-V que ainda não possuem instruções SIMD (ainda) e muito menos suporte para MMX
cam-white
2
@ cam-white Entendi - este é provavelmente o melhor que você pode fazer então. Vou pular na godbolt para verificar a sanidade do RISC também. Edit: Não há suporte para RISC-V no godbolt :(
nanofarad
7
Na verdade, há suporte para RISC-V no godbolt, por exemplo, como esse (E: parece que o compilador se torna excessivamente criativo ao criar a máscara ..)
harold 08/01
4
Outras leituras sobre como o truque de paridade (também chamado de "vetor de execução") pode ser usado em várias situações: emulators.com/docs/LazyOverflowDetect_Final.pdf
jpa
4
Eu fiz outra edição; Os vetores nativos do GNU C na verdade evitam problemas de aliasing estrito; um vetor de uint8_té permitido alias uint8_tdados. Os chamadores de sua função (que precisam incluir uint8_tdados em a uint64_t) são os que precisam se preocupar com o aliasing estrito! Portanto, provavelmente o OP deve declarar / alocar matrizes apenas uint64_tporque char*é permitido alias qualquer coisa no ISO C ++, mas não vice-versa.
Peter Cordes
16

Para o RISC-V, você provavelmente está usando o GCC / clang.

Curiosidade: O GCC conhece alguns desses truques de bithack do SWAR (mostrados em outras respostas) e pode usá-los para você ao compilar código com vetores nativos do GNU C para destinos sem instruções SIMD de hardware. (Mas o clang para o RISC-V apenas o desenrola ingenuamente para operações escalares, então você precisa fazer isso sozinho se quiser um bom desempenho entre os compiladores).

Uma vantagem da sintaxe do vetor nativo é que, ao direcionar uma máquina com o hardware SIMD, ela será usada em vez de vetorizar automaticamente seu bithack ou algo horrível assim.

Isso facilita a gravação de vector -= scalaroperações; a sintaxe Just Works, transmitindo implicitamente, ou seja, dividindo o escalar para você.


Observe também que uma uint64_t*carga de a uint8_t array[]é UB com alias estrito; portanto, tenha cuidado com isso. (Veja também Por que o strlen da glibc precisa ser tão complicado para ser executado rapidamente? Re: tornando os bithacks do SWAR com alias estrito seguro em C puro). Você pode querer que algo assim declare um uint64_tque possa ser convertido em ponteiro para acessar outros objetos, como o char*funcionamento em ISO C / C ++.

use-os para obter dados do uint8_t em um uint64_t para uso com outras respostas:

// GNU C: gcc/clang/ICC but not MSVC
typedef uint64_t  aliasing_u64 __attribute__((may_alias));  // still requires alignment
typedef uint64_t  aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

A outra maneira de realizar cargas seguras para serrilhado é com memcpy a uint64_t, que também remove o alignof(uint64_t) requisito de alinhamento. Mas em ISAs sem cargas eficientes e desalinhadas, o gcc / clang não memcpyse alinha e otimiza quando não pode provar que o ponteiro está alinhado, o que seria desastroso para o desempenho.

TL: DR: sua melhor aposta é declarar seus dados como uint64_t array[...] ou alocá-los dinamicamente como uint64_t, ou de preferênciaalignas(16) uint64_t array[]; Isso garante alinhamento a pelo menos 8 bytes ou 16, se você especificar alignas.

Como uint8_té quase certo unsigned char*, é seguro acessar os bytes de umuint64_t via uint8_t*(mas não vice-versa para uma matriz uint8_t). Portanto, neste caso especial em que o tipo de elemento estreito é unsigned char, você pode contornar o problema de alias estrito porque charé especial.


Exemplo de sintaxe de vetor nativo GNU C:

Os vetores nativos do GNU C sempre têm permissão para usar o alias com seu tipo subjacente (por exemplo, int __attribute__((vector_size(16)))podem com segurança alias, intmas nãofloat ou uint8_tou qualquer outra coisa.

#include <stdint.h>
#include <stddef.h>

// assumes array is 16-byte aligned
void dec_mem_gnu(uint8_t *array) {
    typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias));
    v16u8 *vecs = (v16u8*) array;
    vecs[0] -= 1;
    vecs[1] -= 1;   // can be done in a loop.
}

Para o RISC-V sem nenhum HW SIMD, você pode vector_size(8)expressar apenas a granularidade que pode usar com eficiência e fazer o dobro de vetores menores.

Mas vector_size(8) compila de maneira estúpida para o x86 com o GCC e o clang: o GCC usa bithacks SWAR em registros de número inteiro GP, clang descompacta elementos de 2 bytes para preencher um registro XMM de 16 bytes e depois repete. (A MMX é tão obsoleta que o GCC / clang nem se importa em usá-lo, pelo menos não para x86-64.)

Mas com vector_size (16)( Godbolt ) obtemos o esperado movdqa/ paddb. (Com um vetor tudo gerado por pcmpeqd same,same). Como -march=skylakeainda temos duas operações XMM separadas em vez de uma YMM, infelizmente os compiladores atuais também não "auto-vectorizam" as operações vetoriais em vetores mais amplos: /

Para o AArch64, não é tão ruim de usar vector_size(8)( Godbolt ); O ARM / AArch64 pode trabalhar nativamente em blocos de 8 ou 16 bytes comd ou qregistradores.

Portanto, você provavelmente deseja vector_size(16)compilar se deseja desempenho portátil em x86, RISC-V, ARM / AArch64 e POWER . No entanto, alguns outros ISAs fazem SIMD em registros inteiros de 64 bits, como MIPS MSA, eu acho.

vector_size(8)facilita a análise do asm (apenas um registro de dados): Godbolt compiler explorer

# GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector

dec_mem_gnu(unsigned char*):
        lui     a4,%hi(.LC1)           # generate address for static constants.
        ld      a5,0(a0)                 # a5 = load from function arg
        ld      a3,%lo(.LC1)(a4)       # a3 = 0x7F7F7F7F7F7F7F7F
        lui     a2,%hi(.LC0)
        ld      a2,%lo(.LC0)(a2)       # a2 = 0x8080808080808080
                             # above here can be hoisted out of loops
        not     a4,a5                  # nx = ~x
        and     a5,a5,a3               # x &= 0x7f... clear high bit
        and     a4,a4,a2               # nx = (~x) & 0x80... inverse high bit isolated
        add     a5,a5,a3               # x += 0x7f...   (128-1)
        xor     a5,a4,a5               # x ^= nx  restore high bit or something.

        sd      a5,0(a0)               # store the result
        ret

Eu acho que é a mesma idéia básica que as outras respostas sem loop; impedindo o transporte e fixando o resultado.

Estas são 5 instruções da ULA, pior que a resposta principal, eu acho. Mas parece que a latência do caminho crítico é de apenas 3 ciclos, com duas cadeias de 2 instruções, cada uma levando ao XOR. A resposta de @Reinstate Monica - ζ - é compilada em uma cadeia dep de 4 ciclos (para x86). A taxa de transferência de loop de 5 ciclos é um gargalo, incluindo também um ingênuosub no caminho crítico, e o loop afunila na latência.

No entanto, isso é inútil com o clang. Ele nem adiciona e armazena na mesma ordem em que foi carregado, por isso não está fazendo um bom pipelining de software!

# RISC-V clang (trunk) -O3
dec_mem_gnu(unsigned char*):
        lb      a6, 7(a0)
        lb      a7, 6(a0)
        lb      t0, 5(a0)
...
        addi    t1, a5, -1
        addi    t2, a1, -1
        addi    t3, a2, -1
...
        sb      a2, 7(a0)
        sb      a1, 6(a0)
        sb      a5, 5(a0)
...
        ret
Peter Cordes
fonte
13

Eu apontaria que o código que você escreveu realmente vetoriza quando você começa a lidar com mais de um único uint64_t.

https://godbolt.org/z/J9DRzd

robthebloke
fonte
11
Você poderia explicar ou dar uma referência ao que está acontecendo lá? Parece bem interessante.
n314159 8/01
2
Eu estava tentando fazer isso sem instruções SIMD, mas achei isso interessante :)
cam-white
8
Por outro lado, esse código SIMD é horrível. O compilador entendeu completamente o que está acontecendo aqui. E: é um exemplo de "isso foi claramente feito por um compilador porque nenhum humano seria tão estúpido"
harold
11
@ PeterCordes: Eu estava pensando mais ao longo das linhas de uma __vector_loop(index, start, past, pad)construção que uma implementação poderia tratar como for(index=start; index<past; index++)[o que significa que qualquer implementação poderia processar código usando-a, apenas definindo uma macro], mas que teria uma semântica mais vaga para convidar um compilador para processar as coisas. qualquer tamanho de bloco de potência de dois até pad, estendendo o início para baixo e terminando para cima se ainda não forem múltiplos do tamanho do bloco. Os efeitos colaterais dentro de cada pedaço seria unsequenced, e se um breakocorre dentro do loop, outros representantes ...
supercat
11
@ PeterCordes: Embora restrictseja útil (e seria mais útil se a Norma reconhecesse um conceito de "pelo menos potencialmente baseado em" e depois definido "baseado em" e "pelo menos potencialmente baseado em" diretamente sem casos de canto patetas e impraticáveis) minha proposta também permitiria que um compilador executasse mais execuções do loop do que o solicitado - algo que simplificaria bastante a vetorização, mas para o qual o Padrão não faz nenhuma provisão.
supercat 8/01
11

Você pode garantir que a subtração não transborde e conserte o bit alto:

uint64_t sub(uint64_t arg) {
    uint64_t x1 = arg | 0x80808080808080;
    uint64_t x2 = ~arg & 0x80808080808080;
    // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction
    return (x1 - 0x101010101010101) ^ x2;
}
Falk Hüffner
fonte
Eu acho que funciona para todos os 256 valores possíveis de um byte; Coloquei no Godbolt (com RISC-V) godbolt.org/z/DGL9aq para ver os resultados de propagação constante de várias entradas como 0x0, 0x7f, 0x80 e 0xff (deslocadas para o meio do número). Parece bom. Acho que a resposta principal se resume à mesma coisa, mas explica de uma maneira mais complicada.
Peter Cordes
Os compiladores poderiam fazer um trabalho melhor construindo constantes nos registros aqui. clang passa muitas instruções construindo splat(0x01)e splat(0x80), em vez de obter uma da outra com um turno. Mesmo escrever dessa maneira na fonte godbolt.org/z/6y9v-u não impede o compilador de criar código melhor; apenas faz propagação constante.
Peter Cordes
Eu me pergunto por que não carrega apenas a constante da memória; é isso que os compiladores para Alpha (uma arquitetura semelhante) fazem.
Falk Hüffner
GCC para RISC-V faz constantes de carga da memória. Parece que o clang precisa de algum ajuste, a menos que sejam esperadas falhas no cache de dados e sejam caras em comparação com o rendimento da instrução. (Esse equilíbrio certamente pode ter mudado desde Alpha, e presumivelmente diferentes implementações do RISC-V são diferentes. Os compiladores também poderiam fazer muito melhor se percebessem que era um padrão repetitivo que poderiam mudar / OU para ampliar depois de iniciar com uma LUI / add . para 20 + 12 = 32 bits de dados imediatos imediato bit-padrão de AArch64 poderia mesmo utilizar estes como imediatos para E / OU XOR, descodificar inteligente escolha / densidade vs)
Pedro Cordes
Foi adicionada uma resposta mostrando o vetor nativo do GCC, SWAR para RISC-V
Peter Cordes
7

Não tenho certeza se é isso que você deseja, mas ele faz as 8 subtrações em paralelo entre si:

#include <cstdint>

constexpr uint64_t mask = 0x0101010101010101;

uint64_t sub(uint64_t arg) {
    uint64_t mask_cp = mask;
    for(auto i = 0; i < 8 && mask_cp; ++i) {
        uint64_t new_mask = (arg & mask_cp) ^ mask_cp;
        arg = arg ^ mask_cp;
        mask_cp = new_mask << 1;
    }
    return arg;
}

Explicação: A máscara de bit começa com 1 em cada um dos números de 8 bits. Nós concordamos com nosso argumento. Se tivéssemos um 1 nesse local, subtraímos 1 e temos que parar. Isso é feito configurando o bit correspondente como 0 em new_mask. Se tivéssemos um 0, definimos como 1 e temos que realizar o transporte, para que o bit permaneça 1 e deslocamos a máscara para a esquerda. É melhor você verificar se a geração da nova máscara funciona como pretendido, acho que sim, mas uma segunda opinião não seria ruim.

PS: Na verdade, não tenho certeza se a verificação de mask_cpnão ser nulo no loop pode atrasar o programa. Sem ele, o código ainda estaria correto (uma vez que a máscara 0 simplesmente não faz nada) e seria muito mais fácil para o compilador desenrolar o loop.

n314159
fonte
for não vai funcionar em paralelo, você está confuso com for_each ?
LTPCGO
3
@LTPCGO Não, não é minha intenção paralelizar isso para o loop for, isso realmente quebraria o algoritmo. Mas esse código funciona nos diferentes números inteiros de 8 bits no número inteiro de 64 bits em paralelo, ou seja, todas as 8 subtrações são feitas simultaneamente, mas precisam de até 8 etapas.
n314159
Sei que o que estava perguntando poderia ter sido um pouco irracional, mas isso foi bem próximo do que eu precisava, graças :)
cam-white
4
int subtractone(int x) 
{
    int f = 1; 

    // Flip all the set bits until we find a 1 at position y
    while (!(x & f)) { 
        x = x^f; 
        f <<= 1; 
    } 

    return x^f; // return answer but remember to flip the 1 at y
} 

Você pode fazer isso com operações bit a bit usando o descrito acima, e basta dividir seu número inteiro em partes de 8 bits para enviar 8 vezes para esta função. A parte a seguir foi retirada de Como dividir um número de 64 bits em oito valores de 8 bits? comigo adicionando na função acima

uint64_t v= _64bitVariable;
uint8_t i=0,parts[8]={0};
do parts[i++] = subtractone(v&0xFF); while (v>>=8);

É válido C ou C ++, independentemente de como alguém se deparar com isso

LTPCGO
fonte
5
Porém, isso não paralela o trabalho, que é a pergunta do OP.
nickelpro
Sim, o @nickelpro está certo, isso faria cada subtração uma após a outra, eu gostaria de subtrair todos os números inteiros de 8 bits ao mesmo tempo. Agradeço a resposta tho graças bro
cam-white
2
@nickelpro, quando iniciei a resposta, a edição não havia sido feita, que indicava a parte paralela da pergunta e, por isso, não a notei até o final do envio, deixará de lado se for útil para outras pessoas, pois pelo menos responde às perguntas. parte para fazer operações bit a bit e poderia ser feito para trabalhar em paralelo utilizando em for_each(std::execution::par_unseq,...vez de
whiles
2
É ruim, eu enviei a pergunta e percebi que não disse que precisava ser paralela, então editada
cam-white
2

Não tentando criar o código, mas para um decréscimo de 1, você pode diminuir pelo grupo de 8 1s e depois verificar se os LSBs dos resultados foram "invertidos". Qualquer LSB que não tenha sido alternado indica que ocorreu uma transferência dos 8 bits adjacentes. Deve ser possível elaborar uma sequência de ANDs / ORs / XORs para lidar com isso, sem ramificações.

Hot Licks
fonte
Isso pode funcionar, mas considere o caso em que um carry se propaga por um grupo de 8 bits e em outro. A estratégia nas boas respostas (de definir o MSB ou algo primeiro) para garantir que o carry não se propague é provavelmente pelo menos tão eficiente quanto possível. O objetivo atual a ser atingido (ou seja, as boas respostas sem ramificação) são 5 instruções RISC-V asm ALU com paralelismo no nível das instruções, tornando o caminho crítico apenas 3 ciclos e usando duas constantes de 64 bits.
Peter Cordes
0

Concentre o trabalho em cada byte completamente sozinho e coloque-o de volta onde estava.

uint64_t sub(uint64_t arg) {
   uint64_t res = 0;

   for (int i = 0; i < 64; i+=8) 
     res += ((arg >> i) - 1 & 0xFFU) << i;

    return res;
   }
nonock
fonte