RadiK: Seleção Top-K Radix Paralela e Otimizada com GPU

A seleção top-k, que identifica os maiores ou menores k elementos de um conjunto de dados, é uma operação fundamental em domínios intensivos em dados, como bancos de dados e aprendizado profundo, sendo sua escalabilidade e eficiência críticas para esses sistemas de alto desempenho. No entanto, estudos anteriores sobre sua implementação eficiente em GPU são principalmente baseados em mesclagem e dependem fortemente da rápida, mas limitada em tamanho, memória on-chip, limitando assim a escalabilidade com um limite superior restrito em k. Este trabalho introduz uma seleção top-k radix paralela e otimizada com GPU que suporta valores de k significativamente maiores do que os métodos existentes, sem comprometer a eficiência, independentemente do comprimento da entrada e do tamanho do lote. Nosso método incorpora uma nova estrutura de otimização adaptada para alta largura de banda de memória e utilização de recursos, alcançando até 2,5x de aceleração em comparação com a arte anterior para consultas não em lote e até 4,8x de aceleração para consultas em lote. Além disso, propomos uma técnica de escalonamento adaptativo que fortalece a robustez, proporcionando ainda até 2,7x de aceleração em distribuições de entrada altamente adversariais.