🔢 mathematics

GoldbachGPU: An Open Source GPU-Accelerated Framework for Verification of Goldbach's Conjecture

본 논문은 비트-팩킹과 세그먼트형 이중 체를 활용한 메모리 최적화 기법으로 단일 GPU 에서 골드바흐 추측을 10^12 까지 검증하고, 다중 GPU 및 임의 정밀도 검증을 지원하는 오픈소스 프레임워크 'GoldbachGPU'를 제안합니다.

원저자: Isaac Llorente-Saguer

게시일 2026-03-04

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Isaac Llorente-Saguer

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

골드바흐 추측을 GPU 로 해결하다: '골드바흐 GPU' 프로젝트 설명

이 논문은 수학의 거대한 미해결 문제 중 하나인 **'골드바흐의 추측 (Goldbach's Conjecture)'**을 검증하기 위해 만든 새로운 소프트웨어 프레임워크에 대한 이야기입니다.

이걸 이해하기 쉽게, 거대한 도서관과 빠른 사서의 비유로 설명해 드릴게요.

1. 골드바흐의 추측이란 무엇일까요?

수학자 골드바흐는 1742 년에 이런 질문을 던졌습니다.

"2 보다 큰 모든 짝수는 두 개의 소수 (1 과 자기 자신 외에는 약수가 없는 수) 를 더해서 만들 수 있을까?"

예를 들어:

4 = 2 + 2
10 = 3 + 7
100 = 47 + 53

이것은 아주 작은 숫자에서는 항상 성립하지만, 숫자가 엄청나게 커질수록 (예: 100 자리, 1000 자리) 이 규칙이 깨지지 않는지 확인하는 것은 엄청난 계산이 필요합니다. 지금까지 컴퓨터로 10^18 (100京) 까지 확인했지만, 그 이상은 아직 미스터리였습니다.

2. 기존 문제: "메모리라는 벽"

기존에 그래픽카드 (GPU) 를 이용해 이 문제를 풀려고 시도한 연구자들은 한 가지 큰 장벽에 부딪혔습니다. 바로 메모리 (VRAM) 부족입니다.

비유: 우리가 도서관에서 모든 책 (소수) 을 찾아보려면, 도서관의 모든 책 목록을 책상 위에 펼쳐놓고 있어야 합니다.
문제: 숫자가 커질수록 책 목록이 너무 길어져서 책상 (GPU 메모리) 에 다 올라가지 않습니다. 이전 연구들은 책 목록이 10^11 정도가 되면 책상이 꽉 차서 더 이상 진행할 수 없었습니다.

3. 이 연구의 해결책: "골드바흐 GPU"

저자 (아이작 로렌테 - 사구에르) 는 이 문제를 해결하기 위해 세 가지 창의적인 방법을 섞어 새로운 프로그램을 만들었습니다.

① "책 정리법" 바꾸기 (밀집 비트셋)

기존에는 한 숫자당 1 바이트 (1 글자) 를 써서 메모리를 차지했습니다. 하지만 이 연구는 **"짝수는 소수가 될 수 없으니 아예 목록에서 빼고, 홀수만 0 과 1 로 압축해서 저장"**했습니다.

효과: 메모리 사용량을 16 배나 줄였습니다. 마치 책장을 꽉 채우려던 책을 접어서 넣은 것과 같습니다. 덕분에 8GB 메모리를 가진 일반 게이밍 그래픽카드 (RTX 3070) 로도 10^11 까지의 소수 목록을 모두 담을 수 있게 되었습니다.

② "조각난 도서관" 전략 (세그먼트형 이중 체)

하지만 10^12 (100 조) 까지 가려면 메모리가 여전히 부족합니다. 이때 저자는 전체 목록을 한 번에 보는 대신, 작은 조각 (Segment) 으로 나누어 처리했습니다.

비유: 도서관 전체를 한 번에 보는 게 아니라, 한 구역 (예: A~B 구간의 책) 만 책상에 가져와서 확인합니다.
작동 원리:
1. CPU 가 작은 조각 (약 14MB 크기) 의 소수 목록을 만들어 GPU 로 보냅니다.
2. GPU 는 그 조각 안에서만 짝수를 확인합니다.
3. 확인이 끝나면 그 조각을 버리고 다음 조각을 가져옵니다.
결과: 메모리 사용량이 숫자가 커져도 일정하게 유지됩니다. (O(1) 메모리). 마치 책상 위에 항상 14MB 만 차지하는 책상 위를 사용하면서, 도서관 전체를 순회하는 것과 같습니다.

③ "스마트 검색" (3 단계 검증)

GPU 가 숫자를 확인할 때, 모든 소수를 다 찾아보는 건 비효율적입니다. 그래서 3 단계 검색을 도입했습니다.

