기술 요약: GPIR: GPU 를 활용한 실용적 개인 정보 검색 (PIR) 구현

문제 정의

개인 정보 검색 (PIR) 은 클라이언트가 서버가 호스팅하는 데이터베이스에서 특정 레코드를 접근했는지 드러내지 않고 레코드를 검색할 수 있게 합니다. 격자 기반 동형 암호화 (HE) 는 강력한 프라이버시 보장을 제공하지만, PIR 의 대규모 배포는 서버 측의 과도한 계산 및 메모리 트래픽으로 인해 방해받고 있습니다. OnionPIRv2 와 같은 최신 프로토콜은 세 가지 단계를 포함합니다: ExpandQuery(쿼리를 암호화된 인덱스로 확장), RowSel(암호화된 행 선택), 그리고 ColTor(재귀적 열 토너먼트).

GPU 는 이러한 연산에 적합한 대규모 병렬성을 제공하지만, 기존 GPU 구현은 높은 처리량을 달성하기 위해 **다중 클라이언트 배치 (multi-client batching)**가 사용될 때 치명적인 병목 현상에 직면합니다. 이 논문은 두 가지 주요 아키텍처적 과제를 식별합니다:

1. 캐시 용량 한계 (The Cache-Capacity Wall): 다중 클라이언트 배치는 ExpandQuery 와 ColTor 의 작업 집합을 GPU 의 L2 캐시 용량 이상으로 확장합니다. 이로 인해 (숫자 분해 연산으로 인한) 일시적인 작업 집합의 급증이 지속적인 병목 현상으로 변모하여 과도한 DRAM 트래픽을 유발하고 성능을 붕괴시킵니다.
2. 데이터 배치 충돌: RowSel 단계는 대규모 행렬 - 행렬 곱셈 (GEMM) 으로 축소됩니다. 그러나 표준 HE 데이터 배치는 수론적 변환 (NTT) 에 최적화되어 있으며 $p$-주 (다항식 주) 방식입니다. 이 배치는 고성능 GEMM 에 필요한 틸링 전략에 비효율적이어서, 산술 강도가 높음에도 불구하고 GPU 활용도를 제한하는 구조적 불일치를 만듭니다.

방법론

저자들은 이러한 병목 현상을 해결하기 위해 커널 설계, 데이터 배치, 실행 스케줄링을 재고한 GPU 가속 PIR 시스템인 GPIR을 제시합니다.

1. 단계 인식 하이브리드 실행 모델

ExpandQuery 및 ColTor 단계에 대해 GPIR 은 L2 캐시 대비 작업 집합 크기에 따라 두 가지 커널 세분성 사이를 동적으로 전환합니다:

• 연산 수준 커널: 작업 집합이 L2 캐시 내에 들어갈 때 사용됩니다. 이러한 커널은 (지체별 및 계수별 분할과 같은) 세밀한 병렬성을 활용하여 최대 점유율을 달성하기 위해 (NTT, 숫자 분해와 같은) 원시 연산을 별도로 실행합니다.
• 단계 수준 커널: 작업 집합이 L2 용량을 초과할 때 사용됩니다. 이러한 커널은 단일 단계 내의 모든 연산 (예: NTT, 분해, 누적) 을 하나의 호출로 융합합니다. 이는 온칩 레지스터 또는 공유 메모리에 중간 일시 데이터를 유지하여 "캐시 용량 한계"를 피하고 DRAM 트래픽을 최소화하며, 병렬성 감소라는 대가를 치르더라도 이를 달성합니다.

2. 배치 인식 RowSel 최적화

NTT 기반 배치와 GEMM 요구 사항 간의 충돌을 해결하기 위해 GPIR 은 다음을 도입합니다:

• 전치 배치 설계 (Transposed-Layout Design): 시스템은 효율적인 GEMM 틸링에 적합한 $k$-주 또는 $m/n$-주 배치를 가능하게 하기 위해 데이터를 명시적으로 전치합니다. 이는 더 큰 틸 크기와 더 나은 메모리 병렬화를 가능하게 하여 RowSel 을 메모리 제한 상태에서 계산 제한 상태로 전환시킵니다.
• 세밀한 파이프라이닝: 데이터 전치의 오버헤드를 완화하기 위해 GPIR 은 $p$-차원 (다항식 점) 과 RNS 소수를 분할합니다. 전치 및 GEMM 커널을 별도의 CUDA 스트림에서 실행하고 CUDA Graph 를 활용함으로써, 시스템은 전치 지연을 계산과 중첩하여 직렬화 병목 현상을 방지합니다.

