2025-11-18T22:43:13.755250
Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
Mukunoki, Ozaki
To obtain accurate results in numerical computation, high-precision arithmetic is a straightforward approach. However, most processors lack hardware support for floating-point formats beyond double precision (FP64). Double-word arithmetic (Dekker 1971) extends precision by using standard floating-point operations to represent numbers with twice the mantissa length. Building on this concept, various multi-word arithmetic methods have been proposed to further increase precision by combining additional words. Simplified variants, known as quasi algorithms, have also been introduced, which trade a certain loss of accuracy for reduced computational cost. In this study, we investigate the performance of quasi algorithms for double- and triple-word arithmetic in sparse iterative solvers based on the Conjugate Gradient method, and compare them with both non-quasi algorithms and standard FP64. We evaluate execution time on an x86 processor, the number of iterations to convergence, and solution accuracy. Although quasi algorithms require appropriate normalization to preserve accuracy - without it, convergence cannot be achieved - they can still reduce runtime when normalization is applied correctly, while maintaining accuracy comparable to full multi-word algorithms. In particular, quasi triple-word arithmetic can yield more accurate solutions without significantly increasing execution time relative to double-word arithmetic and its quasi variant. Furthermore, for certain problems, a reduction in iteration count contributes to additional speedup. Thus, quasi triple-word arithmetic can serve as a compelling alternative to conventional double-word arithmetic in sparse iterative solvers.
academicविरल पुनरावृत्तिमूलक समाधानकर्ता उच्च-परिशुद्धता अंकगणित के साथ अर्ध बहु-शब्द एल्गोरिदम का उपयोग करते हुए
मूल जानकारी
- पेपर ID: 2510.13536
- शीर्षक: विरल पुनरावृत्तिमूलक समाधानकर्ता उच्च-परिशुद्धता अंकगणित के साथ अर्ध बहु-शब्द एल्गोरिदम का उपयोग करते हुए
- लेखक: दैची मुकुनोकी (नागोया विश्वविद्यालय), कात्सुहिसा ओजाकी (शिबौरा प्रौद्योगिकी संस्थान)
- वर्गीकरण: cs.MS (गणितीय सॉफ्टवेयर)
- प्रकाशन समय: 15 अक्टूबर 2025 (arXiv प्रीप्रिंट)
- पेपर लिंक: https://arxiv.org/abs/2510.13536
सारांश
संख्यात्मक गणना में सटीक परिणाम प्राप्त करने के लिए, उच्च-परिशुद्धता अंकगणित एक सीधा तरीका है। हालांकि, अधिकांश प्रोसेसर द्वैत-परिशुद्धता (FP64) के बाहर अन्य फ्लोटिंग-पॉइंट प्रारूपों के लिए हार्डवेयर समर्थन की कमी रखते हैं। द्वि-शब्द अंकगणित (डेकर 1971) मानक फ्लोटिंग-पॉइंट संचालन का उपयोग करके दोगुनी मंटिसा लंबाई वाली संख्याओं का प्रतिनिधित्व करके परिशुद्धता का विस्तार करता है। इस अवधारणा के आधार पर, विभिन्न बहु-शब्द अंकगणित विधियां प्रस्तावित की गई हैं, जो अतिरिक्त शब्दों को संयोजित करके परिशुद्धता को और बढ़ाती हैं। सरलीकृत रूपांतर, अर्थात् अर्ध-एल्गोरिदम, भी पेश किए गए हैं, जो कुछ परिशुद्धता हानि के बदले में कम्प्यूटेशनल लागत में कमी प्रदान करते हैं। यह अनुसंधान संयुग्म प्रवणता विधि पर आधारित विरल पुनरावृत्तिमूलक समाधानकर्ताओं में द्वि-शब्द और त्रि-शब्द अंकगणित के अर्ध-एल्गोरिदम के प्रदर्शन की जांच करता है, और इसकी तुलना गैर-अर्ध-एल्गोरिदम और मानक FP64 से करता है।
अनुसंधान पृष्ठभूमि और प्रेरणा
मूल समस्याएं
- हार्डवेयर सीमा समस्या: अधिकांश प्रोसेसर द्वैत-परिशुद्धता (FP64) के बाहर अन्य फ्लोटिंग-पॉइंट प्रारूपों के लिए हार्डवेयर समर्थन की कमी रखते हैं, जो उच्च-परिशुद्धता संख्यात्मक गणना के कार्यान्वयन को सीमित करता है
- विरल पुनरावृत्तिमूलक समाधानकर्ताओं की परिशुद्धता आवश्यकता: बड़ी विरल रैखिक प्रणालियों को हल करते समय, राउंडिंग त्रुटि अभिसरण के लिए आवश्यक पुनरावृत्तियों की संख्या को बढ़ाती है, जो समाधान की परिशुद्धता और दक्षता को प्रभावित करती है
- प्रदर्शन और परिशुद्धता का संतुलन: पारंपरिक बहु-शब्द अंकगणित विधियां हालांकि परिशुद्धता में सुधार कर सकती हैं, लेकिन कम्प्यूटेशनल ओवरहेड अधिक है
अनुसंधान का महत्व
- विरल पुनरावृत्तिमूलक समाधानकर्ता वैज्ञानिक गणना और इंजीनियरिंग अनुप्रयोगों में व्यापक रूप से उपयोग किए जाते हैं
- उच्च-परिशुद्धता अंकगणित अभिसरण को सुधार सकता है, पुनरावृत्तियों की संख्या को कम कर सकता है
- मेमोरी-सीमित अनुप्रयोगों में, बहु-शब्द अंकगणित का अतिरिक्त ओवरहेड मेमोरी विलंबता द्वारा छिपाया जा सकता है
मौजूदा विधियों की सीमाएं
- पारंपरिक बहु-शब्द अंकगणित (जैसे DW, TW) उच्च कम्प्यूटेशनल लागत है
- अर्ध-एल्गोरिदम हालांकि कम्प्यूटेशनल लागत को कम करते हैं, लेकिन परिशुद्धता हानि का कारण बन सकते हैं
- पुनरावृत्तिमूलक समाधानकर्ताओं में अर्ध-एल्गोरिदम के प्रदर्शन का व्यवस्थित मूल्यांकन की कमी है
मूल योगदान
- अर्ध-एल्गोरिदम प्रदर्शन का व्यवस्थित मूल्यांकन: विरल पुनरावृत्तिमूलक समाधानकर्ताओं में QDW और QTW एल्गोरिदम के प्रदर्शन का पहली बार व्यवस्थित मूल्यांकन
- सामान्यीकरण की महत्वपूर्ण भूमिका की खोज: अर्ध-एल्गोरिदम अभिसरण के लिए उचित सामान्यीकरण के महत्व को प्रमाणित करता है
- QTW को प्रभावी विकल्प के रूप में प्रस्तावित करना: प्रमाणित करता है कि अर्ध-त्रि-शब्द अंकगणित (QTW) पारंपरिक द्वि-शब्द अंकगणित का प्रभावी विकल्प हो सकता है
- व्यापक प्रदर्शन विश्लेषण: निष्पादन समय, पुनरावृत्ति संख्या और समाधान परिशुद्धता के तीन आयामों से व्यापक मूल्यांकन
विधि विवरण
कार्य परिभाषा
सममित सकारात्मक-निश्चित रैखिक प्रणाली Ax = b को हल करना, जहां:
- A एक n×n सममित सकारात्मक-निश्चित विरल मैट्रिक्स है
- b दाहिनी ओर का वेक्टर है
- x हल किया जाने वाला वेक्टर है
संयुग्म प्रवणता (CG) विधि का उपयोग करके पुनरावृत्तिमूलक समाधान के लिए, विभिन्न परिशुद्धता अंकगणित के प्रदर्शन का मूल्यांकन करें।
बहु-शब्द अंकगणित आर्किटेक्चर
मूल एल्गोरिदम
त्रुटि-मुक्त परिवर्तन एल्गोरिदम:
TwoSum(a,b): a+b को फ्लोटिंग-पॉइंट परिणाम x और राउंडिंग त्रुटि y में विघटित करता हैQuickTwoSum(a,b): TwoSum का कुशल रूपांतर, |a|≥|b| की आवश्यकता हैTwoProdFMA(a,b): FMA संचालन का उपयोग करके a×b को परिणाम और त्रुटि में विघटित करता है
द्वि-शब्द अंकगणित (DW)
DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- संचालन: 11 FP64 संचालन
- सामान्यीकरण चरण (QuickTwoSum) सहित
DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)
- संचालन: 7 FP64 संचालन
- सामान्यीकरण चरण सहित
अर्ध द्वि-शब्द अंकगणित (QDW)
- सामान्यीकरण चरण को छोड़ता है, उच्च और निम्न शब्दों के ओवरलैप की अनुमति देता है
- QDWadd: 8 संचालन, QDWmul: 4 संचालन
- कम्प्यूटेशनल लागत में महत्वपूर्ण कमी
अर्ध त्रि-शब्द अंकगणित (QTW)
QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- संचालन: 21 FP64 संचालन
- fl(c1+c2)=c1 और fl(c2+c3)=c2 को लागू नहीं करता है
QTWmul: [c1,c2,c3] = QTWmul(a1,a2,a3,b1,b2,b3)
- संचालन: 24 FP64 संचालन
तकनीकी नवाचार बिंदु
- SIMD वेक्टरकरण अनुकूलन:
- AVX2 और AVX-512 निर्देश सेट का उपयोग करके वेक्टरकरण
- QTW एल्गोरिदम शर्तीय शाखाओं को समाप्त करता है, वेक्टरकरण के लिए अधिक उपयुक्त है
- सामान्यीकरण रणनीति:
- CG विधि के अवशिष्ट वेक्टर अपडेट के बाद सामान्यीकरण
- त्रि-शब्द अंकगणित में बिट ओवरलैप को कम करने के लिए VecSum3 एल्गोरिदम का उपयोग
- मिश्रित-परिशुद्धता कार्यान्वयन:
- गुणांक मैट्रिक्स A और दाहिनी ओर का वेक्टर b FP64 में संग्रहीत है
- आंतरिक गणना संबंधित बहु-शब्द अंकगणित का उपयोग करती है
प्रयोगात्मक सेटअप
डेटासेट
SuiteSparse मैट्रिक्स संग्रह से 8 सममित सकारात्मक-निश्चित मैट्रिक्स का उपयोग:
| मैट्रिक्स | आयाम n | गैर-शून्य तत्व nnz | अनुप्रयोग क्षेत्र |
|---|---|---|---|
| Hook_1498 | 1,498,023 | 60,917,445 | संरचनात्मक समस्या |
| bone010 | 986,703 | 47,851,783 | मॉडल कमी |
| nd24k | 72,000 | 28,715,634 | 2D/3D समस्या |
| crankseg_2 | 63,838 | 14,148,858 | संरचनात्मक समस्या |
मूल्यांकन संकेतक
- निष्पादन समय: प्रति पुनरावृत्ति समय और कुल अभिसरण समय
- पुनरावृत्ति संख्या: अभिसरण तक पहुंचने के लिए आवश्यक पुनरावृत्तियों की संख्या
- समाधान परिशुद्धता: सापेक्ष त्रुटि मानदंड ||xk-x*||2/||x*||2
तुलना विधियां
- CG-FP64: मानक द्वैत-परिशुद्धता कार्यान्वयन
- CG-DW: द्वि-शब्द अंकगणित कार्यान्वयन
- CG-QDW: अर्ध द्वि-शब्द अंकगणित कार्यान्वयन
- CG-TW: त्रि-शब्द अंकगणित कार्यान्वयन
- CG-QTW: अर्ध त्रि-शब्द अंकगणित कार्यान्वयन
कार्यान्वयन विवरण
- हार्डवेयर प्लेटफॉर्म: Intel Xeon Gold 6230 CPU (20 कोर, 2.10-3.90 GHz)
- कंपाइलर: g++ 11.3.0, अनुकूलन विकल्प -O3 -march=native
- समानांतरकरण: OpenMP + SIMD वेक्टरकरण
- अभिसरण सहनशीलता: ε = 10^-16, 10^-24, 10^-32
प्रयोगात्मक परिणाम
मुख्य परिणाम
प्रदर्शन ओवरहेड विश्लेषण
FP64 के सापेक्ष निष्पादन समय ओवरहेड (100 पुनरावृत्तियां):
- CG-QDW: लगभग 1.3 गुना
- CG-DW: लगभग 2.1 गुना
- CG-QTW: लगभग 2.4 गुना
- CG-TW: 67 गुना तक
अभिसरण प्रदर्शन तुलना
ε=10^-16 अभिसरण सहनशीलता के तहत विशिष्ट परिणाम:
| मैट्रिक्स | FP64 समय(s)/पुनरावृत्ति | QDW समय(s)/पुनरावृत्ति | QTW समय(s)/पुनरावृत्ति |
|---|---|---|---|
| bone010 | 170/21780 | 120/12547 | 150/11352 |
| pdb1HYS | 5.4/12807 | 3.4/6285 | 4.9/5346 |
मुख्य निष्कर्ष
- सामान्यीकरण की आवश्यकता:
- सामान्यीकरण के बिना, अर्ध-एल्गोरिदम अभिसरण नहीं कर सकते
- अवशिष्ट वेक्टर अपडेट के बाद सामान्यीकरण अभिसरण सुनिश्चित कर सकता है
- QTW के लाभ:
- TW की तुलना में कम्प्यूटेशनल ओवरहेड में महत्वपूर्ण कमी
- TW के समान परिशुद्धता प्राप्त करता है
- SIMD वेक्टरकरण का समर्थन करता है, बेहतर प्रदर्शन
- पुनरावृत्ति संख्या में कमी के लाभ:
- उच्च-परिशुद्धता अंकगणित पुनरावृत्तियों की संख्या को कम कर सकता है
- कुल निष्पादन समय FP64 कार्यान्वयन से कम हो सकता है
थ्रूपुट विश्लेषण
SpMV संचालन की थ्रूपुट (GB/s):
- FP64 और QDW: मेमोरी बैंडविड्थ सीमा के करीब (लगभग 90 GB/s)
- DW और QTW: SIMD अनुकूलन के बाद मेमोरी-सीमित तक पहुंचता है
- TW: शाखा प्रभाव के कारण, प्रदर्शन में महत्वपूर्ण कमी
संबंधित कार्य
बहु-शब्द अंकगणित विकास
- मूल सिद्धांत: डेकर (1971) की द्वि-शब्द अंकगणित
- विस्तार विधियां: त्रि-शब्द (TW), चतुर्थ-शब्द (QW) अंकगणित
- सरलीकृत रूपांतर: अर्ध-एल्गोरिदम (QDW, QTW, QQW)
उच्च-परिशुद्धता रैखिक बीजगणित पुस्तकालय
- QD पुस्तकालय: द्वि-शब्द और चतुर्थ-शब्द अंकगणित का Fortran/C++ कार्यान्वयन
- XBLAS: DW अंकगणित पर आधारित BLAS दिनचर्या
- MPLAPACK: उच्च-परिशुद्धता BLAS और LAPACK
विरल पुनरावृत्तिमूलक समाधानकर्ता अनुप्रयोग
- चतुर्थ-परिशुद्धता CG समाधानकर्ता का अनुसंधान
- मिश्रित-परिशुद्धता विधियां
- Ozaki योजना की सटीक विरल मैट्रिक्स-वेक्टर गुणन
निष्कर्ष और चर्चा
मुख्य निष्कर्ष
- अर्ध-एल्गोरिदम की व्यवहार्यता: उचित सामान्यीकरण के माध्यम से, अर्ध-एल्गोरिदम विरल पुनरावृत्तिमूलक समाधानकर्ताओं में प्रभावी रूप से लागू किए जा सकते हैं
- QTW के लाभ: अर्ध-त्रि-शब्द अंकगणित परिशुद्धता और प्रदर्शन का अच्छा संतुलन प्रदान करता है
- प्रदर्शन सुधार की क्षमता: कुछ समस्याओं पर, पुनरावृत्ति संख्या में कमी अतिरिक्त त्वरण प्रभाव ला सकती है
सीमाएं
- सामान्यीकरण ओवरहेड: परिशुद्धता और निष्पादन समय के बीच संतुलन की आवश्यकता है
- समस्या निर्भरता: प्रदर्शन सुधार प्रभाव विशिष्ट समस्या विशेषताओं पर निर्भर है
- मूल्यांकन सीमा: केवल मूल CG विधि का मूल्यांकन किया गया है, पूर्व-शर्त तकनीकें शामिल नहीं हैं
भविष्य की दिशाएं
- सामान्यीकरण रणनीति अनुकूलन: परिशुद्धता पर अधिक बार सामान्यीकरण के प्रभाव का अनुसंधान
- अन्य पुनरावृत्तिमूलक विधियों में विस्तार: अन्य समाधानकर्ताओं में अनुप्रयोग का मूल्यांकन
- वितरित पर्यावरण अनुप्रयोग: संचार विलंबता प्रभावशाली वातावरण में संभावनाएं
- निम्न-परिशुद्धता प्रारूप कार्यान्वयन: AI प्रोसेसर पर FP16/FP32 का उपयोग करके बहु-शब्द अंकगणित
गहन मूल्यांकन
शक्तियां
- व्यवस्थित अनुसंधान: पुनरावृत्तिमूलक समाधानकर्ताओं में अर्ध-एल्गोरिदम के प्रदर्शन का पहली बार व्यवस्थित मूल्यांकन
- उच्च व्यावहारिक मूल्य: QTW एल्गोरिदम उच्च-परिशुद्धता गणना के लिए एक व्यावहारिक समाधान प्रदान करता है
- पर्याप्त प्रयोग: समय, परिशुद्धता, अभिसरण के कई आयामों से व्यापक मूल्यांकन
- तकनीकी नवाचार: SIMD अनुकूलन और सामान्यीकरण रणनीति का उचित डिजाइन
कमियां
- सैद्धांतिक विश्लेषण अपर्याप्त: अर्ध-एल्गोरिदम त्रुटि संचय का सैद्धांतिक विश्लेषण की कमी
- मूल्यांकन सीमा: केवल CG विधि का मूल्यांकन, अन्य पुनरावृत्तिमूलक विधियों का सत्यापन की कमी
- सामान्यीकरण रणनीति एकल: केवल एक सामान्यीकरण स्थान और आवृत्ति का प्रयास
प्रभाव
- शैक्षणिक योगदान: उच्च-परिशुद्धता संख्यात्मक गणना क्षेत्र के लिए नए एल्गोरिदम विकल्प प्रदान करता है
- व्यावहारिक मूल्य: QTW एल्गोरिदम वास्तविक वैज्ञानिक गणना समस्याओं में सीधे लागू किया जा सकता है
- पुनरुत्पादनीयता: कार्यान्वयन विवरण पर्याप्त रूप से वर्णित हैं, पुनरुत्पादन में सुविधा
लागू परिदृश्य
- वैज्ञानिक गणना: उच्च-परिशुद्धता समाधान की आवश्यकता वाली बड़ी विरल रैखिक प्रणालियां
- इंजीनियरिंग सिमुलेशन: संरचनात्मक विश्लेषण, विद्युत चुंबकीय क्षेत्र गणना आदि अनुप्रयोग
- संसाधन-सीमित वातावरण: हार्डवेयर चतुर्थ-परिशुद्धता समर्थन की कमी वाली प्रणालियां
संदर्भ
यह पेपर 29 संबंधित संदर्भों का हवाला देता है, जो बहु-शब्द अंकगणित सिद्धांत, उच्च-परिशुद्धता रैखिक बीजगणित पुस्तकालय, विरल पुनरावृत्तिमूलक समाधानकर्ता आदि मुख्य क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करता है, जो अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करता है।