Technische Samenvatting: GPIR: Praktische Private Information Retrieval met GPU's mogelijk maken

Probleemstelling

Private Information Retrieval (PIR) stelt clients in staat om records op te halen uit een door een server gehoste database zonder de specifieke opgehaalde record te onthullen. Hoewel roostergebaseerde homomorfische encryptie (HE) sterke privacygaranties biedt, wordt de implementatie van PIR op grote schaal gehinderd door intensieve serverzijde berekening en geheugentransport. Moderne protocollen, zoals OnionPIRv2, omvatten drie fasen: ExpandQuery (het uitbreiden van een query naar versleutelde indices), RowSel (versleutelde rijselectie) en ColTor (recursief kolomtoernooi).

Hoewel GPU's enorme parallelisme bieden dat geschikt is voor deze bewerkingen, ondervinden bestaande GPU-implementaties kritieke knelpunten wanneer batchverwerking voor meerdere clients wordt ingezet om een hoge doorvoer te bereiken. Het artikel identificeert twee primaire architecturale uitdagingen:

1. De Cache-capaciteitsmuur: Batchverwerking voor meerdere clients breidt de werksets van ExpandQuery en ColTor uit tot buiten de capaciteit van de L2-cache van de GPU. Dit zorgt ervoor dat tijdelijke pieken in de werkset (door operaties voor cijferontleding) persistente knelpunten worden, wat leidt tot excessief DRAM-verkeer en een instorting van de prestaties.
2. Conflicten in gegevenslay-out: De RowSel-fase reduceert tot grootschalige matrix-matrix vermenigvuldigingen (GEMM's). De standaard HE-gegevenslay-outs zijn echter geoptimaliseerd voor Number-Theoretic Transforms (NTT's) en zijn $p$-major (polynoom-major). Deze lay-out is inefficiënt voor de tiling-strategieën die nodig zijn voor hoogpresterende GEMM's, wat een structurele mismatch creëert die het GPU-gebruik beperkt, zelfs wanneer de rekenintensiteit hoog is.

Methodologie

De auteurs presenteren GPIR, een door GPU's versnelde PIR-systeem dat het ontwerp van kernels, de gegevenslay-out en de uitvoerscheduling heroverweegt om deze knelpunten aan te pakken.

1. Stage-bewust hybride uitvoeringsmodel

Voor de fasen ExpandQuery en ColTor schakelt GPIR dynamisch tussen twee kernelgranulariteiten, afhankelijk van de grootte van de werkset ten opzichte van de L2-cache:

• Operationele Kernels: Gebruikt wanneer de werkset binnen de L2-cache past. Deze kernels voeren primitieve bewerkingen (zoals NTT, cijferontleding) afzonderlijk uit, waarbij de bezetting wordt gemaximaliseerd door fijnmazig parallelisme (opdeling per limb en per coëfficiënt) te benutten.
• Stageniveau Kernels: Gebruikt wanneer de werkset de L2-capaciteit overschrijdt. Deze kernels fuseren alle bewerkingen binnen een enkele fase (bijv. NTT, ontleding en accumulatie) in één aanroep. Hierdoor blijven tijdelijke tussenresultaten in registers of gedeeld geheugen op de chip bewaard, wat de "cache-capaciteitsmuur" omzeilt en het DRAM-verkeer minimaliseert, zelfs ten koste van verminderd parallelisme.

2. Lay-outbewuste RowSel-optimalisaties

Om het conflict tussen door NTT-gedreven lay-outs en GEMM-eisen op te lossen, introduceert GPIR:

• Getransponeerde Lay-out Ontwerp: Het systeem transposeert gegevens expliciet om $k$-major of $m/n$-major lay-outs mogelijk te maken die geschikt zijn voor efficiënt GEMM-tiling. Dit maakt grotere tile-groottes en betere geheugencoalescing mogelijk, waardoor RowSel verschuift van een geheugengebonden naar een rekengebonden regime.
• Fijnmazige Pipelining: Om de overhead van datatranspositie te mitigeren, partitioneert GPIR de $p$-dimensie (polynoompunten) en RNS-priemgetallen. Door transpositie- en GEMM-kernels in afzonderlijke CUDA-streams te lanceren en CUDA Graphs te gebruiken, overlapt het systeem de latentie van transpositie met de berekening, waardoor serialisatieknelpunten worden voorkomen.

