Riepilogo Tecnico: GPIR: Abilitare il Recupero Privato di Informazioni Pratico con le GPU

Enunciato del Problema

Il Recupero Privato di Informazioni (PIR) consente ai client di recuperare record da un database ospitato su server senza rivelare il record specifico accessibile. Sebbene la crittografia omomorfica (HE) basata su reticoli offra garanzie di privacy robuste, il dispiegamento del PIR su larga scala è ostacolato da un'intensa computazione lato server e dal traffico di memoria. I protocolli moderni, come OnionPIRv2, coinvolgono tre fasi: ExpandQuery (espansione di una query in indici cifrati), RowSel (selezione di righe cifrate) e ColTor (torneo ricorsivo delle colonne).

Sebbene le GPU offrano un massiccio parallelismo adatto a queste operazioni, le implementazioni GPU esistenti affrontano colli di bottiglia critici quando viene impiegato il batching multi-client per ottenere un'elevata capacità di elaborazione. Il documento identifica due sfide architetturali primarie:

1. Il Muro della Capacità della Cache: Il batching multi-client espande i set di lavoro di ExpandQuery e ColTor oltre la capacità della cache L2 della GPU. Ciò fa sì che i picchi transitori dei set di lavoro (dovuti alle operazioni di decomposizione delle cifre) diventino colli di bottiglia persistenti, costringendo a un traffico DRAM eccessivo e collassando le prestazioni.
2. Conflitti di Disposizione dei Dati: La fase RowSel si riduce a grandi moltiplicazioni matrice-matrice (GEMM). Tuttavia, le disposizioni dei dati HE standard sono ottimizzate per le Trasformate Numerico-Teoriche (NTT) e sono $p$-major (polinomiali-major). Questa disposizione è inefficiente per le strategie di tassellazione richieste dai GEMM ad alte prestazioni, creando un disallineamento strutturale che limita l'utilizzo della GPU anche quando l'intensità aritmetica è elevata.

Metodologia

Gli autori presentano GPIR, un sistema PIR accelerato da GPU che ripensa la progettazione dei kernel, la disposizione dei dati e la pianificazione dell'esecuzione per affrontare questi colli di bottiglia.

1. Modello di Esecuzione Ibrido Consapevole della Fase

Per le fasi ExpandQuery e ColTor, GPIR passa dinamicamente tra due granularità di kernel in base alla dimensione del set di lavoro rispetto alla cache L2:

• Kernel a Livello di Operazione: Utilizzati quando il set di lavoro rientra nella cache L2. Questi kernel eseguono operazioni primitive (ad esempio, NTT, decomposizione delle cifre) separatamente, massimizzando l'occupazione sfruttando il parallelismo a grana fine (partizionamento per membro e per coefficiente).
• Kernel a Livello di Fase: Utilizzati quando il set di lavoro supera la capacità L2. Questi kernel fondono tutte le operazioni all'interno di una singola fase (ad esempio, NTT, decomposizione e accumulazione) in una singola invocazione. Ciò mantiene i dati transitori intermedi nei registri on-chip o nella memoria condivisa, evitando il "muro della capacità della cache" e minimizzando il traffico DRAM, anche a costo di una ridotta parallelizzazione.

2. Ottimizzazioni RowSel Consapevoli della Disposizione

Per risolvere il conflitto tra disposizioni guidate da NTT e i requisiti GEMM, GPIR introduce:

• Design a Disposizione Trasposta: Il sistema traspone esplicitamente i dati per abilitare disposizioni $k$-major o $m/n$-major adatte a una tassellazione GEMM efficiente. Ciò consente dimensioni di tassello più grandi e un migliore allineamento della memoria, spostando RowSel da un regime limitato dalla memoria a uno limitato dalla computazione.
• Pipelining a Grana Fine: Per mitigare l'overhead della trasposizione dei dati, GPIR partiziona la dimensione $p$ (punti polinomiali) e i primi RNS. Avviando kernel di trasposizione e GEMM in flussi CUDA separati e utilizzando CUDA Graphs, il sistema sovrappone la latenza di trasposizione alla computazione, prevenendo colli di bottiglia di serializzazione.

3. Esecuzione Scalabile Multi-GPU

