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

Este trabajo presenta una arquitectura totalmente residente en GPU y sin bloqueos para la verificación masiva de la conjetura de Goldbach, que logra una eficiencia paralela superior al 98% y acelera el proceso en 45,6 veces al eliminar la comunicación con el host mediante un mecanismo de robo de trabajo asíncrono y el uso de memoria compartida optimizada.

Lo esencial

¡Hola! Imagina que el Conjetura de Goldbach es un desafío matemático gigante: la idea de que cualquier número par grande (como 10, 100 o un billón) se puede construir sumando dos números primos (esos números mágicos que solo se dividen por sí mismos y por 1, como 2, 3, 5, 7, 11...).

Durante años, los matemáticos han intentado verificar esto para números cada vez más grandes usando superordenadores. Pero había un problema: era como intentar llenar un océano con una cuchara de café.

Este nuevo artículo presenta una revolución en cómo hacemos este trabajo, usando tarjetas gráficas (GPUs) de una manera totalmente nueva. Aquí te lo explico con analogías sencillas:

1. El Problema Anterior: El "Cuello de Botella" del Camión de Mudanzas

Antes, teníamos un sistema donde la CPU (el cerebro del ordenador) preparaba los datos y luego los enviaba a la GPU (el músculo, la tarjeta gráfica) para que hiciera los cálculos.

• La analogía: Imagina que la GPU es un equipo de 100 obreros muy rápidos trabajando en una fábrica. La CPU es el jefe que les lleva los materiales.
• El problema: El jefe (CPU) tenía que preparar una caja de materiales, cargarla en un camión lento (la conexión PCIe), y llevarla a la fábrica. Los obreros terminaban su trabajo en un segundo, pero luego tenían que esperar 10 segundos a que el jefe trajera la siguiente caja.
• Resultado: Los obreros pasaban el 90% del tiempo parados, mirando el reloj. Añadir más obreros (más tarjetas gráficas) no ayudaba porque el jefe seguía siendo el mismo y lento.

2. La Solución: La Fábrica Autónoma (Arquitectura "Lock-Free")

En este nuevo trabajo, el autor (Isaac Llorente-Saguer) ha diseñado un sistema donde la GPU ya no necesita al jefe.

• La analogía: Ahora, los obreros tienen su propia cocina y almacén dentro de la fábrica. No necesitan esperar al camión.
  • Cocina en la GPU: La GPU genera sus propios materiales (los números primos) usando una memoria ultra-rápida que tiene justo al lado de los obreros (llamada memoria compartida L1).
  • Trabajo en equipo sin discusiones: Antes, si dos obreros querían coger la misma caja, tenían que pararse a discutir quién la cogía primero (bloqueos o "locks"). Ahora, usan un sistema de "robos de trabajo" (work-stealing). Si un obrero termina rápido, simplemente coge la siguiente tarea de la pila sin preguntar a nadie. Nadie se detiene, nadie discute.
• Resultado: ¡La fábrica nunca se detiene! Los obreros trabajan al 100% de su capacidad.

3. Los Resultados: Velocidad de la Luz

Gracias a este cambio, los resultados son impresionantes:

• Velocidad: En una sola tarjeta gráfica moderna (una RTX 5090), el sistema verifica números hasta un billón ($10^{12}$) en 36 segundos. ¡Es como si antes tardaran una hora y ahora lo hicieran en un suspiro!
• Escalabilidad: Si usas 4 tarjetas gráficas trabajando juntas, verifican números hasta $10^{13}$ en 2 minutos y medio.
• Eficiencia: El sistema es tan bueno que, si usas 4 tarjetas, funcionan al 98.6% de su capacidad teórica. Es como tener 4 coches de Fórmula 1 corriendo en perfecta sincronía sin chocar.

4. Seguridad: El "Guardián Matemático"

El autor también se preocupó por no cometer errores. Al trabajar con números tan gigantes, existe el riesgo de que una calculadora se equivoque por "desbordamiento" (como cuando un reloj pasa de las 12:59 a las 00:00 y se reinicia).

• La analogía: Han puesto un guardián matemático (llamado Miller-Rabin) que revisa cada cálculo con una lupa de 128 bits. Este guardián garantiza que, hasta un número inmensamente grande ($1.84 \times 10^{19}$), no hay ni un solo error. Si el sistema dice que un número funciona, ¡es verdad!

