Programar com SIMD

Para contar bytes com sinal inferiores a −2, percorre [−128,−3,0,127,−4,−3,−2]. O primeiro grupo de quatro produz duas ocorrências; os três bytes restantes produzem outras duas. O valor igual a −2 fica excluído porque a comparação é estrita.

A tradução para SIMD precisa de conservar esta contagem e de não ler além dos sete bytes. Começa pela operação escalar, escolhe as vias e verifica comprimento zero, alinhamento, resto e largura do acumulador.

Contar valores que satisfazem uma condição

Pretende-se contar bytes com sinal menores que um limite. Em cada grupo de 4: carrega uma palavra; compara com o limite replicado; converte a máscara de comparação em contagens; soma horizontalmente; avança 4 bytes.

Para replicar um limite negativo, conserva primeiro os 8 bits baixos: andi t0,a2,255. Depois replica por shifts e OR. Replicar diretamente o valor estendido com sinal pode transportar bits altos para as outras vias.

Uma máscara [0xFF,0,0xFF,0xFF] tem três verdadeiros. AND com 0x01010101 produz [1,0,1,1]. Extrai cada byte e soma-o num acumulador escalar: dá 3.

Acumular máscaras com ADD8 durante todo o vetor cria contadores modulares. Ao atingir 256 verdadeiros na mesma via, o contador volta a zero. A alternativa seguinte reduz cada grupo imediatamente e trata o resto sem essa limitação:

def contar_inferiores(valores, limite):
    total = 0
    grupos = len(valores) // 4
    for g in range(grupos):
        grupo = valores[4*g:4*g + 4]
        mascara = [255 if x < limite else 0 for x in grupo]
        total += sum(x & 1 for x in mascara)
    total += sum(x < limite for x in valores[4*grupos:])
    return total

for valores, limite in [([], 0), ([-3, 0, 5, -8, 2], 0), ([-1]*1024, 0)]:
    resultado = contar_inferiores(valores, limite)
    assert resultado == sum(x < limite for x in valores)
    print(resultado)

Para contar ocorrências, troca a comparação por igualdade. Para contar ímpares, AND com 1 em cada byte dá diretamente a máscara 0/1. O acumulador escalar também precisa de largura suficiente para o comprimento máximo.

Traduzir a contagem para registos

Contrato: a0 aponta para bytes com sinal, com base alinhada a 4; a1 é um comprimento entre 0 e 2³¹−1; a2 é um limite entre −128 e 127. O resultado cabe em a0. A rotina altera apenas registos não preservados pelo chamado. O chamador deve guardar os seus valores antes da chamada, se precisar deles depois. A zona de memória deve conter todos os bytes indicados pelo comprimento.

contar_inferiores:
    li t2, 0                 # acumulador escalar
    andi t0, a2, 255
    slli t3, t0, 8
    or t0, t0, t3
    slli t3, t0, 16
    or t0, t0, t3            # limite replicado em quatro bytes
    li t1, 0x01010101
    srli a3, a1, 2           # grupos completos
    andi a4, a1, 3           # bytes restantes
    beqz a3, resto

grupo:
    lw t3, 0(a0)
    scmplt8 t4, t3, t0
    and t4, t4, t1           # quatro contagens 0 ou 1
    srli t5, t4, 16
    add t4, t4, t5
    srli t5, t4, 8
    add t4, t4, t5
    andi t5, t4, 255         # soma dos quatro bytes, entre 0 e 4
    add t2, t2, t5
    addi a0, a0, 4
    addi a3, a3, -1
    bnez a3, grupo

resto:
    beqz a4, fim
    lb t3, 0(a0)
    slt t5, t3, a2
    add t2, t2, t5
    addi a0, a0, 1
    addi a4, a4, -1
    bnez a4, resto

fim:
    mv a0, t2
    ret

A redução usa somas escalares para juntar os quatro bytes da máscara. Cada parcela vale no máximo 1, por isso não há carry entre bytes nestas somas: após o primeiro shift/soma, o byte baixo contém b0+b2 e o seguinte, b1+b3. A segunda soma reúne os quatro no byte baixo. Para a máscara [1,0,1,1], o resultado baixo passa de 2 para 3. Esta justificação vale para contagens 0/1; com contadores arbitrários por via, seria preciso outra análise.

A entrada vazia passa pelas duas verificações e retorna zero sem ler memória. O resto usa lb, para estender o sinal, e compara com o limite original. A linha scmplt8 requer a ISA empacotada; o bloco Python anterior permite conferir a operação em cada via.

Produto interno de meias palavras

Para o produto interno $\sum_i x_i y_i$, cada carga de palavra traz dois elementos de 16 bits. KMDA calcula dois produtos e soma-os num parcial de 32 bits. Mantém x=[2,−3,4,1] e y=[5,6,−2,7]:

