Vetores SoA na SPU

8

Li muito sobre os benefícios da organização de dados em 'Structs of Arrays' (SoA), em vez do típico 'Array of Structs' (AoS), para obter melhor rendimento ao usar as instruções SIMD . Enquanto o 'porquê' faz total sentido para mim, não tenho certeza de quanto fazer isso ao trabalhar com coisas como vetores.

Os próprios vetores podem ser considerados como uma estrutura de uma matriz de dados (tamanho fixo), para que você possa converter uma matriz desses em uma estrutura de matrizes X, Y e Z. Com isso, você pode trabalhar em 4 vetores de uma vez, em oposição a um de cada vez.

Agora, pelo motivo específico de postar isso no GameDev:

Isso faz sentido para trabalhar com vetores na SPU? Mais especificamente, faz sentido DMA várias matrizes apenas para um único vetor? Ou seria melhor manter o DMA na matriz de vetores e desenrolá-los nos diferentes componentes para trabalhar?

Eu pude ver o benefício de cortar o desenrolamento (se você fez 'AoS'), mas parece que você pode ficar rapidamente sem canais de DMA se você seguir essa rota e estiver trabalhando com vários conjuntos de vetores ao mesmo tempo.

(Nota: ainda não tem experiência profissional com o Cell, mas já está brincando no OtherOS há algum tempo)

Chris Waters
fonte

Respostas:

5

Uma abordagem é usar uma abordagem AoSoA (leia-se: Matriz de estrutura de matriz), que é um híbrido de AoS e SoA. A idéia é armazenar N structs no valor de dados em um pedaço contíguo no formato SoA, depois os próximos N structs no valor SoA.

Seu formulário AoS para 16 vetores (rotulado 0,1,2 ... F), swizzled na granularidade de 4 estruturas é:

000111222333444555666777888999AAABBBCCCDDDEEEFFF
XYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZ

para SoA, isto é:

0123456789ABCDEF
XXXXXXXXXXXXXXXX

0123456789ABCDEF
AAAAAAAAAAAAAAAA

0123456789ABCDEF
ZZZZZZZZZZZZZZZZ

para AoSoA, isso se torna:

01230123012345674567456789AB89AB89ABCDEFCDEFCDEF
XXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZZ

A abordagem AoSoA tem os seguintes benefícios do AoS:

  • Somente uma única transferência de DMA é necessária para transferir um pedaço de estruturas para a memória local da SPU.
  • As estruturas ainda têm a chance de todos os dados serem ajustados em um cacheline.
  • A pré-busca de bloco ainda é muito fácil.

A abordagem AoSoA também possui os seguintes benefícios do formato SoA:

  • Você pode carregar dados da memória local da SPU diretamente nos registros vetoriais de 128 bits sem precisar mexer seus dados.
  • Você ainda pode operar em quatro estruturas ao mesmo tempo.
  • Você pode utilizar totalmente o SIMD'ness do seu processador de vetores se não houver ramificações básicas (ou seja, nenhuma faixa não utilizada na aritmética de seus vetores).

A abordagem AoSoA ainda apresenta algumas dessas desvantagens da forma SoA:

  • o gerenciamento de objetos deve ser feito com granularidade impressionante.
  • gravações de acesso aleatório de uma estrutura completa agora precisam tocar na memória dispersa.
  • (esses podem acabar não sendo problemas, dependendo de como você organiza / gerencia suas estruturas e a vida útil delas)

BTW, esses conceitos do AoSoA se aplicam muito bem ao SSE / AVX / LRBni, bem como às GPUs que podem ser comparadas a processadores SIMD muito amplos, por exemplo. Largura de 32/48/64, dependendo do fornecedor / arquitetura.

