Resumen Técnico: GPIR: Habilitando la Recuperación Privada de Información Práctica con GPUs

Declaración del Problema

La Recuperación Privada de Información (PIR, por sus siglas en inglés) permite a los clientes recuperar registros de una base de datos alojada en un servidor sin revelar el registro específico al que acceden. Aunque la criptografía homomórfica (HE) basada en retículos ofrece garantías de privacidad sólidas, el despliegue de PIR a gran escala se ve obstaculizado por la intensa computación en el lado del servidor y el tráfico de memoria. Los protocolos modernos, como OnionPIRv2, involucran tres fases: ExpandQuery (ampliar una consulta en índices cifrados), RowSel (selección de filas cifradas) y ColTor (torneo recursivo de columnas).

Aunque las GPUs ofrecen un paralelismo masivo adecuado para estas operaciones, las implementaciones existentes en GPU enfrentan cuellos de botella críticos cuando se emplea el agrupamiento de múltiples clientes (multi-client batching) para lograr un alto rendimiento. El artículo identifica dos desafíos arquitectónicos principales:

1. El Muro de la Capacidad de Caché: El agrupamiento de múltiples clientes expande los conjuntos de trabajo de ExpandQuery y ColTor más allá de la capacidad de la caché L2 de la GPU. Esto hace que los picos transitorios del conjunto de trabajo (debido a operaciones de descomposición de dígitos) se conviertan en cuellos de botella persistentes, forzando un tráfico excesivo de DRAM y colapsando el rendimiento.
2. Conflictos de Diseño de Datos: La fase RowSel se reduce a multiplicaciones de matrices a gran escala (GEMMs). Sin embargo, los diseños de datos HE estándar están optimizados para Transformadas Numéricas Teóricas (NTTs) y son $p$-mayor (mayor en polinomios). Este diseño es ineficiente para las estrategias de fragmentación (tiling) requeridas por GEMMs de alto rendimiento, creando una incompatibilidad estructural que limita la utilización de la GPU incluso cuando la intensidad aritmética es alta.

Metodología

Los autores presentan GPIR, un sistema de PIR acelerado por GPU que replantea el diseño de kernels, el diseño de datos y la programación de ejecución para abordar estos cuellos de botella.

1. Modelo de Ejecución Híbrido Consciente de la Etapa

Para las fases ExpandQuery y ColTor, GPIR cambia dinámicamente entre dos granularidades de kernels basándose en el tamaño del conjunto de trabajo en relación con la caché L2:

• Kernels a Nivel de Operación: Se utilizan cuando el conjunto de trabajo cabe dentro de la caché L2. Estos kernels ejecutan operaciones primitivas (por ejemplo, NTT, descomposición de dígitos) por separado, maximizando la ocupación explotando el paralelismo de grano fino (partición por limbos y por coeficientes).
• Kernels a Nivel de Etapa: Se utilizan cuando el conjunto de trabajo excede la capacidad de la L2. Estos kernels fusionan todas las operaciones dentro de una sola etapa (por ejemplo, NTT, descomposición y acumulación) en una sola invocación. Esto retiene los datos transitorios intermedios en registros on-chip o memoria compartida, evitando el "muro de la capacidad de caché" y minimizando el tráfico de DRAM, incluso a costa de una reducción del paralelismo.

2. Optimizaciones de RowSel Conscientes del Diseño

Para resolver el conflicto entre los diseños impulsados por NTT y los requisitos de GEMM, GPIR introduce:

• Diseño de Diseño Transpuesto: El sistema transpone explícitamente los datos para habilitar diseños $k$-mayor o $m/n$-mayor adecuados para una fragmentación (tiling) de GEMM eficiente. Esto permite tamaños de fragmento más grandes y una mejor coalescencia de memoria, desplazando RowSel de un régimen limitado por memoria a uno limitado por cómputo.
• Pipelining de Grano Fino: Para mitigar la sobrecarga de la transposición de datos, GPIR particiona la dimensión $p$ (puntos polinomiales) y los primos RNS. Al lanzar kernels de transposición y GEMM en flujos CUDA separados y utilizar CUDA Graphs, el sistema solapa la latencia de transposición con el cómputo, evitando cuellos de botella de serialización.