GPIR si estende ai sistemi multi-GPU per scalare sia la capacità di elaborazione delle query che la capacità del database:

• Sharding del DB: Il database è partizionato tra le GPU per aumentare la capacità di memoria aggregata.
• All-Gathering dei Cts Espansi: Per la fase ExpandQuery, il sistema distribuisce il carico di lavoro e poi esegue un all-gather dei testi cifrati espansi tra le GPU. Ciò sfrutta interconnessioni ad alta larghezza di banda (ad esempio, NVLink) per minimizzare l'overhead di comunicazione mentre si scala la capacità di elaborazione.
• Aggregazione della Risposta: I risultati parziali di ColTor vengono uniti con un costo di comunicazione trascurabile.

Contributi Chiave

• Analisi Architetturale del PIR in Batch: Il documento caratterizza il "muro della capacità della cache" nel PIR in batch, dimostrando come lo spostamento dei colli di bottiglia dal PIR in batch si sposti dalla larghezza di banda della memoria al traffico DRAM per ExpandQuery e ColTor, esponendo al contempo inefficienze nella disposizione dei dati in RowSel.
• Esecuzione Ibrida Consapevole della Fase: Un modello di esecuzione dinamico che seleziona la granularità del kernel (livello di operazione vs. livello di fase) in base alla dimensione del set di lavoro, bilanciando efficacemente l'occupazione e la riduzione del traffico DRAM.
• RowSel Consapevole della Disposizione: Un design a disposizione trasposta con pipelining a grana fine che risolve il disallineamento strutturale tra i modelli di accesso ai dati NTT e GEMM, migliorando significativamente la capacità di elaborazione computazionale.
• Strategie di Scalabilità Multi-GPU: Strategie di coordinamento innovative per il PIR che scalano la capacità di elaborazione e la capacità del database con un overhead di comunicazione trascurabile, utilizzando lo sharding del DB e interconnessioni ad alta larghezza di banda.

Risultati

Valutati su GPU NVIDIA RTX 5090 e H100 con dimensioni del database che variano da 1 GB a 4 GB:

• Capacità di Elaborazione: GPIR raggiunge una capacità di elaborazione fino a 297,2× superiore rispetto a PIRonGPU, l'implementazione GPU open-source all'avanguardia.
• Accelerazione rispetto alla Linea di Base: Rispetto a un'implementazione di base basata su PIRonGPU con batching multi-client, GPIR raggiunge un'accelerazione di 1,84–2,23× nel tempo di esecuzione end-to-end.
• Riduzione DRAM: La strategia di esecuzione ibrida riduce le transazioni DRAM fino a 1,83× per ExpandQuery e 1,52× per ColTor rispetto ai kernel a livello di operazione.
• Scalabilità Multi-GPU:
  • Scalabilità della Capacità di Elaborazione: Su H100 con NVLink, GPIR raggiunge una scalabilità quasi lineare, raggiungendo un'accelerazione di 3,76× con quattro GPU.
  • Scalabilità del DB: Quando si scala il database da 4 GB a 16 GB su quattro GPU, GPIR mantiene o migliora leggermente la capacità di elaborazione delle query (fino a 1,09×), dimostrando che la scalabilità della capacità non comporta un degrado delle prestazioni proporzionale.

Significato

Il documento sostiene che, sebbene il batching multi-client sia essenziale per un PIR ad alta capacità di elaborazione, esso rimodella fondamentalmente i colli di bottiglia delle prestazioni sulle GPU. L'applicazione ingenua dei kernel GPU esistenti non riesce ad affrontare il conseguente "muro della capacità della cache" e i conflitti di disposizione dei dati. Introducendo design software consapevoli dell'architettura—specificamente l'esecuzione ibrida consapevole della fase e le ottimizzazioni consapevoli della disposizione—GPIR dimostra che il PIR a server singolo basato su reticoli può essere reso pratico per servizi di database su larga scala e rispettosi della privacy sulle moderne piattaforme di accelerazione. Il lavoro sottolinea che il raggiungimento di un PIR pratico richiede non solo potenza computazionale grezza, ma anche una gestione attenta delle gerarchie di memoria e dei modelli di movimento dei dati specifici al flusso di lavoro PIR.