작은 소수: 아주 작은 소수는 GPU 메모리에 항상 상주시켜서 즉시 확인 (가장 빠름).
현재 구간의 소수: 지금 처리 중인 조각에 있는 소수는 조각 목록에서 확인.
중간 구간: 그 사이는 '밀러 - 라빈'이라는 수학적 테스트로 빠르게 확인.
이렇게 하면 GPU 가 일을 덜 해도 정확한 결과를 얻을 수 있습니다.

4. 성과: 무엇이 달라졌나요?

이 프로그램을 일반인도 쓸 수 있는 NVIDIA RTX 3070 그래픽카드 하나만 달린 컴퓨터로 실행했습니다.

기록 경신: 단일 GPU 로 **10^12 (100 조)**까지의 모든 짝수를 확인했습니다. 이는 기존 단일 GPU 기록보다 10 배 더 큰 범위입니다.
시간: 100 조까지 확인하는 데 약 41 분이 걸렸습니다.
결과: 반례 (규칙이 깨지는 경우) 는 단 하나도 발견되지 않았습니다.
확장성: 이 기술은 데이터센터의 고성능 GPU 8 개를 연결하면 더 빠르게 확장할 수 있습니다. 또한, 10,000 자리 같은 거대 숫자 하나를 확인하는 기능도 구현했습니다.

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

이 논문은 **"하드웨어의 한계가 아니라, 알고리즘의 문제였다"**는 것을 증명했습니다.

예전에는 "GPU 메모리가 부족해서 더 큰 수를 못 확인한다"고 생각했지만, 실제로는 데이터를 어떻게 저장하고 처리하느냐에 따라 일반 가정용 컴퓨터로도 슈퍼컴퓨터 수준의 연산을 할 수 있음을 보여줬습니다.
모든 코드 (소스 코드) 를 공개하여 누구나 검증하고 개선할 수 있게 했습니다.

요약

이 연구는 "거대한 도서관 (수학 문제) 을 해결하기 위해, 책상 (메모리) 을 넓히는 대신 책을 효율적으로 정리하고 (압축), 한 번에 한 구역씩만 옮겨가며 (세그먼트) 빠르게 확인하는 (GPU 가속)" 새로운 방법을 개발했습니다. 그 결과, 일반인도 쓸 수 있는 컴퓨터로 수학의 거대한 미스터리 중 하나를 더 깊이 파헤칠 수 있게 되었습니다.

1. 문제 정의 (Problem)

