# Programar com SIMD

Contagens, produtos internos, vetores e números complexos com condições de largura.

Página: https://resumos.rgo.pt/cadeiras/ac/programar-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:

**main.py**

```python
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]`:

| Elementos | Produtos | Parcial KMDA |
| --- | --- | --- |
| 0 e 1 | $2\times5=10$; $(−3)\times6=−18$ | −8 |
| 2 e 3 | $4\times(−2)=−8$; $1\times7=7$ | −1 |

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:

| Estado | B0 | B1 | B2 | B3 |
| --- | --- | --- | --- | --- |
| Antes | x1 | y1 | x2 | y2 |
| SWAP8 | y1 | x1 | y2 | x2 |
| SWAP16 | x2 | y2 | x1 | y1 |

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 é:

$$
\begin{aligned} \Re(ab)&=a_rb_r-a_ib_i,\\ \Im(ab)&=a_rb_i+a_ib_r. \end{aligned}
$$

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.

## Exercícios

Detetar overflow de contagens

Um contador ADD8 acumula 0xFF para 256 comparações verdadeiras na mesma via, e no fim troca sinal com SUB8(0, contador). Que contagem devolve essa via?

Pista

O acumulador tem só 8 bits.

Solução

Devolve 0, embora houvesse 256 verdadeiros. Reduzir cada grupo num acumulador escalar mais largo evita esse wrap; outra opção exige um limite explícito por via.

Erros frequentes

Supor que a troca de sinal recupera bits já descartados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#contar-valores-que-satisfazem-uma-condi%C3%A7%C3%A3o)

Traduzir o produto interno e conferir largura

Para x=\[2,−3,4,1\] e y=\[5,6,−2,7\], com elementos de 16 bits, sem overflow neste vetor, descreve um ciclo SIMD que calcule o produto interno. Indica cargas, parciais e avanço dos apontadores. Se um par dos dois vetores fosse \[−32768,−32768\], bastaria alargar o acumulador após KMDA para obter a soma exata?

Solução

Cada par usa lw em x e y, KMDA e uma soma escalar no acumulador. Avança os dois apontadores 4 bytes. Os parciais são 2×5−3×6=−8 e 4×(−2)+1×7=−1; total −9. No extremo dado, a soma de produtos é 2³¹ e KMDA já satura em 2³¹−1. Um acumulador largo não recupera a unidade perdida; usa os dois produtos completos de SMUL16 e soma-os com largura suficiente.

Confere a tua resposta:

*   Obtive parciais −8 e −1 e total −9.
*   Usei duas cargas e KMDA por par, com avanço de 4 bytes.
*   Expliquei que aumentar o acumulador não desfaz saturação de KMDA.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#produto-interno-de-meias-palavras)

O menor inteiro com sinal

Qual valor de 16 bits com sinal impede representar |x| no mesmo tipo?

Pista

O intervalo não é simétrico.

Solução

−32768, porque negação modular conserva 0x8000 em vez de produzir 32768 com sinal. Exclui-o do contrato ou alarga a representação.

*   **−32768.** O seu valor absoluto 32768 não cabe em 16 bits com sinal.
*   **−32767.** 32767 cabe e é representável.
*   **0.** O seu valor absoluto é 0.

Erros frequentes

Confundir overflow com um problema resolvido pela escolha MAX.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#valor-absoluto-e-ajuste)

Combinar produtos diretos e cruzados

H0 é real, H1 imaginária. Multiplica a=(2,3) por b=(4,−1), explicando os quatro produtos.

Pista

Faz dois diretos e dois cruzados.

Solução

Real 8−(−3)=11; imaginária −2+12=10. O resultado é 11+j 10. Empacotar novamente só é válido se as duas partes couberem na largura pretendida.

Confere a tua resposta:

*   Usei arbr−aibi para a parte real.
*   Usei arbi+aibr para a imaginária.
*   Obtive 11 e 10 sem trocar as vias.

Erros frequentes

Somar os diretos para a parte real ou subtrair os cruzados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#coordenadas-e-n%C3%BAmeros-complexos)

Não perder o último grupo incompleto

Aplica a rotina `contar_inferiores` ao vetor de bytes com sinal \[−128,−3,0,127,−4,−3,−2\], com limite −2 e base alinhada. Quantos grupos e bytes de resto há? Que contagem devolve?

Pista

A comparação é estrita, x<−2.

Solução

Um grupo de 4 contém dois inferiores: −128 e −3. O resto contém −4 e −3, mas não −2. Total 4. Um lw extra para o resto leria um oitavo byte fora do contrato, por isso o resto usa três lb.

Confere a tua resposta:

*   Separei 1 grupo de 4 e 3 bytes restantes.
*   Obtive 2 no grupo e 2 no resto.
*   Obtive 4 sem ler além dos 7 bytes.

Erros frequentes

Ignorar o resto, usar menor ou igual ou executar um load de palavra além do tamanho válido.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#traduzir-a-contagem-para-registos)

Espelhar dois pontos por palavra

Dois pontos de coordenadas de 8 bits estão em memória como \[1,2,3,4\]=\[x1,y1,x2,y2\], em endereços crescentes. Uma carga little endian dá 0x04030201. Calcula a palavra após SWAP8 e após SWAP16. Qual serve para trocar x e y de cada ponto?

Solução

SWAP8 dá bytes \[2,1,4,3\], palavra 0x03040102, e espelha os dois pontos. SWAP16 dá \[3,4,1,2\], palavra 0x02010403: troca os pontos de posição, conservando x e y dentro de cada um. A granularidade da permutação tem de coincidir com a largura das coordenadas.

Confere a tua resposta:

*   Separei \[x1,y1,x2,y2\] em B0 a B3.
*   Obtive \[2,1,4,3\] com SWAP8.
*   Mostrei que SWAP16 troca pontos, sem trocar as coordenadas de cada um.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/programar-simd/#coordenadas-e-n%C3%BAmeros-complexos)