A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture

이 논문은 호스트-디바이스 통신 지연을 제거하고 비동기 잠금 해제 작업 도용 풀을 도입하여 골드바흐의 추측을 검증하는 완전 GPU 거주 아키텍처를 제안함으로써, 단일 RTX 5090 에서 $10^{12}$까지의 검증을 36.5 초 만에 수행하는 등 기존 방식 대비 45.6 배의 속도 향상을 달성했다고 요약할 수 있습니다.

핵심

이 논문은 수학의 오랜 미해결 문제 중 하나인 **'골바흐의 추측 (Goldbach's Conjecture)'**을 검증하기 위해, 일반 컴퓨터 그래픽 카드 (GPU) 를 이용해 놀라운 속도로 계산을 수행한 새로운 방법을 소개합니다.

쉽게 말해, **"모든 2 보다 큰 짝수는 두 개의 소수 (1 과 자기 자신으로만 나누어 떨어지는 수) 의 합으로 만들 수 있다"**는 이 추측을 컴퓨터로 확인하는 작업을, 기존보다 45 배 이상 빠르고 여러 개의 그래픽 카드를 동시에 쓸 수 있도록 업그레이드한 이야기입니다.

이 복잡한 내용을 일상적인 비유로 설명해 드릴게요.

---

1. 골바흐의 추측이란 무엇인가요? (미션)

상상해 보세요. 모든 짝수 (4, 6, 8, 10...) 를 두 개의 소수 (2, 3, 5, 7, 11...) 를 더해서 만들 수 있는지 확인하는 미션입니다.

• 4 = 2 + 2
• 6 = 3 + 3
• 10 = 3 + 7
• ...
  수학자들은 이 규칙이 2 보다 큰 모든 짝수에 맞는지 증명하지 못했습니다. 그래서 컴퓨터로 하나씩 확인해 보는 '검증 작업'을 해왔습니다.

2. 이전 방식의 문제점: "지루한 택배 기사" (구형 GoldbachGPU)

저자가 이전에 개발한 프로그램은 그래픽 카드 (GPU) 를 사용했지만, **CPU(메인 두뇌)**가 일을 너무 많이 했습니다.

• 비유: GPU 는 거대한 공장을, CPU 는 택배 기사라고 생각하세요.
• 문제: 공장은 아주 빠르게 물건을 만들 수 있는데, 택배 기사 (CPU) 가 필요한 원자재 (데이터) 를 하나씩 공장에 가져다주느라 바빴습니다.
• 결과: 공장은 원자재가 올 때까지 빈손으로 기다려야 했습니다. 그래서 그래픽 카드를 두 개로 늘려도 속도가 빨라지지 않았습니다. (택배 기사가 한 명뿐이니까요.)

3. 이번 연구의 혁신: "공장 내부의 자동화 시스템" (새로운 GoldbachGPU v2.0)

이번 논문은 이 문제를 완전히 해결했습니다. 공장이 스스로 원자재를 준비하고, 스스로 일하는 시스템을 만들었습니다.

A. 공장이 스스로 재료를 준비합니다 (GPU 내장 체질)

이전에는 CPU 가 원자재를 준비해서 공장에 보냈지만, 이제는 **공장 내부 (GPU 의 L1 공유 메모리)**에서 바로 원자재를 가공합니다.

• 비유: 공장에 있는 로봇들이 스스로 원자재를 잘게 썰고 다듬어서 바로 조립합니다. 택배 기사 (CPU) 가 오갈 필요도, 기다릴 필요도 없습니다.
• 효과: 데이터 이동 (PCIe 버스) 이 거의 사라져서, 공장은 1 초도 쉬지 않고 일할 수 있습니다.

B. 지루한 대기 없이 일하는 로봇들 (락 프리 작업 도둑)

여러 대의 그래픽 카드를 쓸 때, 각 카드가 할 일을 미리 정해두면 (고정 분배), 느린 카드 때문에 전체가 멈추는 문제가 생깁니다.

• 비유: 4 명의 로봇이 일할 때, "네가 1100 번, 네가 101200 번"이라고 정해두면, 100 번을 끝낸 로봇은 200 번을 하는 로봇이 끝날 때까지 빈손으로 기다려야 합니다.
• 해결: 이번 시스템은 "일할 게 있으면 가져가!" 방식입니다. 한 로봇이 일을 끝내면, 바로 다음 일을 스스로 가져갑니다.
• 결과: 4 대의 그래픽 카드를 써도, 각 로봇이 99% 이상 일하는 시간을 보내게 되어 속도가 거의 4 배 빨라집니다.

