Classificação rápida vetorizada com desempenho de transferência Blogue de código aberto do Google

By | Junho 4, 2022

Hoje, compartilhamos código-fonte aberto que pode classificar matrizes de números cerca de dez vezes mais rápido que C++ std :: classificar, e supera algoritmos específicos de arquitetura de última geração, sendo portátil para todas as arquiteturas modernas de CPU. Abaixo, discutiremos como conseguimos isso.

Primeiro, alguns antecedentes. Tem havido uma tendência recente de bancos de dados de colunas que armazenam todos os valores de uma determinada coluna em sucessão, em vez de armazenar todos os campos de registro ou “linhas” antes dos campos do próximo registro. Isso pode ser mais rápido para filtrar ou classificar, que são os principais blocos de construção para consultas SQL; portanto, nos concentramos nesse layout de dados.

Dado que a classificação foi extensivamente estudada, como podemos encontrar uma aceleração de 10x? A resposta está nas instruções SIMD/vetor. Eles executam operações em vários elementos independentes em uma única instrução — por exemplo, executando 16 float32 de uma só vez ao usar o conjunto de instruções AVX-512 ou quatro no Arm NEON:

Supercomputador Summit

Se você já conhece o SIMD, já deve ter ouvido falar que ele é usado em supercomputadores, álgebra linear para aplicativos de aprendizado de máquina, processamento de vídeo ou codecs de imagem como JPEG XL. Mas se as operações SIMD incluem apenas elementos independentes, como podemos classificá-los, o que envolve reorganizar elementos adjacentes do array?

Imagine que temos alguma maneira especial de ordenar, por exemplo, arrays de 256 elementos. Então Algoritmo de ordenação rápida ordenar uma string maior consiste em particionar em dois subconjuntos: aqueles menores que o valor “swivel” (idealmente a mediana) e todos os outros; em seguida, repita até que a substring não tenha mais de 256 elementos e use nosso método especial para classificá-los. O particionamento ocupa a maior parte do tempo da CPU, portanto, se pudermos acelerá-lo com o SIMD, teremos uma classificação rápida.

Felizmente, conjuntos de instruções modernos (Arm ALL, RISC-V V, x86 AVX-512) incluem uma instrução especial adequada para particionamento. Devido à entrada separada de valores sim/não (se o elemento é menor que o pivô), esta instrução de “compressão” armazena na memória consecutiva apenas os elementos cuja entrada correspondente é “sim”. Podemos então negar logicamente os valores sim/não e reaplicar a instrução para gravar os elementos em outra partição. Essa estratégia foi usada em Quicksort específico para o AVX-512. Mas e quanto a outros conjuntos de instruções, como o AVX2, que não possuem armazenamento de compactação? Trabalho prévio mostrou como imitar esta instrução usando instruções permut.

Desenvolvemos essas técnicas para obter o primeiro Quicksort vetorizado que é portátil para seis conjuntos de instruções em três arquiteturas e, na verdade, supera as variedades específicas de arquiteturas anteriores. Nossos benefícios de implementação Rodovias funções SIMD portáteis, para que não precisemos reimplementar cerca de 3.000 linhas de C++ para cada plataforma. A rodovia usa armazenamento de compactação quando disponível, caso contrário, instruções de permutação equivalentes. Ao contrário do anterior Estado da arte—O que também era específico para inteiros de 32 bits — oferecemos suporte a toda a gama de entradas de 16 a 128 bits.

Apesar de nossa implementação portátil, também alcançamos velocidades recordes no AVX2, AVX-512 (Intel Skylake) e Arm NEON (Apple M1). Para um milhão de números de 32/64/128 bits, nosso código executado no Apple M1 pode produzir saída classificada a 499/471/466 MB/s. No Skylake de 3 GHz com AVX-512, as velocidades são 1123/1119/1120 MB/s. Curiosamente, o AVX-512 é 1,4-1,6 vezes mais rápido que o AVX2 – vale a pena acelerar sem esforço (Highway verifica quais instruções estão disponíveis na CPU e usa as melhores disponíveis). Ao trabalhar no AVX2, medimos 798 MB / s, enquanto a técnica anterior otimizada para AVX2 gerencia apenas 699 MB / s. Para comparação, a biblioteca padrão atinge 58/128/117 MB/s na mesma CPU, então conseguimos 9-19x aceleração dependendo do tipo de números.

Anteriormente, a classificação era considerada cara. Estamos interessados ​​em quais novos aplicativos e recursos serão desbloqueados com a capacidade de classificar a 1 GB / s em um núcleo de CPU. Apache2 licenciado Código fonte está disponível no Github (gratuito abra um problema se você tiver dúvidas ou comentários) e o nosso papel oferece uma explicação detalhada e avaliação da implementação (incluindo um caso especial para 256 elementos).

Por Jan Wassenberg – Pesquisa sobre a arquitetura do cérebro do computador

Deixe uma resposta

O seu endereço de email não será publicado.