Resumo Técnico: GPIR: Habilitando Recuperação de Informação Privada Prática com GPUs

Declaração do Problema

A Recuperação de Informação Privada (PIR) permite que clientes recuperem registros de um banco de dados hospedado em um servidor sem revelar o registro específico acessado. Embora a criptografia homomórfica baseada em retículos (HE) forneça garantias robustas de privacidade, a implantação de PIR em escala é impedida por intensa computação no lado do servidor e tráfego de memória. Protocolos modernos, como o OnionPIRv2, envolvem três fases: ExpandQuery (expansão de uma consulta em índices criptografados), RowSel (seleção de linha criptografada) e ColTor (torneio recursivo de colunas).

Embora as GPUs ofereçam paralelismo massivo adequado para essas operações, as implementações existentes de GPU enfrentam gargalos críticos quando o agrupamento de múltiplos clientes (multi-client batching) é empregado para alcançar alta vazão. O artigo identifica dois desafios arquitetônicos primários:

1. O Muro de Capacidade de Cache: O agrupamento de múltiplos clientes expande os conjuntos de trabalho de ExpandQuery e ColTor além da capacidade do cache L2 da GPU. Isso faz com que picos transitórios de conjunto de trabalho (devido a operações de decomposição de dígitos) se tornem gargalos persistentes, forçando tráfego excessivo de DRAM e colapsando o desempenho.
2. Conflitos de Layout de Dados: A fase RowSel reduz-se a multiplicações de matriz-matriz em grande escala (GEMMs). No entanto, os layouts padrão de HE são otimizados para Transformadas Teóricas de Números (NTTs) e são $p$-major (majoritários em polinômios). Esse layout é ineficiente para as estratégias de telha (tiling) requeridas por GEMMs de alto desempenho, criando uma incompatibilidade estrutural que limita a utilização da GPU mesmo quando a intensidade aritmética é alta.

Metodologia

Os autores apresentam o GPIR, um sistema de PIR acelerado por GPU que repensa o design de kernels, o layout de dados e o agendamento de execução para abordar esses gargalos.

1. Modelo de Execução Híbrido Consciente de Estágio

Para as fases ExpandQuery e ColTor, o GPIR alterna dinamicamente entre duas granularidades de kernel com base no tamanho do conjunto de trabalho em relação ao cache L2:

• Kernels de Nível de Operação: Usados quando o conjunto de trabalho cabe dentro do cache L2. Esses kernels executam operações primitivas (por exemplo, NTT, decomposição de dígitos) separadamente, maximizando a ocupação explorando paralelismo de granularidade fina (particionamento por membro e por coeficiente).
• Kernels de Nível de Estágio: Usados quando o conjunto de trabalho excede a capacidade do L2. Esses kernels fundem todas as operações dentro de um único estágio (por exemplo, NTT, decomposição e acumulação) em uma única invocação. Isso retém dados transitórios intermediários em registradores on-chip ou memória compartilhada, evitando o "muro de capacidade de cache" e minimizando o tráfego de DRAM, mesmo ao custo de paralelismo reduzido.

2. Otimizações de RowSel Conscientes de Layout

Para resolver o conflito entre layouts orientados a NTT e requisitos de GEMM, o GPIR introduz:

• Design de Layout Transposto: O sistema transpõe explicitamente os dados para habilitar layouts $k$-major ou $m/n$-major adequados para telhamento (tiling) eficiente de GEMM. Isso permite tamanhos de telha maiores e melhor coalescência de memória, deslocando o RowSel de um regime limitado por memória para um regime limitado por computação.
• Pipelining de Granularidade Fina: Para mitigar a sobrecarga da transposição de dados, o GPIR particiona a dimensão $p$ (pontos polinomiais) e os primos RNS. Ao lançar kernels de transposição e GEMM em streams CUDA separados e utilizar CUDA Graphs, o sistema sobrepõe a latência de transposição com a computação, evitando gargalos de serialização.

3. Execução Escalável Multi-GPU

