Résumé technique : GPIR : Rendre la récupération privée d'informations pratique avec les GPU

Énoncé du problème

La récupération privée d'informations (PIR) permet aux clients de récupérer des enregistrements d'une base de données hébergée par un serveur sans révéler l'enregistrement spécifique consulté. Bien que le chiffrement homomorphe (HE) basé sur les réseaux offre de solides garanties de confidentialité, le déploiement de la PIR à grande échelle est entravé par des calculs côté serveur intenses et un trafic mémoire élevé. Les protocoles modernes, tels qu'OnionPIRv2, comportent trois phases : ExpandQuery (expansion d'une requête en indices chiffrés), RowSel (sélection de lignes chiffrées) et ColTor (tournoi récursif de colonnes).

Bien que les GPU offrent un parallélisme massif adapté à ces opérations, les implémentations GPU existantes rencontrent des goulots d'étranglement critiques lorsque le regroupement de plusieurs clients (multi-client batching) est utilisé pour atteindre un débit élevé. L'article identifie deux défis architecturaux principaux :

1. Le mur de la capacité du cache : Le regroupement de plusieurs clients étend les ensembles de travail de ExpandQuery et ColTor au-delà de la capacité du cache L2 du GPU. Cela transforme les pics transitoires d'ensembles de travail (dus aux opérations de décomposition de chiffres) en goulots d'étranglement persistants, forçant un trafic DRAM excessif et effondrant les performances.
2. Conflits de disposition des données : La phase RowSel se réduit à des multiplications matrice-matrice à grande échelle (GEMM). Cependant, les dispositions de données HE standard sont optimisées pour les Transformées Numériques Théoriques (NTT) et sont de type $p$-major (majorité polynomiale). Cette disposition est inefficace pour les stratégies de tuilage requises par les GEMM haute performance, créant un décalage structurel qui limite l'utilisation du GPU même lorsque l'intensité arithmétique est élevée.

Méthodologie

Les auteurs présentent GPIR, un système PIR accéléré par GPU qui repense la conception des noyaux, la disposition des données et la planification de l'exécution pour résoudre ces goulots d'étranglement.

1. Modèle d'exécution hybride conscient des étapes

Pour les phases ExpandQuery et ColTor, GPIR commute dynamiquement entre deux granularités de noyaux en fonction de la taille de l'ensemble de travail par rapport au cache L2 :

• Noyaux au niveau de l'opération : Utilisés lorsque l'ensemble de travail tient dans le cache L2. Ces noyaux exécutent séparément des opérations primitives (par exemple, NTT, décomposition de chiffres), maximisant l'occupation en exploitant un parallélisme fin (partitionnement par membre et par coefficient).
• Noyaux au niveau de l'étape : Utilisés lorsque l'ensemble de travail dépasse la capacité du L2. Ces noyaux fusionnent toutes les opérations au sein d'une seule étape (par exemple, NTT, décomposition et accumulation) en une seule invocation. Cela conserve les données transitoires intermédiaires dans les registres on-chip ou la mémoire partagée, évitant le « mur de la capacité du cache » et minimisant le trafic DRAM, même au prix d'une réduction du parallélisme.

2. Optimisations de RowSel conscientes de la disposition

Pour résoudre le conflit entre les dispositions pilotées par les NTT et les exigences des GEMM, GPIR introduit :

• Conception de disposition transposée : Le système transpose explicitement les données pour permettre des dispositions de type $k$-major ou $m/n$-major, adaptées au tuilage GEMM efficace. Cela permet des tailles de tuiles plus grandes et un meilleur regroupement des accès mémoire, déplaçant RowSel d'un régime limité par la mémoire à un régime limité par le calcul.
• Pipelining fin : Pour atténuer la surcharge de la transposition des données, GPIR partitionne la dimension $p$ (points polynomiaux) et les nombres premiers RNS. En lançant des noyaux de transposition et de GEMM dans des flux CUDA séparés et en utilisant des Graphes CUDA, le système chevauche la latence de transposition avec le calcul, empêchant les goulots d'étranglement de sérialisation.

3. Exécution évolutive multi-GPU

GPIR s'étend aux systèmes multi-GPU pour augmenter à la fois le débit des requêtes et la capacité de la base de données :

• Fragmentation de la base de données (DB Sharding) : La base de données est partitionnée sur les GPU pour augmenter la capacité mémoire agrégée.
• Collecte globale des Cts étendus : Pour la phase ExpandQuery, le système distribue la charge de travail puis effectue une collecte globale (all-gather) des textes chiffrés étendus sur les GPU. Cela exploite les interconnexions à haut débit (par exemple, NVLink) pour minimiser les surcoûts de communication tout en augmentant le débit.
• Agrégation des réponses : Les résultats partiels de ColTor sont fusionnés avec un coût de communication négligeable.

Contributions clés

• Analyse architecturale de la PIR groupée : L'article caractérise le « mur de la capacité du cache » dans la PIR groupée, démontrant comment le regroupement déplace les goulots d'étranglement de la bande passante mémoire vers le trafic DRAM pour ExpandQuery et ColTor, tout en exposant les inefficacités de disposition des données dans RowSel.
• Exécution hybride consciente des étapes : Un modèle d'exécution dynamique qui sélectionne la granularité du noyau (niveau opération vs niveau étape) en fonction de la taille de l'ensemble de travail, équilibrant efficacement l'occupation et la réduction du trafic DRAM.
• RowSel conscient de la disposition : Une conception de disposition transposée avec un pipelining fin qui résout le décalage structurel entre les motifs d'accès aux données NTT et GEMM, améliorant considérablement le débit de calcul.
• Stratégies de mise à l'échelle multi-GPU : Des stratégies de coordination novatrices pour la PIR qui augmentent le débit et la capacité de la base de données avec un surcoût de communication négligeable, en utilisant la fragmentation de la base de données et les interconnexions à haut débit.

Résultats

Évalué sur des GPU NVIDIA RTX 5090 et H100 avec des tailles de base de données allant de 1 Go à 4 Go :

• Débit : GPIR atteint un débit jusqu'à 297,2 fois supérieur à celui de PIRonGPU, l'implémentation GPU open-source la plus avancée.
• Accélération par rapport à la référence : Par rapport à une implémentation de référence basée sur PIRonGPU avec regroupement de plusieurs clients, GPIR réalise une accélération de 1,84 à 2,23 fois dans le temps d'exécution de bout en bout.
• Réduction du trafic DRAM : La stratégie d'exécution hybride réduit les transactions DRAM d'un facteur allant jusqu'à 1,83 pour ExpandQuery et 1,52 pour ColTor par rapport aux noyaux au niveau de l'opération.
• Mise à l'échelle multi-GPU :
  • Mise à l'échelle du débit : Sur H100 avec NVLink, GPIR atteint une mise à l'échelle quasi linéaire, atteignant une accélération de 3,76 fois avec quatre GPU.
  • Mise à l'échelle de la base de données : Lors de l'extension de la base de données de 4 Go à 16 Go sur quatre GPU, GPIR maintient ou améliore légèrement le débit des requêtes (jusqu'à 1,09 fois), démontrant que la mise à l'échelle de la capacité n'entraîne pas de dégradation proportionnelle des performances.

Importance

L'article soutient que si le regroupement de plusieurs clients est essentiel pour une PIR à haut débit, il remodèle fondamentalement les goulots d'étranglement de performance sur les GPU. L'application naïve des noyaux GPU existants échoue à résoudre le « mur de la capacité du cache » et les conflits de disposition des données qui en résultent. En introduisant des conceptions logicielles conscientes de l'architecture — spécifiquement l'exécution hybride consciente des étapes et les optimisations conscientes de la disposition — GPIR démontre que la PIR à serveur unique basée sur les réseaux peut être rendue pratique pour des services de base de données à grande échelle respectant la vie privée sur les plateformes d'accélérateurs modernes. Ce travail met en évidence que la réalisation d'une PIR pratique ne nécessite pas seulement une puissance de calcul brute, mais aussi une gestion minutieuse des hiérarchies mémoire et des motifs de déplacement de données spécifiques au flux de travail PIR.