En Resumen

Este artículo nos dice que hemos pasado de un sistema donde los obreros esperaban al jefe (lento y limitado) a un sistema donde los obreros son autónomos, rápidos y trabajan en equipo perfecto.

Hemos verificado la Conjetura de Goldbach para números más grandes y más rápido que nunca, usando hardware que puedes comprar en una tienda (aunque sea de gama alta), y todo el código está disponible para que cualquiera lo use. Es un ejemplo perfecto de cómo una idea inteligente de arquitectura puede hacer que la tecnología existente vuele.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture" (Una arquitectura sin bloqueos y totalmente residente en GPU para la verificación de la Conjetura de Goldbach), traducido y adaptado al español.

---

Resumen Técnico: Verificación de la Conjetura de Goldbach con Arquitectura GPU-Nativa

1. El Problema

La Conjetura de Goldbach postula que todo número entero par mayor que 2 puede expresarse como la suma de dos números primos. Aunque existen avances teóricos (como el teorema de Chen), la conjetura binaria sigue sin demostrarse. La verificación computacional es crucial para establecer límites empíricos.

El trabajo anterior del autor (GoldbachGPU v1) logró superar el límite de memoria VRAM mediante un "tamizado doble segmentado", pero introdujo un nuevo cuello de botella: la dependencia del anfitrión (CPU). En esa arquitectura, la CPU debía construir el bitset de cada segmento y transferirlo a la GPU a través del bus PCIe. Esto provocaba que las GPUs de alto rendimiento (como la H100 o RTX 3090) permanecieran inactivas esperando datos, limitando la escalabilidad multi-GPU y haciendo que el sistema estuviera limitado por la E/S (I/O) en lugar de por la capacidad de cómputo.

2. Metodología y Arquitectura Propuesta

El artículo presenta GoldbachGPU v2.0, una arquitectura completamente descentralizada y residente en el dispositivo que elimina por completo la dependencia del anfitrión durante el camino crítico de verificación.

Componentes Clave de la Arquitectura:

• Tamizado de Segmentos Nativo en GPU (L1 Shared Memory):

  • Se ha migrado la construcción del tamiz (Sieve of Eratosthenes) desde la CPU a la GPU.
  • Se utiliza un diseño de tiling (mosaico) en la memoria compartida L1 de la GPU. Cada segmento se divide en baldosas de 32,768 números impares (4 KB), que caben perfectamente en los 48 KB de memoria L1 disponibles por Streaming Multiprocessor (SM) en arquitecturas Ada Lovelace y Blackwell.
  • Los hilos de la GPU construyen los bitsets de segmentos de forma cooperativa utilizando un array de primos base residente en memoria de solo lectura.
  • Resultado: Se eliminan las transferencias PCIe de grandes bitsets (14 MB) del camino crítico. La CPU solo envía un índice atómico de inicio y recibe un escalar de 4 bytes.

• Pool de Robo de Trabajo (Work-Stealing) Sin Bloqueos:

  • Se reemplaza la partición estática de la carga de trabajo por un pool asíncrono sin bloqueos.
  • Un contador atómico de 64 bits (g_next_seg_start) en memoria del anfitrión gestiona el trabajo. Cada hilo de la GPU (uno por dispositivo físico) realiza una operación atómica fetch_add para reclamar el siguiente segmento.
  • Esto garantiza una utilización casi del 100% de todos los aceleradores, reequilibrando automáticamente la carga si los GPUs tienen velocidades diferentes (debido a binning de silicio o estrangulamiento térmico).

• Ruta de Cero Copia (Zero-Copy Fast Path):

  • La verificación se realiza en dos fases. La Fase 1 (GPU) verifica si existe un primo $p \le 10^6$ tal que $n - p$ también es primo.
  • Si la GPU encuentra una solución, el resultado se reduce localmente a un contador de "no verificados". Si el contador es cero, se sigue la ruta rápida de cero copia, evitando cualquier transferencia de datos de dispositivo a anfitrión (D2H).
  • Solo si la Fase 1 falla (caso extremadamente raro), se activa una Fase 2 de respaldo en CPU optimizada (búsqueda binaria y prueba de Miller-Rabin determinista de 128 bits).