jpaver
fonte
Não vejo como isso oferece alguma vantagem sobre não compactá-los por componente, a menos que você esteja compactando dados não vetoriais que você realmente usa como flutuadores - embora eu veja que o seu AoS exclui W, o que não pareceria muito favorável ao acesso à memória, eu acho que nesse caso há uma vitória. Observe também que as SPUs não têm linhas de cache, exceto para se comunicar com a memória principal.
Kaj
2
1. Como tudo, sua milhagem pode variar dependendo dos dados / algoritmo / processador exato. Em casos com restrições de registro, evitar a necessidade de 4 registros temporários antes que você possa embaralhar todos os seus campos X no mesmo registro pode ser útil. Mas, novamente, YMMV. 2. Minha resposta foi mais geral, porque os conceitos se transferem bem dentro do campo da programação paralela de dados; linhas de cache considerações são mais pertinentes para GPU / SSE, mas eu senti que deveria mencioná-los todos iguais :)
jpaver
11
Justo, sou iluminado e aprenderei a criticar mais sutilmente! Obrigado por compartilhar sua visão: o)
Kaj
3

As SPUs são realmente um caso especial interessante quando se trata de vetorizar código. As instruções são divididas em famílias "aritmética" e "carga / armazenamento", e as duas famílias são executadas em tubulações separadas. A SPU pode emitir um de cada tipo por ciclo.

Obviamente, o código matemático está fortemente vinculado às instruções matemáticas - portanto, normalmente, os loops matemáticos no SPU terão muitos e muitos ciclos abertos no pipe de carregamento / armazenamento. Como as embaralhamentos ocorrem no tubo de carregamento / armazenamento, geralmente você tem instruções de carregamento / armazenamento livres suficientes para passar o formato xyzxyzxyzxyz para o formato xxxxyyyyzzzz sem nenhuma sobrecarga.

Essa técnica está em uso no Naughty Dog, pelo menos - consulte as apresentações de montagem da SPU ( parte 1 e parte 2 ) para obter detalhes.

Infelizmente, o compilador geralmente não é inteligente o suficiente para fazer isso automaticamente - se você optar por seguir esse caminho, precisará escrever o assembly você mesmo ou desenrolar seus loops usando intrínsecos e verificar o assembler para garantir que é o que deseja. Portanto, se você deseja escrever um código geral de plataforma cruzada que funcione bem no SPU, convém usar SoA ou AoSoA (como o jpaver sugere).

Charlie
fonte
Ah, afinal concordamos: o) Mexa na SPU, se necessário, tempo suficiente para fazê-la lá.
Kaj
1

Como em qualquer otimização, perfil! A legibilidade vem em primeiro lugar, e só deve ser sacrificada quando o perfil identifica um gargalo específico e você esgotou todas as opções para ajustar o algoritmo de alto nível (a maneira mais rápida de fazer o trabalho é não ter que fazer o trabalho!) seguindo qualquer otimização de baixo nível para confirmar que você realmente tornou as coisas mais rápidas do que o oposto, especialmente com dutos tão peculiares quanto os da célula.

Quais técnicas você usa então dependerão dos detalhes do gargalo. Em geral, ao trabalhar com tipos de vetores, um componente de vetor que você ignora em um resultado representa o trabalho desperdiçado. Alternar SoA / AoS não faz sentido, a menos que permita um trabalho mais útil preenchendo esses componentes não utilizados (por exemplo, um produto pontual na PPU do PS3 vs quatro produtos pontuais paralelamente na mesma quantidade de tempo). Para responder à sua pergunta, gastar tempo misturando componentes apenas para executar uma operação em um único vetor parece uma pessimização para mim!

O outro lado das SPUs é que a maior parte do custo de pequenas transferências de DMA está configurada; qualquer coisa menor que 128 bytes levará o mesmo número de ciclos para transferir e qualquer coisa menor que cerca de um kilobyte apenas alguns ciclos a mais. Portanto, não se preocupe em fornecer mais dados do que o necessário; reduzir o número de transferências sequenciais de DMA acionadas e executar o trabalho enquanto as transferências de DMA estão acontecendo - e, portanto, desdobrar prólogos e epílogos de loop para formar pipelines de software - é a chave para o bom desempenho da SPU e é mais fácil lidar com casos extremos, buscando dados extras / descartando resultados parcialmente computados do que pulando em bastidores para tentar organizar a quantidade exata de dados necessários para serem lidos e processados.