Uma soma escalar reúne $−8+(−1)=−9$. Avança os dois apontadores quatro bytes por grupo e trata um eventual elemento restante com cargas de meia palavra. O acumulador precisa de largura para o total; não guardes parciais de 32 bits em vias de 8 bits.

KMDA satura no caso em que as quatro meias palavras valem −32768. Um acumulador mais largo depois da instrução não recupera o valor já saturado. Para uma soma exata nesse caso, usa os dois produtos completos de SMUL16 e acumula-os com largura suficiente. A soma de muitos parciais também pode exceder 32 bits. A ordem de redução de inteiros sem overflow conserva o resultado; para vírgula flutuante pode mudar arredondamentos.

Alterar e somar vetores

Para Y[i]=k×Y[i], replica k em duas meias palavras, faz SMUL16 e guarda os 16 bits de cada produto com duas operações sh, se o contrato garantir que o resultado cabe. O par de produtos 32 bits é uma saída intermédia, não uma palavra empacotada pronta para sw.

Para Z[i]=X[i]+Y[i], ADD16 produz duas somas modulares e sw guarda as duas parcelas. Se a intenção é uma soma matemática com sinal, garante $−32768\le X[i]+Y[i]\le32767$ para cada i.

Uma rotina Y←Y−kX pode chamar a alteração de vetor e a soma, mas deve preservar ra e os argumentos necessários entre chamadas. Também deve deixar claro se pode modificar X. Para conservar X, calcula os produtos em temporários ou guarda em outra área.

Valor absoluto e ajuste

Para Y[i]−d×|X[i]|, SMAX16 entre X e −X funciona exceto no menor inteiro −32768, cujo valor absoluto 32768 não cabe em 16 bits com sinal. Excluir esse valor é uma condição; alargar a representação é outra solução. KABS16 também não calcula o valor exato nesse extremo: satura −32768 em 32767 e assinala overflow. Substituir o absoluto por essa instrução exige aceitar saturação ou excluir o extremo.

Se SMUL16 produz dois produtos 32 bits, SUB16 não pode subtrair diretamente um desses registos como se contivesse ambos os produtos. Primeiro empacota as partes de 16 bits de cada produto, se couberem, ou faz subtrações escalares de 32 bits e guarda os resultados individualmente.

Coordenadas e números complexos

Na ficha, mirrorSeq recebe pontos de 8 bits intercalados em memória: x1,y1,x2,y2. Em little endian, a palavra tem vias [B0,B1,B2,B3]=[x1,y1,x2,y2]. SWAP8 troca bytes dentro de cada meia palavra:

SWAP8 espelha cada ponto trocando x e y. SWAP16 apenas troca a posição dos dois pontos neste formato. Se cada coordenada tiver 16 bits, uma palavra guarda um só ponto (H1,H0)=(y,x) e SWAP16 passa a ser a instrução adequada.

Para complexos, H0 guarda a parte real e H1 a imaginária. O produto é:

Com a=(2,3) e b=(4,−1), os produtos diretos são 8 e −3; os cruzados, −2 e 12. SMUL16 fornece os diretos e SMULX16 os cruzados, em pares de registos de 32 bits. A subtração escalar $8−(−3)=11$ forma a parte real; a soma $−2+12=10$, a imaginária. Só depois empacota (H1,H0)=(10,11), se ambas couberem em 16 bits com sinal.

Custo e limites de SIMD

SIMD reduz instruções aritméticas por elemento, mas os dados têm de chegar aos registos. Replicação de constantes, permutações, alinhamento e restos têm custo. Um vetor curto pode não amortizar a preparação.

A apresentação conta instruções para contar ímpares em N bytes, com N múltiplo de 4 nos exemplos. A versão escalar executa $3+6N$ instruções. As 3 de preparação fixam endereço do vetor, contador e acumulador; cada byte custa 6 instruções no ciclo.

A versão SIMD executa $21+1{,}5N$. As 4 de preparação fixam endereço, número de grupos, máscara 0x01010101 e acumulador; cada grupo de 4 bytes custa 6 instruções. A combinação final dos quatro parciais custa $1+16$: 1 para juntar e 16 da redução escalar.

O resto do vetor fica de fora desta conta. Para N=8, são 51 contra 33; para N=4000, 24003 contra 6021. A razão tende para 4 quando N cresce, porque o ciclo escalar faz 6 instruções por byte e o SIMD faz 6 por cada grupo de 4.

Usa esta comparação para calibrar a intuição, sem a confundir com uma medição de tempo: faltas, paragens e o resto do programa não entram nestas contas.

O ganho teórico de 4 vias só se aplica à parte que efetivamente executa 4 operações em paralelo. Se essa parte ocupava 60% do tempo e melhora 4 vezes, Amdahl dá $1/(0,4+0,6/4)=1,818$, antes de contar custos novos. Não multipliques automaticamente o desempenho total pelo número de vias.