• Garantías de Corrección y Seguridad:

  • Se implementan guardas matemáticas estrictas para prevenir desbordamientos de enteros de 64 bits.
  • Se utiliza una variante determinista de la prueba de Miller-Rabin con 12 bases, certificada para enteros menores a $2^{64}$.
  • El límite superior teórico de verificación segura se establece en **$1.84 \times 10^{19}$** (aproximadamente$2^{63.8}$).

3. Contribuciones Clave

1. Eliminación del Cuello de Botella de E/S: Migración completa del pipeline de generación de segmentos a la memoria compartida L1 de la GPU, eliminando la latencia de PCIe como factor limitante.
2. Escalabilidad Multi-GPU Eficiente: Implementación de un mecanismo de trabajo asíncrono sin bloqueos que permite una eficiencia paralela del 99.7% con 2 GPUs y 98.6% con 4 GPUs.
3. Velocidad Algorítmica: Logro de un aceleración de 45.6x en comparación con la arquitectura anterior (v1) en el mismo hardware para $N = 10^{10}$.
4. Validación Matemática Rigurosa: Garantía de corrección hasta el límite de $1.84 \times 10^{19}$ mediante aritmética de 128 bits y pruebas de primalidad deterministas.
5. Reproducibilidad y Código Abierto: El código está disponible públicamente, con instrucciones de compilación y scripts para replicar los resultados en hardware comercial.

4. Resultados Experimentales

Los experimentos se realizaron en una estación de trabajo con NVIDIA RTX 5090 (arquitectura Blackwell) bajo CUDA 12.8.1.

• Comparación de Hardware Idéntico (v1 vs v2):
  • En $N = 10^{10}$, la arquitectura v2 completó la tarea en 395.8 ms, frente a los 18,056.5 ms de la v1.
  • Esto representa un speedup de 45.6x, confirmando que la arquitectura anterior estaba limitada por la E/S (PCIe) y no por el cómputo.
• Verificación de Rango Completo:
  • $10^{12}$: Verificado en 36.5 segundos en una sola RTX 5090.
  • $10^{13}$: Verificado en 133.5 segundos en un sistema de 4 GPUs RTX 5090.
• Eficiencia Paralela:
  • Se midió una eficiencia del 99.7% con 2 GPUs y 98.6% con 4 GPUs.
  • El análisis de perfilado (Nsight Systems) mostró una saturación casi continua de los dispositivos, con un tiempo de kernel agregado de 79.4s contra un tiempo de reloj de pared de 20.5s en la configuración de 4 GPUs.
  • No se activó ninguna fase de respaldo (Phase 2) en ningún límite probado, confirmando que la conjetura se cumple con primos pequeños ($p \le 10^6$) para todos los números pares hasta $10^{13}$.

5. Significado e Impacto

Este trabajo representa un avance significativo en la computación de alto rendimiento para problemas de teoría de números:

• Cambio de Paradigma: Demuestra que es posible eliminar la dependencia del anfitrión en tareas de tamizado masivo, permitiendo que las GPUs operen de forma totalmente autónoma.
• Eficiencia de Recursos: Al eliminar las transferencias de datos innecesarias, se maximiza la utilidad de hardware costoso (GPUs de última generación), haciendo viable la verificación de rangos mucho más grandes en tiempos razonables.
• Escalabilidad Futura: La arquitectura está diseñada para ser distribuida fácilmente en clústeres heterogéneos o multi-nodo mediante el uso de parámetros de línea de comandos (--start), sentando las bases para futuras verificaciones que superen el récord actual de $4 \times 10^{18}$ establecido por Oliveira e Silva et al.
• Límites y Futuro: El artículo identifica claramente el límite actual de 64 bits y propone direcciones para futuras investigaciones, como el uso de aritmética de 128/256 bits en PTX y kernels de marcado masivo a nivel de warp para mejorar aún más el rendimiento.

En conclusión, GoldbachGPU v2.0 establece un nuevo estándar en la verificación computacional de la Conjetura de Goldbach, combinando optimizaciones de bajo nivel de GPU con una arquitectura de software robusta y sin bloqueos.