O GPIR estende-se a sistemas multi-GPU para escalar tanto a vazão de consultas quanto a capacidade do banco de dados:

• Fragmentação (Sharding) de DB: O banco de dados é particionado entre GPUs para aumentar a capacidade agregada de memória.
• Coleta Total de Cts Expandidos: Para a fase ExpandQuery, o sistema distribui a carga de trabalho e depois realiza uma coleta total (all-gather) dos textos cifrados expandidos entre as GPUs. Isso aproveita interconexões de alta largura de banda (por exemplo, NVLink) para minimizar a sobrecarga de comunicação enquanto escala a vazão.
• Agregação de Respostas: Resultados parciais do ColTor são mesclados com custo de comunicação negligenciável.

Contribuições Principais

• Análise Arquitetural de PIR Agrupada: O artigo caracteriza o "muro de capacidade de cache" na PIR agrupada, demonstrando como o agrupamento desloca os gargalos de largura de banda de memória para tráfego de DRAM para ExpandQuery e ColTor, ao mesmo tempo que expõe ineficiências de layout de dados no RowSel.
• Execução Híbrida Consciente de Estágio: Um modelo de execução dinâmico que seleciona a granularidade do kernel (nível de operação vs. nível de estágio) com base no tamanho do conjunto de trabalho, equilibrando efetivamente a ocupação e a redução de tráfego de DRAM.
• RowSel Consciente de Layout: Um design de layout transposto com pipelining de granularidade fina que resolve a incompatibilidade estrutural entre os padrões de acesso a dados de NTT e GEMM, melhorando significativamente a vazão computacional.
• Estratégias de Escalonamento Multi-GPU: Estratégias de coordenação inovadoras para PIR que escalonam a vazão e a capacidade do banco de dados com sobrecarga de comunicação negligenciável, utilizando fragmentação de DB e interconexões de alta largura de banda.

Resultados

Avaliado em GPUs NVIDIA RTX 5090 e H100 com tamanhos de banco de dados variando de 1 GB a 4 GB:

• Vazão: O GPIR alcança até 297,2× mais vazão do que o PIRonGPU, a implementação de GPU de código aberto mais avançada.
• Aceleração sobre a Linha de Base: Comparado a uma implementação de linha de base baseada no PIRonGPU com agrupamento de múltiplos clientes, o GPIR alcança uma aceleração de 1,84–2,23× no tempo de execução de ponta a ponta.
• Redução de DRAM: A estratégia de execução híbrida reduz as transações de DRAM em até 1,83× para ExpandQuery e 1,52× para ColTor em comparação com kernels de nível de operação.
• Escalonamento Multi-GPU:
  • Escalonamento de Vazão: No H100 com NVLink, o GPIR alcança escalonamento quase linear, atingindo 3,76× de aceleração com quatro GPUs.
  • Escalonamento de DB: Ao escalar o banco de dados de 4 GB para 16 GB entre quatro GPUs, o GPIR mantém ou melhora ligeiramente a vazão de consultas (até 1,09×), demonstrando que o escalonamento de capacidade não incorre em degradação de desempenho proporcional.

Significado

O artigo argumenta que, embora o agrupamento de múltiplos clientes seja essencial para PIR de alta vazão, ele remodela fundamentalmente os gargalos de desempenho nas GPUs. A aplicação ingênua de kernels de GPU existentes falha em abordar o resultante "muro de capacidade de cache" e conflitos de layout de dados. Ao introduzir designs de software conscientes da arquitetura — especificamente execução híbrida consciente de estágio e otimizações conscientes de layout —, o GPIR demonstra que a PIR de servidor único baseada em retículos pode ser tornada prática para serviços de banco de dados de grande escala e preservação de privacidade em plataformas aceleradoras modernas. O trabalho destaca que alcançar PIR prática requer não apenas poder computacional bruto, mas também gerenciamento cuidadoso de hierarquias de memória e padrões de movimento de dados específicos ao fluxo de trabalho de PIR.