3. Schaalbare Multi-GPU Uitvoering

GPIR breidt uit naar multi-GPU-systemen om zowel de query-doorvoer als de databasecapaciteit te schalen:

• DB Sharding: De database wordt over GPU's verdeeld om de totale geheugencapaciteit te vergroten.
• All-Gathering Expanded Cts: Voor de ExpandQuery-fase verdeelt het systeem de werklast en verzamelt vervolgens de uitgebreide ciphertexts over de GPU's via een all-gather-operatie. Dit maakt gebruik van hoogbandbreedte interconnects (zoals NVLink) om communicatie-overhead te minimaliseren terwijl de doorvoer wordt geschaald.
• Responsaggregatie: Deeltresultaten van ColTor worden samengevoegd met verwaarloosbare communicatiekosten.

Belangrijkste Bijdragen

• Architecturale Analyse van Gebatchte PIR: Het artikel karakteriseert de "cache-capaciteitsmuur" in gebatchte PIR, en toont aan hoe batchverwerking knelpunten verschuift van geheugenbandbreedte naar DRAM-verkeer voor ExpandQuery en ColTor, terwijl het inefficiënties in de gegevenslay-out in RowSel blootlegt.
• Stage-bewust Hybride Uitvoering: Een dynamisch uitvoeringsmodel dat de kernelgranulariteit (operationeel versus stageniveau) selecteert op basis van de werksetgrootte, waardoor een effectief evenwicht wordt gevonden tussen bezetting en DRAM-verkeerreductie.
• Lay-outbewuste RowSel: Een getransponeerde lay-out-ontwerp met fijnmazige pipelining dat de structurele mismatch tussen NTT- en GEMM-gegevenstoegangspatronen oplost, wat de reken-doorvoer aanzienlijk verbetert.
• Multi-GPU Schaalstrategieën: Nieuwe coördinatiestrategieën voor PIR die de doorvoer en databasecapaciteit schalen met verwaarloosbare communicatie-overhead, door gebruik te maken van DB sharding en hoogbandbreedte interconnects.

Resultaten

Gedeeld op een NVIDIA RTX 5090 en H100 GPU's met databasegroottes variërend van 1 GB tot 4 GB:

• Doorvoer: GPIR bereikt tot 297,2× hogere doorvoer dan PIRonGPU, de state-of-the-art open-source GPU-implementatie.
• Snelheidswinst ten opzichte van Baseline: In vergelijking met een baseline-implementatie gebaseerd op PIRonGPU met batchverwerking voor meerdere clients, bereikt GPIR een 1,84–2,23× snelheidswinst in de end-to-end uitvoeringstijd.
• DRAM-reductie: De hybride uitvoeringsstrategie vermindert DRAM-transacties met tot 1,83× voor ExpandQuery en 1,52× voor ColTor in vergelijking met operationele kernels.
• Multi-GPU Schaling:
  • Doorvoerscaling: Op H100 met NVLink bereikt GPIR bijna lineaire schaling, met een 3,76× snelheidswinst met vier GPU's.
  • DB Schaling: Bij het schalen van de database van 4 GB naar 16 GB over vier GPU's behoudt GPIR de query-doorvoer of verbetert deze licht (tot 1,09×), wat aantoont dat capaciteitsschaling geen proportionele prestatiedegradatie met zich meebrengt.

Betekenis

Het artikel betoogt dat hoewel batchverwerking voor meerdere clients essentieel is voor PIR met hoge doorvoer, dit fundamenteel de prestatieknelpunten op GPU's herschikt. Een naïeve toepassing van bestaande GPU-kernels faalt om de resulterende "cache-capaciteitsmuur" en conflicten in gegevenslay-out aan te pakken. Door architectuurbewuste softwareontwerpen in te voeren – specifiek stage-bewuste hybride uitvoering en lay-outbewuste optimalisaties – toont GPIR aan dat roostergebaseerde single-server PIR praktisch kan worden gemaakt voor grootschalige, privacy-bewarende databaseservices op moderne acceleratorplatforms. Het werk benadrukt dat het realiseren van praktische PIR niet alleen ruwe rekenkracht vereist, maar ook zorgvuldig beheer van geheugenhierarchieën en databewegingspatronen die specifiek zijn voor de PIR-werkstroom.