4. 놀라운 성과 (결과)

이 새로운 시스템을 사용하면 어떤 일이 일어날까요?

• 속도: 같은 컴퓨터에서 기존 방식보다 45 배 이상 빨라졌습니다. (예: 100 억까지 확인하는 데 걸리는 시간이 18 초에서 0.4 초로 줄었습니다.)
• 규모: 최신 그래픽 카드 4 대 (RTX 5090) 를 연결하면, 133 초 (약 2 분) 만에 10 조 (10^13) 까지 있는 모든 짝수를 확인했습니다.
• 정확성: 컴퓨터 계산에서 흔히 발생하는 '숫자 넘침' 오류를 방지하는 강력한 안전장치도 함께 만들어, 1840 억억 (1.84 × 10^19) 까지 계산이 정확함을 수학적으로 보장했습니다.

5. 요약: 왜 이 연구가 중요한가요?

이 논문은 **"컴퓨터의 힘을 최대한 끌어내는 방법"**을 보여줍니다.

• 과거: "컴퓨터가 일을 하려면 사람이 재료를 가져다줘야 해." (CPU 가 병목 현상)
• 현재: "컴퓨터가 스스로 재료를 만들고, 여러 대가 서로 도와가며 일해." (완전 자동화)

이 기술은 단순히 수학 문제를 푸는 것을 넘어, 여러 개의 고성능 컴퓨터를 연결해 거대한 계산을 할 때 어떻게 하면 가장 효율적으로 일할 수 있는지에 대한 귀중한 교훈을 줍니다. 또한, 모든 코드가 공개되어 누구나 이 기술을 이용해 더 큰 수를 검증해 볼 수 있습니다.

한 줄 요약:

"이제 그래픽 카드들은 택배 기사의 도움을 받지 않고, 스스로 재료를 준비하고 여러 대가 팀워크를 발휘해 133 초 만에 10 조 개의 숫자를 확인하는 초고속 미션을 완수했습니다!"

기술 요약

1. 문제 정의 (Problem)

골드바흐 추측 (2 보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다) 을 검증하기 위한 대규모 계산 작업에서 기존 GPU 기반 접근 방식은 다음과 같은 병목 현상에 직면해 있었습니다:

• 호스트 - 디바이스 통신 병목: 이전 연구 (v1) 에서는 CPU 가 세그먼트별 소수 비트셋을 생성한 후 PCIe 버스를 통해 GPU 로 전송해야 했습니다. GPU 커널 실행 시간이 매우 짧아 (수 밀리초) CPU 가 다음 세그먼트를 준비하는 동안 GPU 가 대기하는 상황이 발생했습니다.
• 확장성 한계: CPU 의 시체 (Sieve) 생성 속도가 GPU 연산 능력을 제한하여, GPU 를 추가하더라도 성능 향상 (스케일링) 이 거의 이루어지지 않았습니다.
• 메모리 제약: 단일 GPU 의 VRAM 용량 한계로 인해 대규모 범위를 검증하기 어려웠습니다.

2. 방법론 (Methodology)

저자는 GoldbachGPU v2.0을 제안하며, 호스트 (CPU) 와 디바이스 (GPU) 간의 의존성을 완전히 제거하고 GPU 만으로 모든 작업을 수행하는 아키텍처를 설계했습니다.

핵심 기술 요소

1. GPU 네이티브 세그먼트 시체 (GPU-Native Segment Sieving):

   • 세그먼트별 소수 비트셋 생성 작업을 CPU 가 아닌 GPU L1 공유 메모리 (Shared Memory) 내에서 수행합니다.
   • 32,768 개의 홀수로 구성된 타일 (Tile) 단위로 나누어 4KB 비트셋을 L1 메모리에 로드하고, GPU 스레드가 협력하여 시체를 수행합니다.
   • 이를 통해 PCIe 전송이 주요 경로 (Critical Path) 에서 제거되었습니다.

2. 잠금 없는 비동기 작업 도난 풀 (Lock-Free Asynchronous Work-Stealing Pool):

   • 정적 작업 분배 대신, 호스트 메모리에 위치한 64 비트 원자적 (Atomic) 카운터 (std::atomic<uint64_t>) 를 사용합니다.
   • 각 GPU 스레드가 fetch_add 연산을 통해 다음 세그먼트를 비동기적으로 claiming 하여, GPU 간 속도 차이 (Thermal throttling, Silicon binning 등) 에 따른 대기 시간을 방지하고 부하를 자동으로 균형 잡습니다.