3. 확장 가능한 멀티 GPU 실행

GPIR 은 쿼리 처리량과 데이터베이스 용량 모두를 확장하기 위해 멀티 GPU 시스템으로 확장됩니다:

• DB 샤딩 (DB Sharding): 데이터베이스를 GPU 간에 분할하여 총합 메모리 용량을 증가시킵니다.
• 확장된 암호문 전체 수집 (All-Gathering Expanded Cts): ExpandQuery 단계에서 시스템은 작업 부하를 분산한 후 확장된 암호문을 GPU 간에 전체 수집 (all-gather) 합니다. 이는 NVLink 와 같은 대역폭이 높은 인터커넥트를 활용하여 처리량을 확장하면서도 통신 오버헤드를 최소화합니다.
• 응답 집계: ColTor 의 부분 결과는 무시할 수 있는 통신 비용으로 병합됩니다.

주요 기여

• 배치된 PIR 의 아키텍처 분석: 이 논문은 배치된 PIR 에서의 "캐시 용량 한계"를 특징짓고, 배치가 ExpandQuery 와 ColTor 에 대한 병목 현상을 메모리 대역폭에서 DRAM 트래픽으로 이동시키면서 RowSel 에서 데이터 배치 비효율성을 노출시키는 방식을 보여줍니다.
• 단계 인식 하이브리드 실행: 작업 집합 크기에 따라 커널 세분성 (연산 수준 대 단계 수준) 을 선택하는 동적 실행 모델로, 점유율과 DRAM 트래픽 감소를 효과적으로 균형 잡습니다.
• 배치 인식 RowSel: NTT 와 GEMM 데이터 접근 패턴 간의 구조적 불일치를 해결하고 계산 처리량을 크게 향상시키는 세밀한 파이프라이닝을 갖춘 전치 배치 설계입니다.
• 멀티 GPU 확장 전략: DB 샤딩과 대역폭이 높은 인터커넥트를 활용하여 통신 오버헤드가 거의 없이 처리량과 데이터베이스 용량을 확장하는 PIR 을 위한 새로운 조정 전략입니다.

결과

1GB 에서 4GB 범위의 데이터베이스 크기를 가진 NVIDIA RTX 5090 및 H100 GPU 에서 평가됨:

• 처리량: GPIR 은 최신 오픈 소스 GPU 구현체인 PIRonGPU 보다 최대 297.2 배 높은 처리량을 달성합니다.
• 기반 대비 속도 향상: 다중 클라이언트 배치를 기반으로 한 PIRonGPU 기반의 기준 구현과 비교할 때, GPIR 은 엔드 - 투 - 엔드 실행 시간에서 1.84~2.23 배의 속도 향상을 달성합니다.
• DRAM 감소: 하이브리드 실행 전략은 연산 수준 커널에 비해 ExpandQuery 의 경우 DRAM 트랜잭션을 최대 1.83 배, ColTor 의 경우 1.52 배 감소시킵니다.
• 멀티 GPU 확장:
  • 처리량 확장: NVLink 가 탑재된 H100 에서 GPIR 은 거의 선형적인 확장을 달성하여 4 개 GPU 로 3.76 배의 속도 향상을 기록합니다.
  • DB 확장: 4 개 GPU 에 걸쳐 데이터베이스를 4GB 에서 16GB 로 확장할 때, GPIR 은 쿼리 처리량을 유지하거나 약간 향상시킵니다 (최대 1.09 배). 이는 용량 확장이 비례적인 성능 저하를 초래하지 않음을 보여줍니다.

의의

이 논문은 다중 클라이언트 배치가 고성능 PIR 에 필수적이지만, GPU 의 성능 병목 현상을 근본적으로 재편성한다고 주장합니다. 기존 GPU 커널의 단순한 적용은 결과적으로 발생하는 "캐시 용량 한계"와 데이터 배치 충돌을 해결하지 못합니다. 단계 인식 하이브리드 실행 및 배치 인식 최적화와 같은 아키텍처 인식 소프트웨어 설계를 도입함으로써, GPIR 은 격자 기반 단일 서버 PIR 이 현대 가속기 플랫폼에서 대규모 프라이버시 보호 데이터베이스 서비스에 실용적으로 만들 수 있음을 보여줍니다. 이 작업은 실용적인 PIR 을 달성하기 위해서는 raw 계산 능력뿐만 아니라 PIR 워크플로우에 특화된 메모리 계층 구조와 데이터 이동 패턴의 신중한 관리가 필요함을 강조합니다.