sombra da Lua
fonte
Se você descompactá-los, de acordo com a abordagem do AOSAO, pelo menos insira vários vetores de uma só vez. Além disso, você deseja extrair um lote e, durante o processamento, extrai o próximo lote. Ao enviar o primeiro lote, você processa o segundo e puxa o terceiro. Dessa forma, você esconde o máximo de latência possível.
Kaj
0

Não, isso não faria muito sentido em geral, pois a maioria dos opcodes vetoriais opera em um vetor como um todo e não em componentes separados. Assim, você já pode multiplicar um vetor em 1 instrução, enquanto que, ao dividir os componentes separados, você gasta 4 instruções nele. Portanto, como você basicamente realiza muitas operações em parte de uma estrutura, é melhor colocá-las em uma matriz, mas dificilmente você faz as coisas apenas em um componente de um vetor ou muito diferente em cada componente, quebrando-as fora não funcionaria.
Obviamente, se você encontrar uma situação em que precisa fazer algo apenas para os componentes (digamos) x dos vetores, pode funcionar, no entanto, a penalidade de refazer tudo de volta quando você precisar do vetor real não seria barata, então você poderia pergunto se você não deveria usar vetores para começar, mas apenas uma matriz de elementos flutuantes que permitem que os códigos de vetor opcionais façam seus cálculos específicos.

Kaj
fonte
2
Você está perdendo o objetivo de SoA para a matemática vetorial. Você raramente tem apenas um objeto no qual está trabalhando - na prática, está iterando uma matriz e fazendo a mesma coisa com muitos objetos. Considere fazer produtos com quatro pontos. Se você estiver armazenando vetores como AoS na forma xyz0, obter o ponto de dois vetores requer 5 instruções para multiplicar a reprodução aleatória-adição-reprodução aleatória - 5. Fazer produtos com 4 pontos requer 20 instruções. Por outro lado, se você tiver 8 vetores armazenados da forma SoA (xxxx, aaaa, zzzz, xxxx, aaaa, zzzz), poderá criar produtos de 4 pontos com apenas 3 instruções (mul, madd, madd) - isso é 6 vezes mais rápido.
Charlie
Ponto justo. No entanto, duas observações. Eu sempre manteria o W presente para não precisar de 20 instruções; em segundo lugar, a maior parte da sobrecarga restante pode estar oculta na latência de outras instruções - seu loop apertado sofreria severas paradas de tubulação, não? fazer 6 vezes é uma otimização teórica. Portanto, enquanto sim, você deseja agrupar suas operações - dificilmente precisará apenas fazer um lote rápido de produtos pontuais sem mais nada para fazer com os dados. O custo de desizzar / espalhar no lado da PPU seria muito sacrifício para mim.
Kaj
Gemido, eu estou corrigido - na SPU eu precisaria de 20 se feito ingenuamente (mas eu iria embaralhar no lugar). Foi uma das coisas em que acabei fazendo muitos swizzles para otimizar. O 360 possui um bom ponto intrínseco (mas não possui a incrível manipulação de bits).
Kaj
Sim, agora que penso nisso, se você está tentando fazer "produtos com quatro pontos", pode executar um pouco melhor do que 20 instruções, porque pode combinar algumas das adições posteriores. Mas ter seus vetores registrados como xxxx, yyyy, zzzz - seja você swizzled ou armazenado como SoA - se livra completamente desses shuffles. De qualquer forma, você está certo que o SoA torna o código lógico ramificado mais lento - mas eu diria que a solução em muitos casos como esse é reunir seus dados e refatorar a lógica ramificada em loops planos agradáveis.
Charlie
Acordado. Tenho certeza de que, se passar por cima do meu código SPU antigo (não é possível, empresa anterior), houve casos em que o mudei para o formato xxxxyyyyzzzz para otimização sem percebê-lo especificamente. Eu nunca o ofereci a partir do PPU nesse formato. Veja bem, OP, o que está contemplando separadamente x, y, z separadamente. Isso definitivamente não funcionaria para mim. Eu também (como fiz) preferiria swizzle localmente, pois nem tudo funciona melhor no formato xxxxyyyyzzzz. Tenho que escolher suas batalhas, eu acho. A otimização para SPU é uma explosão e você se sente muito inteligente quando obtém a solução mais precisa: o)
Kaj