3. Ejecución Escalable en Múltiples GPUs

GPIR se extiende a sistemas de múltiples GPUs para escalar tanto el rendimiento de consultas como la capacidad de la base de datos:

• Fragmentación de la Base de Datos (DB Sharding): La base de datos se particiona entre GPUs para aumentar la capacidad de memoria agregada.
• Recolección Total de Cts Ampliados (All-Gathering Expanded Cts): Para la fase ExpandQuery, el sistema distribuye la carga de trabajo y luego realiza una recolección total (all-gather) de los textos cifrados ampliados entre las GPUs. Esto aprovecha interconexiones de alto ancho de banda (por ejemplo, NVLink) para minimizar la sobrecarga de comunicación mientras se escala el rendimiento.
• Agregación de Respuestas: Los resultados parciales de ColTor se fusionan con un costo de comunicación negligible.

Contribuciones Clave

• Análisis Arquitectónico de PIR Agrupado: El artículo caracteriza el "muro de la capacidad de caché" en PIR agrupado, demostrando cómo el agrupamiento desplaza los cuellos de botella del ancho de banda de memoria al tráfico de DRAM para ExpandQuery y ColTor, al tiempo que expone ineficiencias en el diseño de datos en RowSel.
• Ejecución Híbrida Consciente de la Etapa: Un modelo de ejecución dinámico que selecciona la granularidad del kernel (nivel de operación vs. nivel de etapa) basándose en el tamaño del conjunto de trabajo, equilibrando efectivamente la ocupación y la reducción del tráfico de DRAM.
• RowSel Consciente del Diseño: Un diseño de transposición con pipelining de grano fino que resuelve la incompatibilidad estructural entre los patrones de acceso a datos de NTT y GEMM, mejorando significativamente el rendimiento computacional.
• Estrategias de Escalado Multi-GPU: Estrategias de coordinación novedosas para PIR que escalan el rendimiento y la capacidad de la base de datos con una sobrecarga de comunicación negligible, utilizando fragmentación de la base de datos e interconexiones de alto ancho de banda.

Resultados

Evaluado en GPUs NVIDIA RTX 5090 y H100 con tamaños de base de datos que van desde 1 GB hasta 4 GB:

• Rendimiento: GPIR logra hasta 297.2× más rendimiento que PIRonGPU, la implementación de GPU de código abierto más avanzada.
• Aceleración sobre la Línea Base: En comparación con una implementación base basada en PIRonGPU con agrupamiento de múltiples clientes, GPIR logra una aceleración de 1.84–2.23× en el tiempo de ejecución de extremo a extremo.
• Reducción de DRAM: La estrategia de ejecución híbrida reduce las transacciones de DRAM hasta en 1.83× para ExpandQuery y 1.52× para ColTor en comparación con los kernels a nivel de operación.
• Escalado Multi-GPU:
  • Escalado de Rendimiento: En H100 con NVLink, GPIR logra un escalado casi lineal, alcanzando una aceleración de 3.76× con cuatro GPUs.
  • Escalado de DB: Al escalar la base de datos de 4 GB a 16 GB entre cuatro GPUs, GPIR mantiene o mejora ligeramente el rendimiento de consultas (hasta 1.09×), demostrando que el escalado de capacidad no incurre en una degradación de rendimiento proporcional.

Significado

El artículo argumenta que, aunque el agrupamiento de múltiples clientes es esencial para PIR de alto rendimiento, redefine fundamentalmente los cuellos de botella de rendimiento en las GPUs. La aplicación ingenua de kernels de GPU existentes no logra abordar el "muro de la capacidad de caché" resultante y los conflictos de diseño de datos. Al introducir diseños de software conscientes de la arquitectura, específicamente la ejecución híbrida consciente de la etapa y las optimizaciones conscientes del diseño, GPIR demuestra que la PIR de un solo servidor basada en retículos puede hacerse práctica para servicios de bases de datos a gran escala que preservan la privacidad en plataformas de aceleradores modernas. El trabajo destaca que lograr una PIR práctica requiere no solo potencia computacional bruta, sino una gestión cuidadosa de las jerarquías de memoria y los patrones de movimiento de datos específicos del flujo de trabajo de PIR.