3. 2 단계 검증 파이프라인:

   • Phase 1 (GPU): 작은 소수 ($p \le 10^6$) 를 사용하여 $q = n - p$가 소수인지 확인합니다. GPU 에서 직접 결과를 집계합니다.
   • Phase 2 (CPU Fallback): Phase 1 에서 검증되지 않은 수가 있을 경우에만 CPU 로 전송하여 최적화된 시체와 128 비트 Miller-Rabin 테스트로 해결합니다. (실제 실험에서는 $10^{13}$까지 Phase 2 가 발동되지 않음)

4. 정확성 보장 및 오버플로우 방어:

   • 64 비트 정수 오버플로우를 방지하기 위해 산술 연산 시 나눗셈 기반의 경계 검사를 적용했습니다.
   • 64 비트 정수에 대해 12 개의 Witness 집합을 사용하는 결정론적 Miller-Rabin 테스트를 적용하여 $1.84 \times 10^{19}$($2^{63.8}$) 까지의 검증 정확성을 수학적으로 보장합니다.

3. 주요 기여 (Key Contributions)

• 완전 GPU 거주 아키텍처: 세그먼트 생성부터 검증까지 전 과정을 GPU 에서 처리하여 호스트 - 디바이스 통신을 최소화했습니다.
• 잠금 없는 스케일링: CPU 의 개입 없이 GPU 만으로 작업을 분배하는 메커니즘을 도입하여 다중 GPU 환경에서 99% 이상의 병렬 효율을 달성했습니다.
• 수학적 엄밀성: 64 비트 정수 범위 내에서의 오버플로우와 논리적 오류를 방지하는 엄격한 방어 기법을 구현했습니다.
• 오픈 소스 및 재현성: 모든 소스 코드와 빌드 스크립트를 공개하여 상용 하드웨어에서 재현 가능하도록 했습니다.

4. 실험 결과 (Results)

실험은 NVIDIA RTX 5090 (Blackwell 아키텍처) 기반의 워크스테이션에서 수행되었습니다.

• 알고리즘적 속도 향상:
  • 동일한 하드웨어 (RTX 5090) 에서 이전 버전 (v1, 호스트 결합형) 대비 $N=10^{10}$에서 45.6 배의 속도 향상을 기록했습니다.
  • 이는 이전 아키텍처가 I/O(PCIe) 병목에 시달렸음을 증명하며, v2 는 계산 병목으로 전환되었음을 의미합니다.
• 다중 GPU 확장성:
  • 2 GPU: 99.7% 병렬 효율 달성.
  • 4 GPU: 98.6% 병렬 효율 달성.
  • 초기화 오버헤드를 제외하면 계산 효율은 거의 100% 에 수렴했습니다.
• 검증 범위 및 시간:
  • 단일 RTX 5090 으로 $10^{12}$까지 36.5 초 만에 검증 완료.
  • 4 개의 RTX 5090 으로 $10^{13}$까지 133.5 초 만에 검증 완료.
  • 모든 범위에서 반례는 발견되지 않았습니다.
• 통신 오버헤드:
  • 세그먼트당 호스트 - 디바이스 전송량은 소수 배치 (약 628KB) 와 검증 결과 스칼라 (4 바이트) 만으로 축소되었습니다.
  • 전체 실행 중 디바이스 - 호스트 트래픽은 총 20KB 에 불과했습니다.

5. 의의 및 결론 (Significance)

이 논문은 골드바흐 추측의 계산적 검증을 위한 새로운 패러다임을 제시합니다.

• 아키텍처적 혁신: GPU 의 연산 능력을 극대화하기 위해 호스트 CPU 의 역할을 최소화하고, 메모리 계층 구조 (L1 Shared Memory) 를 효율적으로 활용한 사례입니다.
• 확장성 증명: 잠금 없는 (Lock-free) 작업 분배 전략을 통해 이기종 및 다중 GPU 클러스터에서도 거의 이상적인 선형 확장성을 달성할 수 있음을 입증했습니다.
• 한계와 미래: 현재 프레임워크는 64 비트 정수 범위 ($1.84 \times 10^{19}$) 까지 검증이 보장되지만, 이를 넘어선 범위를 위해서는 128 비트/256 비트 연산 및 새로운 소수 판별법 (Baillie-PSW 등) 이 필요합니다. 또한, 비트 단위 대량 마킹 (Bitwise bulk-marking) 기법을 적용하면 추가적인 성능 향상이 기대됩니다.

결론적으로, 이 연구는 GPU 기반의 대규모 수론적 검증 작업에서 I/O 병목을 제거하고 순수 계산 성능을 극대화할 수 있는 효율적인 아키텍처를 성공적으로 제시한 의의가 있습니다.