골드바흐 추측 (Goldbach's Conjecture) 은 "2 보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다"는 명제입니다. 이 추측은 아직 수학적으로 증명되지 않았으며, 컴퓨터를 통한 대규모 검증이 중요한 보완 역할을 해왔습니다.

기존의 GPU 기반 접근 방식은 다음과 같은 한계에 직면해 있었습니다:

메모리 병목 현상: 단일 GPU 의 VRAM(비디오 메모리) 에 모든 소수 테이블을 한 번에 로드하는 '모놀리식 (Monolithic)' 방식은 약 $10^{11}$ 이상의 범위로 확장 시 메모리 부족으로 인해 실패했습니다.
확장성 부재: 기존 오픈소스 프레임워크 중 단일 GPU 로 $10^{11}$ 을 넘어선 완전한 검증을 수행한 사례는 없었습니다.
스레드 발산: 비효율적인 메모리 접근 패턴으로 인한 스레드 발산 (Thread Divergence) 이 성능 저하의 주요 원인이었습니다.

2. 방법론 (Methodology)

이 논문은 GoldbachGPU라는 오픈소스 프레임워크를 제안하며, 상용 GPU 하드웨어 (예: NVIDIA RTX 3070) 를 사용하여 $10^{12}$ 까지 검증하는 데 성공했습니다. 핵심 기술적 접근법은 다음과 같습니다.

A. 밀집 비트셋 (Dense Bit-packed Representation)

소수 테이블을 바이트 배열 대신 비트 단위 (Bit-packed) 로 압축 저장합니다.
짝수 (2 제외) 는 소수가 아니므로 저장에서 제외하고, 홀수만 저장하여 메모리 사용량을 16 배 감소시켰습니다.
이를 통해 $10^{11}$ 범위까지의 소수 테이블을 8GB VRAM 을 가진 GPU 에 상주시킬 수 있게 되었습니다.

B. 세그먼트된 더블-체기 (Segmented Double-Sieve) 아키텍처

기존의 "각 짝수 $n$ 에 대해 소수 $p$ 를 찾는다"는 방식 대신, Oliveira e Silva 의 루프 반전 (Loop Inversion) 전략을 차용했습니다.

루프 반전: 후보 소수 $p$ 를 반복하며, $q = n - p$ 가 소수인지 확인하여 해당 짝수 $n$ 을 마킹합니다.
세그먼트 처리: 전체 범위를 작은 구간 (Segment) 으로 나누어 처리합니다. 각 구간은 CPU 에서 체 (Sieve) 를 수행하여 생성된 비트셋 (약 14MB) 을 VRAM 으로 전송합니다.
다단계 소수 판별 오라클 (Primality Oracle): GPU 커널은 $q$ $q$ 의 소수 여부를 다음 우선순위로 판단합니다.
- Priority 1: $q \le P_{SMALL}$ (상주하는 작은 소수 비트셋, 약 122KB)
- Priority 2: $q \in [A, B]$ (현재 세그먼트 비트셋, 약 14MB)
- Priority 3: $P_{SMALL} < q < A$ (결정론적 64-bit Miller-Rabin 테스트)
- 이 방식은 VRAM 에 전체 소수 테이블이 필요 없게 하여 메모리 제약을 완전히 제거합니다.

C. 검증 체계

GPU Fast-path: 위 오라클을 통해 대부분의 경우 GPU 에서 빠르게 해결합니다.
CPU Fallback: GPU 에서 해를 찾지 못한 경우를 대비해 엄격한 CPU 기반 전수 조사를 수행하지만, 실제 실험에서는 한 번도 호출되지 않았습니다.
임의 정밀도 (Arbitrary Precision): GMP 라이브러리를 사용하여 $10^{10,000}$ 이상의 매우 큰 숫자에 대한 단일 숫자 검증을 지원합니다.

3. 주요 기여 (Key Contributions)

VRAM 천장 제거: 세그먼트된 더블-체기 아키텍처를 통해 단일 상용 GPU 로 $10^{12}$ 까지 완전 검증을 가능하게 함.
메모리 효율성 향상: 밀집 비트셋을 도입하여 기존 방식 대비 16 배의 메모리 절감 효과 달성 ( $10^{11}$ 범위까지 GPU 상주 가능).
수학적 완전성 보장: GPU 의 빠른 처리와 CPU 의 엄격한 백업 (Fallback) 을 결합하여 결과의 정확성을 보장.
임의 정밀도 검증: GMP 와 OpenMP 를 활용한 동기화된 배치 검색 전략으로 $10^{10,000}$ 까지 검증 가능.
오픈소스 및 재현성: 모든 코드가 공개되어 있으며, 상용 하드웨어와 데이터센터급 하드웨어 모두에서 재현 가능.

4. 실험 결과 (Results)

하드웨어 환경: Intel i7-12700H CPU, NVIDIA RTX 3070 (8GB VRAM).
검증 범위: 단일 GPU 로 $10^{12}$ 까지 완전 검증 완료.
성능:
- $10^9$ 범위에서 CPU 대비 16 배 속도 향상.
- $10^{12}$ 범위 검증 소요 시간: 약 41 분.
- 메모리 사용량: 세그먼트당 고정된 14 MB만 사용 ( $O(1)$ 메모리 복잡도).
- 오류 발견: 모든 계산에서 반례 (Counterexample) 는 발견되지 않음.
확장성:
- 8 개의 H100 GPU 를 사용한 데이터센터 환경에서도 선형적인 확장성 (Strong Scaling) 을 보임.
- $N=10^{10}$ 에서 6 개 GPU 사용 시 80% 이상의 병렬 효율 달성.
임의 정밀도: 10,001 자리 수 ( $10^{10,000}$ ) 에 대한 검증이 20 개 스레드에서 약 182 초 소요됨.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 GPU 컴퓨팅의 메모리 한계가 하드웨어의 근본적인 제약이 아니라, 아키텍처적 설계 (모놀리식 테이블 저장) 의 문제임을 증명했습니다.

기술적 돌파구: 단순한 병렬 처리를 넘어, 메모리 효율적인 데이터 표현 (비트셋) 과 알고리즘적 최적화 (세그먼트 체) 를 결합하여 상용 하드웨어로 이전에는 불가능했던 규모의 수학적 검증을 가능하게 했습니다.
미래 전망: 현재 CPU 기반의 세그먼트 생성이 병목 현상이지만, 이를 GPU 로 이전하고 비트 단위 연산을 최적화한다면 단일 GPU 로 $10^{15}$ 이상의 범위를 검증할 수 있을 것으로 기대됩니다.
결론: GoldbachGPU 는 골드바흐 추측의 검증 범위를 단일 GPU 환경에서 $10^{12}$ 까지 확장시켰으며, 오픈소스 프레임워크로서 향후 대규모 분산 계산 및 고사양 하드웨어 활용의 기준을 제시했습니다.