Tipo de bytes rápidos no registro?
https://stackoverflow.com/questions/1580686
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dado um registro de 4 bytes (ou 16 para SIMD), deve haver uma maneira eficiente de classificar os bytes no registro com algumas instruções.
Desde já, obrigado.
Solução
Procure um eficiente Rede de classificação para n = o número de bytes com os quais você se preocupa (4 ou 16). Converta isso em uma sequência de instruções de comparação e troca. (Para n = 16, isso será mais do que 'alguns', no entanto.)
Outras dicas
Encontrei! Está no artigo de 2007 "Usando registros e instruções SIMD para permitir o paralelismo no nível de instrução em algoritmos de classificação" de Furtak, Amaral e Niewiomski. Seção 4.
Ele usa 4 registros SSE, possui 12 etapas e executa em 19 instruções, incluindo carga e loja.
O mesmo artigo tem um excelente trabalho para criar dinamicamente redes de classificação com o SIMD.
Para acelerar a classificação de strings, acabei empacotando 7 bytes por duplo e classificando (classificando) uma matriz de 16 duplos no SSE2, usando classificação bitônica para criar duas execuções de 8 e uma mesclagem binária para mesclar as duas execuções.Você pode ver a primeira parte aqui http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) e aqui http://mischasan.wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/ (C) e a etapa de mesclagem bitônica (se você quiser usar o SSE até o fim) aqui: http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/ .Substituí a classificação por inserção na parte inferior do qsort por essa classificação, e é cerca de 5 vezes mais rápido que o qsort direto.HTH
Eu não tinha visto o jornal da UofA;a lógica bitônica é da programação GPGPU da velha escola (CTM).
Desculpe pelas strings de link incorporadas;Não sei como adicionar links clicáveis no stackoverflow de comentários.
Todos os algoritmos de classificação exigem valores de "troca" de um lugar para outro. Como você está falando sobre um registro da CPU literal, isso significa que qualquer tipo precisaria de outro registro para usar como um local temporário para manter os bytes que estão sendo trocados.
Eu nunca vi um chip com um método interno para classificar bytes dentro de um registro. Não estou dizendo que não foi feito, mas não consigo pensar em muitos usos para tal instrução.
