🔢 mathematics

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

यह शोध पत्र एक पूर्णतः डिवाइस-रेसिडेंट, मल्टी-जीपीयू आर्किटेक्चर प्रस्तुत करता है जो लॉक-फ्री वर्क-स्टीलिंग और अनुकूलित शेयर्ड-मेमोरी टिलिंग के माध्यम से नियर-जीरो होस्ट-डिवाइस कम्युनिकेशन और 99.7% पैरेलल एफिशिएंसी प्राप्त करता है, जिससे एक चार-जीपीयू सिस्टम पर पिछले तरीकों की तुलना में 45.6× स्पीडअप के साथ मात्र 133.5 सेकंड में $10^{13}$ तक गोल्डबैक के अनुमान (Goldbach's conjecture) का सत्यापन संभव हो पाता है।

मूल लेखक: Isaac Llorente-Saguer

प्रकाशित 2026-03-10

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Isaac Llorente-Saguer

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ इस शोध पत्र का विवरण है, जिसे "अकादमिक भाषा" से बदलकर रोजमर्रा की भाषा में सरल उपमाओं (analogies) के माध्यम से समझाया गया है।

बड़ी तस्वीर: वे क्या करने की कोशिश कर रहे हैं?

एक विशाल, अनंत पुस्तकालय की कल्पना करें जहाँ हर किताब एक सम संख्या (even number) जैसे कि 4, 6, 8, 10, आदि का प्रतिनिधित्व करती है। एक प्रसिद्ध गणितीय पहेली जिसे गोल्डबैक कंजेक्चर (Goldbach's Conjecture) कहा जाता है, दावा करती है कि इन सभी किताबों में से प्रत्येक को खोला जा सकता है और उसमें दो "प्राइम नंबर" (अभाज्य संख्या) वाले पृष्ठ मिल सकते हैं जिनका योग उस किताब की संख्या के बराबर हो।

उदाहरण के लिए:

किताब #10 = पेज 3 + पेज 7 (दोनों प्राइम हैं)।
किताब #100 = पेज 3 + पेज 97।

गणितज्ञों ने बहुत बड़ी संख्याओं तक इसकी जाँच की है, लेकिन वे इससे भी ऊपर जाना चाहते हैं। समस्या यह है कि इन संख्याओं की एक-एक करके जाँच करने में बहुत लंबा समय लगता है। यह शोध पत्र इन किताबों को जितनी जल्दी हो सके जाँचने के लिए एक सुपर-फास्ट, स्वचालित फैक्ट्री बनाने के बारे में है।

पुरानी फैक्ट्री (वर्जन 1.0): "कन्वेयर बेल्ट" की समस्या

लेखक के पिछले काम में, उन्होंने GPUs (जो वीडियो गेम्स और AI के दिमाग होते हैं) नामक शक्तिशाली कंप्यूटर चिप्स का उपयोग करके एक फैक्ट्री बनाई थी।

सेटअप: GPU एक सुपर-फास्ट वर्कर था। CPU (मुख्य कंप्यूटर दिमाग) मैनेजर था।
रुकावट (Bottleneck): मैनेजर (CPU) को हर एक बैच के लिए "प्राइम नंबर्स" की एक सूची लिखनी पड़ती थी, उसे वर्कर (GPU) को सौंपना पड़ता था, वर्कर के काम पूरा करने का इंतज़ार करना पड़ता था, फिर सूची वापस लेना पड़ता था, एक नई सूची लिखना पड़ता था और फिर उसे सौंपना पड़ता था।
उपमा: एक फॉर्मूला 1 रेस कार (GPU) की कल्पना करें जो 200 मील प्रति घंटे की रफ्तार से चल सकती है। लेकिन, हर बार जब वह एक लैप पूरा करती है, तो उसे पिट लेन में रुकना पड़ता है, टायर बदलने के लिए मैकेनिक (CPU) का इंतज़ार करना पड़ता है, और फिर मैकेनिक से नया मैप लेने के लिए इंतज़ार करना पड़ता है। भले ही कार तेज़ है, लेकिन वह अपना 90% समय पिट लेन में बैठकर इंतज़ार करने में बिता देती है। अधिक रेस कारें जोड़ने से भी कोई मदद नहीं मिली क्योंकि समस्या कारों की नहीं, बल्कि धीमे मैकेनिक की थी।

नई फैक्ट्री (वर्जन 2.0): "सेल्फ-ड्राइविंग" क्रांति

यह नया शोध पत्र एक पूरी तरह से पुनर्गठित फैक्ट्री पेश करता है जहाँ वर्कर्स को अब मैनेजर का इंतज़ार करने की ज़रूरत नहीं है।

1. "स्व-निहित" वर्कर (GPU-Native Sieving)

मैनेजर द्वारा प्राइम नंबर्स की सूची सौंपने के बजाय, अब वर्कर्स के पास उनके अपने कार्यक्षेत्र में ही एक छोटी, सुपर-फास्ट नोटबुक (जिसे L1 Shared Memory कहा जाता है) है।

बदलाव: वर्कर अब अपनी खुद की प्राइम नंबर्स की सूची लिख सकता है, किताबों की जाँच कर सकता है, और तुरंत अगले बैच पर जा सकता है।
परिणाम: "पिट स्टॉप" खत्म हो गया है। रेस कार कभी नहीं रुकती। वह बस चलती रहती है। इसने प्रक्रिया को पहले की तुलना में 45 गुना तेज़ बना दिया है।

2. "फ्री-फॉर-ऑल" वर्क क्यू (Lock-Free Work-Stealing)

पुराने सिस्टम में, मैनेजर विशिष्ट वर्कर्स को विशिष्ट बैच असाइन करता था। यदि एक वर्कर थोड़ा धीमा था (शायद उसकी कॉफी ठंडी थी, या उसका चिप थोड़ा पुराना था), तो पूरी फैक्ट्री को उसके लिए रुकना पड़ता था।

नया सिस्टम: कमरे के बीच में बिना क्रम वाली किताबों के ढेर की कल्पना करें। कोई भी वर्कर जो अपना वर्तमान कार्य पूरा कर लेता है, वह बस अगला उपलब्ध ढेर उठा लेता है। यदि कोई वर्कर तेज़ है, तो वह अधिक ढेर उठाता है। यदि कोई धीमा है, तो वह कम ढेर उठाता है।
परिणाम: कोई भी खाली खड़ा होकर इंतज़ार नहीं करता। सिस्टम अपने आप संतुलन बना लेता है। शोध पत्र दिखाता है कि 4 वर्कर्स के साथ, फैक्ट्री 98.6% दक्षता (लगभग पूर्ण) के साथ चलती है।

3. "सेफ्टी नेट" (Overflow Guards)

जब आप $10^{19}$ (यानी 1 के पीछे 19 शून्य) जैसी बड़ी संख्याओं तक गिनती करते हैं, तो सामान्य कंप्यूटर गणित भ्रमित हो सकता है और वापस शून्य पर आ सकता है, जैसे कार का ओडोमीटर 999,999 से वापस 000,000 पर आ जाता है।

समाधान: लेखक ने सख्त "गणितीय सीटबेल्ट" बनाई है। यदि संख्याएँ कंप्यूटर के मानक गणित के लिए बहुत बड़ी हो जाती हैं, तो सिस्टम एक विशेष "128-बिट" मोड पर स्विच हो जाता है ताकि गिनती कभी गलत न हो। उन्होंने साबित किया कि यह सिस्टम एक विशिष्ट सीमा ( $1.84 \times 10^{19}$ ) तक सुरक्षित है।

परिणाम: यह कितना तेज़ है?

लेखक ने इस नए सिस्टम का परीक्षण नवीनतम और सबसे शक्तिशाली ग्राफिक्स कार्ड (NVIDIA RTX 5090s) पर किया।

पुराना तरीका: $10^{10}$ तक की संख्याओं की जाँच करने में लंबा समय लगता था।
नया तरीका: यह वही काम 45 गुना तेज़ी से करता है।
रिकॉर्ड:
- एक सुपर-कंप्यूटर कार्ड ने मात्र 36 सेकंड में 1 ट्रिलियन ( $10^{12}$ ) तक की जाँच की।
- चार कार्डों ने मिलकर केवल 2 मिनट 13 सेकंड में 10 ट्रिलियन ( $10^{13}$ ) तक की जाँच की।

यह क्यों महत्वपूर्ण है?

यह ओपन सोर्स है: लेखक ने अपना रहस्य छिपाकर नहीं रखा। कोई भी सामान्य गेमिंग पीसी के साथ इस कोड को डाउनलोड कर सकता है और इन जाँचों को चला सकता है।
यह हार्डवेयर की समस्या को हल करता है: यह साबित करता है कि आपको भारी गणित के लिए लाखों डॉलर के सुपरकंप्यूटर की आवश्यकता नहीं है; आपको बस कंप्यूटर को खुद का इंतज़ार करने से रोकना होगा।
यह एक सीढ़ी है: हालाँकि उन्होंने गोल्डबैक कंजेक्चर को सिद्ध नहीं किया है (जो कि एक गणितीय प्रमाण है, न कि केवल एक जाँच), उन्होंने उस सीमा को आगे बढ़ा दिया है जिसे हम पहले से कहीं अधिक सत्यापित (verify) कर सकते हैं, जिससे गणितज्ञों को इस बात का अधिक विश्वास मिलता है कि यह नियम सच है।

सारांश उपमा

एक विशाल दीवार को पेंट करने की कल्पना करें।

वर्जन 1: आपके पास पेंटर्स की एक टीम है, लेकिन हर ब्रशस्ट्रोक के लिए एक व्यक्ति को सप्लाई क्लोजेट (सामान रखने की जगह) तक दौड़कर जाना पड़ता है। पेंटर्स तेज़ हैं, लेकिन दौड़ने वाला व्यक्ति धीमा है।
वर्जन 2: आप हर पेंटर को उनकी जेब में ही पेंट का अपना व्यक्तिगत, अनंत भंडार दे देते हैं। उनके पास एक ऐसी प्रणाली भी है जहाँ वे खाली होने पर बस दीवार का अगला खाली हिस्सा पकड़ लेते हैं।
परिणाम: दीवार का पेंटिंग का काम बहुत कम समय में पूरा हो जाता है, और अधिक पेंटर्स जोड़ने से वास्तव में फर्क पड़ता है क्योंकि कोई भी सप्लाई क्लोजेट के लिए इंतज़ार नहीं कर रहा होता।

यहाँ "गोल्डबैक अनुमान के सत्यापन के लिए एक लॉक-फ्री, पूर्णतः GPU-रेसिडेंट आर्किटेक्चर" नामक शोध पत्र का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

गोल्डबैक अनुमान (Goldbach's conjecture) यह प्रतिपादित करता है कि 2 से बड़े प्रत्येक सम पूर्णांक (even integer) दो अभाज्य संख्याओं (prime numbers) का योग है। $4 \times 10^{18}$ तक इसके सत्यापन के लिए वितरित CPU क्लस्टरों का उपयोग किया गया है, लेकिन इस सत्यापन को और आगे बढ़ाने के लिए महत्वपूर्ण कम्प्यूटेशनल बाधाओं को दूर करना आवश्यक है।

लेखक के पूर्व कार्य (GoldbachGPU v1) ने सेगमेंटेड सीव (segmented sieve) का उपयोग करके VRAM सीमाओं को सफलतापूर्वक संबोधित किया, जिससे मेमोरी फुटप्रिंट घटकर निरंतर 14 MB रह गया। हालाँकि, इस आर्किटेक्चर ने एक नई महत्वपूर्ण बाधा उत्पन्न की: होस्ट-डिवाइस I/O लेटेंसी (Host-Device I/O Latency)।

v1 में, CPU प्रत्येक सेगमेंट के लिए प्राइम बिटसेट (prime bitset) तैयार करता था और उसे PCIe के माध्यम से GPU को स्थानांतरित करता था।
आधुनिक हाई-बैंडविड्थ वाले GPUs पर, वेरिफिकेशन कर्नल कुछ मिलीसेकंड में ही पूरा हो जाता था, जिससे GPU अगले सेगमेंट की प्रतीक्षा में खाली बैठा रहता था जबकि CPU अगला सेगमेंट तैयार कर रहा होता था।
इसने सिस्टम को कंप्यूट-बाउंड के बजाय I/O-बाउंड बना दिया, जिससे कई GPUs (जैसे, दूसरा GPU जोड़ने पर भी कोई गति नहीं मिली) के माध्यम से प्रभावी स्केलिंग करना असंभव हो गया।

2. कार्यप्रणाली: GoldbachGPU v2.0 (Methodology)

यह शोध पत्र एक पूर्णतः डिवाइस-रेसिडेंट, लॉक-फ्री आर्किटेक्चर का प्रस्ताव करता है जो क्रिटिकल वेरिफिकेशन पाथ से होस्ट CPU को पूरी तरह हटा देता है। यह सिस्टम हेट्रोजेनियस मल्टी-GPU क्लस्टर्स के लिए डिज़ाइन किया गया है।

A. GPU-नेटिव सेगमेंट सीविंग (L1 शेयर्ड मेमोरी)

चूँकि CPU सेगमेंट बिटसेट्स जनरेट करने के बजाय, सीव जनरेशन को पूरी तरह से GPU में स्थानांतरित कर दिया गया है:

टायल्ड सीव (Tiled Sieve): सेगमेंट को 32,768 विषम संख्याओं (4 KB बिटसेट्स) के टाइल्स में विभाजित किया गया है।
L1 ऑप्टिमाइज़ेशन: इन टाइल्स को सीधे GPU की L1 शेयर्ड मेमोरी (Ada/Blackwell आर्किटेक्चर पर प्रति SM 48 KB) में लोड किया जाता है।
प्रक्रिया: GPU थ्रेड्स बेस प्राइम्स के एक स्थायी रूप से रेजिडेंट, रीड-ओनली एरे का उपयोग करके टाइल्स को सहयोगात्मक रूप से सीव (sieve) करते हैं। परिणाम को ग्लोबल VRAM में फ्लश किया जाता है।
प्रभाव: यह प्रति सेगमेंट 14 MB के वेरिएबल PCIe ट्रांसफर को समाप्त करता है। अब होस्ट केवल छोटे प्राइम्स का निरंतर ~628 KB बैच स्थानांतरित करता है और 4-बाइट का परिणाम प्राप्त करता है।

B. लॉक-फ्री एसिंक्रोनस वर्क-स्टीलिंग पूल (Lock-Free Asynchronous Work-Stealing Pool)

मल्टी-GPU दक्षता को अधिकतम करने के लिए, सिस्टम स्टेटिक वर्कलोड पार्टीशनिंग के स्थान पर एक डायनेमिक, लॉक-फ्री दृष्टिकोण अपनाता है:

एटोमिक क्लेमिंग (Atomic Claiming): होस्ट मेमोरी में एक सिंगल 64-बिट एटोमिक काउंटर (g_next_seg_start) अगले प्रोसेस होने वाले सेगमेंट को ट्रैक करता है।
वर्क-स्टीलिंग (Work-Stealing): प्रत्येक GPU वर्कर थ्रेड (एक भौतिक GPU के लिए एक) अगले सेगमेंट को क्लेम करने के लिए एक एटोमिक fetch_add करता है।
लाभ: यह सिलिकॉन बिनिंग या थर्मल थ्रॉटलिंग के कारण प्रदर्शन में भिन्नता वाले विभिन्न GPUs के बीच वर्कलोड को स्वचालित रूप से संतुलित करता है और बिना किसी म्यूटेक्स कंटेंशन (mutex contention) के लगभग 100% डिवाइस यूटिलाइजेशन प्राप्त करता है।

C. ज़ीरो-कॉपी फास्ट पाथ और फेज 2 फॉलबैक (Zero-Copy Fast Path & Phase 2 Fallback)

फेज 1 (GPU): GPU उम्मीदवार प्राइम्स $p \le 10^6$ के लिए $n = p + q$ की जाँच करता है।
रिडक्शन (Reduction): एक डिवाइस-साइड कर्नल "अनवेरिफाइड" (unverified) संख्याओं की गणना करता है।
फास्ट पाथ: यदि गणना शून्य है (जो सभी परीक्षण किए गए रेंज के लिए होता है), तो परिणाम एक 4-बाइट स्केलर होता है। कोई बड़ा डेटा ट्रांसफर नहीं होता है।
फेज 2 (CPU फॉलबैक): यदि अनवेरिफाइड संख्याएँ मौजूद हैं, तो एक PCIe ट्रांसफर होता है, और होस्ट CPU एक प्री-कंप्यूटेड प्राइम एरे और 128-बिट डिटरमिनिस्टिक मिलर-राबिन टेस्ट का उपयोग करके उन्हें हल करता है। व्यवहार में, यह फेज $N \le 10^{13}$ के लिए कभी भी कॉल नहीं किया जाता है।

D. गणितीय सुदृढ़ता और सुरक्षा (Mathematical Soundness & Safety)

ओवरफ्लो गार्ड्स (Overflow Guards): सीव अरिथमेटिक (जैसे $p^2$ गणना) के दौरान 64-बिट पूर्णांक ओवरफ्लो को रोकने के लिए सख्त डिवीजन-आधारित गार्ड्स का उपयोग किया गया है।
डिटरमिनिस्टिक प्राइमैलिटी: सिस्टम एक 12-विटनेस डिटरमिनिस्टिक मिलर-राबिन टेस्ट का उपयोग करता है, जो $n < 2^{64}$ के लिए सिद्ध रूप से सही है।
ऊपरी सीमा (Upper Bound): यह फ्रेमवर्क $1.84 \times 10^{19}$ (लगभग $2^{63.8}$ ) तक गणितीय रूप से सुदृढ़ है। इसके आगे, 128-बिट इंटरमीडिएट उत्पाद ओवरफ्लो हो जाएंगे और विटनेस सेट के नियम लागू नहीं होंगे।

3. प्रमुख योगदान (Key Contributions)

होस्ट-डिवाइस बॉटलनैक का उन्मूलन: सीव जनरेशन को GPU के L1 शेयर्ड मेमोरी में स्थानांतरित करके, आर्किटेक्चर ने समस्या को I/O-बाउंड से कंप्यूट-बाउंड में बदल दिया, जिससे वास्तविक मल्टी-GPU स्केलिंग संभव हुई।
लॉक-फ्री मल्टी-GPU स्केलिंग: एक एटोमिक वर्क-स्टीलिंग पूल का परिचय, जो स्टेटिक पार्टीशनिंग में निहित "स्ट्रैगलर" (straggler) समस्या को दूर करते हुए 4 GPUs पर >98% पैरेलल एफिशिएंसी प्राप्त करता है।
एल्गोरिद्मिक स्पीडअप: समान हार्डवेयर पर $N=10^{10}$ पर पिछले होस्ट-कपल्ड संस्करण की तुलना में 45.6× की गति वृद्धि।
रिकॉर्ड-ब्रेकिंग वेरिफिकेशन: 4-GPU सिस्टम (RTX 5090) का उपयोग करके 133.5 सेकंड में $10^{13}$ तक गोल्डबैक अनुमान का सत्यापन।
ओपन-सोर्स पुनरुत्पादकता (Reproducibility): वितरित नोड्स में फ्लेक्सिबल रेंज पार्टीशनिंग के लिए CLI सपोर्ट के साथ पूर्ण कोड उपलब्धता।

4. परिणाम (Results)

प्रयोग NVIDIA RTX 5090 GPUs (Blackwell आर्किटेक्चर) का उपयोग करके CUDA 12.8.1 पर किए गए थे।

सिंगल GPU प्रदर्शन:
- $10^{12}$ को 36.5 सेकंड में सत्यापित किया।
- $10^{13}$ को 365 सेकंड में सत्यापित किया (स्केलिंग डेटा से निकाला गया, वास्तविक 4-GPU रन 133.5s में $10^{13}$ के लिए पूरा हुआ)।
मल्टी-GPU स्केलिंग (जब $N = 2 \times 10^{12}$ हो):
- 1 GPU: 80.87s
- 2 GPUs: 40.55s (99.7% पैरेलल एफिशिएंसी)
- 4 GPUs: 20.51s (98.6% पैरेलल एफिशिएंसी)
कम्युनिकेशन ओवरहेड:
- होस्ट-टू-डिवाइस ट्रांसफर: ~0.628 MB प्रति सेगमेंट (निरंतर)।
- डिवाइस-टू-होस्ट ट्रांसफर: ~4 bytes प्रति सेगमेंट (स्केलर)।
- पूरे रन के लिए कुल D2H ट्रैफिक: 20 KB।
थर्मल स्टेबिलिटी: प्रोफाइलिंग ने दिखाया कि लंबे सिंगल-GPU रन के दौरान भी न्यूनतम फ्रीक्वेंसी थ्रॉटलिंग (<1.0% कमी) हुई, और 4-GPU रन महत्वपूर्ण थर्मल संचय से बचने के लिए पर्याप्त तेजी से पूरे हो गए।

5. महत्व (Significance)

यह कार्य GPU पर कम्प्यूटेशनल नंबर थ्योरी सत्यापन में एक प्रतिमान परिवर्तन (paradigm shift) का प्रतिनिधित्व करता है:

आर्किटेक्चरल परिपक्वता: यह प्रदर्शित करता है कि GPUs जटिल सीव ऑपरेशंस के लिए पूरी तरह से आत्मनिर्भर हो सकते हैं, जिससे CPU ऑर्केस्ट्रेशन पर निर्भरता समाप्त हो जाती है जो पहले स्केलेबिलिटी को सीमित करती थी।
स्केलेबिलिटी: लॉक-फ्री डिज़ाइन यह सिद्ध करता है कि हेट्रोजेनियस GPU क्लस्टर्स इस प्रकार की समस्याओं के लिए लगभग रैखिक स्केलिंग (near-linear scaling) प्राप्त कर सकते हैं, जो कि PCIe लेटेंसी के कारण पहले असंभव था।
भविष्य की सीमा: $10^{13}$ तक मिनटों में सत्यापन करके (जो CPU क्लस्टरों के लिए वर्षों का काम है) और $1.84 \times 10^{19}$ की साउंडनेस सीलिंग स्थापित करके, यह फ्रेमवर्क एक नया बेंचमार्क सेट करता है।
विस्तार क्षमता: मॉड्यूलर डिज़ाइन (CLI --start फ्लैग) वितरित नोड्स में आसान वितरण की अनुमति देता है, और पेपर भविष्य के कार्यों के लिए स्पष्ट मार्ग बताता है, जैसे कि बिटवाइज़ बल्क-मार्किंग कर्नल्स और $2^{64}$ की सीमा को तोड़ने के लिए 256-बिट अंकगणित।

संक्षेप में, यह शोध पत्र सफलतापूर्वक गोल्डबैक वेरिफिकेशन को CPU-लिमिटेड, I/O-बाउंड कार्य से एक अत्यधिक कुशल, पूर्णतः GPU-रेसिडेंट कंप्यूटेशन में बदल देता है, जो भारी गति वृद्धि और लगभग पूर्ण पैरेलल एफिशिएंसी प्राप्त करता है।