2025-11-20T19:52:15.672703

A GPU-resident Memory-Aware Algorithm for Accelerating Bidiagonalization of Banded Matrices

Ringoot, Alomairy, Edelman
The reduction of a banded matrix to a bidiagonal form is a crucial step in the Singular Value Decomposition (SVD), a cornerstone of scientific computing and AI. Despite being a highly parallel algorithm, it was previously believed to be unsuitable for GPU computation because it is memory bandwidth-bound. Recent developments in GPU hardware, including larger L1 memory per Streaming Multiprocessor/Compute Unit, have changed that. We present the first GPU algorithm for reducing a banded matrix to bidiagonal form as part of the NextLA.jl open-source software package. Our algorithm is based on previous CPU-based multicore parallel cache-efficient bulge chasing algorithms and adapted to optimize for GPU throughput. We leverage Julia Language's Array abstractions and KernelAbstractions to implement a single hardware- and data precision-agnostic function on NVIDIA, AMD, Intel, and Apple Metal GPUs for half, single, and double precision, and examine performance optimization across hardware architectures and data precision. We also develop a hardware-aware performance model and identify key hyperparameters, such as inner tilewidth and block concurrency, that govern optimal GPU execution for bandwidth-bound workloads. We demonstrate highly parallel bandwidth-bound algorithm on the GPU can outperform CPU-based implementations: the GPU algorithm outperforms multithreaded CPU High-Performance libraries PLASMA and SLATE as of matrix size 1024 x 1024 and by a factor over 100 for matrices of 32k x 32k. In addition, the performance of the algorithm increases linearly with matrix bandwidth size, making faster reduction of larger matrix bandwidths now also possible. With this work, we break memory bandwidth barriers, as well as matrix bandwidth barriers, resulting in orders-of-magnitude faster algorithms for the reduction of banded matrices to bidiagonal form on the GPU.
academic

GPU-निवासी मेमोरी-जागरूक एल्गोरिदम बैंडेड मैट्रिसेस के द्विविकर्ण करण को त्वरित करने के लिए

मूल जानकारी

  • पेपर ID: 2510.12705
  • शीर्षक: A GPU-resident Memory-Aware Algorithm for Accelerating Bidiagonalization of Banded Matrices
  • लेखक: Evelyne Ringoot, Rabab Alomairy, Alan Edelman (MIT कंप्यूटर विज्ञान और AI प्रयोगशाला)
  • वर्गीकरण: cs.DC (वितरित, समानांतर और क्लस्टर कंप्यूटिंग), cs.MS (गणितीय सॉफ्टवेयर)
  • प्रकाशन समय: 14 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.12705

सारांश

यह पेपर पहला GPU-निवासी मेमोरी-जागरूक एल्गोरिदम प्रस्तुत करता है, जो बैंडेड मैट्रिसेस को द्विविकर्ण मैट्रिसेस में कम करने के लिए है, जो एकवचन मान विघटन (SVD) में एक महत्वपूर्ण चरण है। हालांकि यह एल्गोरिदम अत्यधिक समानांतर है, लेकिन इसकी मेमोरी बैंडविड्थ बाधा विशेषताओं के कारण पहले GPU कंप्यूटिंग के लिए अनुपयुक्त माना जाता था। GPU हार्डवेयर के विकास के साथ, विशेष रूप से प्रत्येक स्ट्रीम मल्टीप्रोसेसर/कंप्यूट यूनिट में बड़ी L1 मेमोरी, यह स्थिति बदल गई है। लेखकों ने पिछले CPU मल्टी-कोर समानांतर कैश-कुशल bulge-chasing एल्गोरिदम पर आधारित है और GPU थ्रूपुट के लिए अनुकूलित है। एल्गोरिदम NVIDIA, AMD, Intel और Apple Metal GPU पर हार्डवेयर और डेटा सटीकता-अज्ञेयवादी एकल फ़ंक्शन को लागू करता है, जो आधा-सटीकता, एकल-सटीकता और दोहरी-सटीकता कंप्यूटिंग का समर्थन करता है। प्रयोग दिखाते हैं कि GPU एल्गोरिदम 1024×1024 मैट्रिक्स आकार से शुरू होकर मल्टी-थ्रेडेड CPU उच्च-प्रदर्शन लाइब्रेरी PLASMA और SLATE को पार करता है, 32k×32k मैट्रिक्स पर 100 गुना से अधिक प्रदर्शन सुधार के साथ।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

एकवचन मान विघटन (SVD) वैज्ञानिक कंप्यूटिंग, मशीन लर्निंग और डेटा विश्लेषण में एक मौलिक संख्यात्मक उपकरण है, जो प्रमुख घटक विश्लेषण, अव्यक्त शब्दार्थ अनुक्रमण, निम्न-रैंक सन्निकटन और मैट्रिक्स पूर्णता जैसे अनुप्रयोगों में व्यापक रूप से उपयोग किया जाता है। आधुनिक बड़े पैमाने के हार्डवेयर पर SVD आमतौर पर तीन-चरण प्रक्रिया को अपनाता है:

  1. सघन मैट्रिक्स से बैंडेड मैट्रिक्स में कमी
  2. बैंडेड मैट्रिक्स से द्विविकर्ण मैट्रिक्स में कमी (bulge-chasing)
  3. द्विविकर्ण मैट्रिक्स से विकर्ण मैट्रिक्स में कमी

अनुसंधान प्रेरणा

हालांकि पहले और तीसरे चरण के GPU कार्यान्वयन का व्यापक रूप से अध्ययन किया गया है, दूसरा चरण आधुनिक GPU पर अभी भी पर्याप्त रूप से अन्वेषित नहीं है। Dongarra और अन्य ने 2014 में बताया कि "त्वरक bulge chasing जैसे मेमोरी-बाधित सूक्ष्म-दानेदार कंप्यूटिंग कार्यों को संभालने में खराब प्रदर्शन करते हैं, जो दूसरे चरण के GPU कार्यान्वयन की संभावित लाभ को सीमित करता है"।

तकनीकी अवसर

हाल के वर्षों में GPU आर्किटेक्चर की प्रगति, विशेष रूप से:

  • प्रत्येक स्ट्रीम मल्टीप्रोसेसर L1 कैश आकार का विस्तार
  • उच्च ऑन-चिप बैंडविड्थ
  • अधिक लचीली मेमोरी पहुंच पैटर्न
  • बेहतर कैश पुनः उपयोग और बड़ी मेमोरी पदानुक्रम

ये सुधार मेमोरी-कंप्यूटिंग संतुलन को महत्वपूर्ण रूप से बदलते हैं, मेमोरी-बाधित एल्गोरिदम के पुनः डिजाइन के लिए नए अवसर बनाते हैं।

मुख्य योगदान

  1. पहला GPU-निवासी मेमोरी-जागरूक bulge-chasing एल्गोरिदम: बैंडेड मैट्रिक्स से द्विविकर्ण मैट्रिक्स कमी के लिए पहला GPU-मूल एल्गोरिदम प्रस्तुत करता है, जो नवीनतम पीढ़ी के उच्च-प्रदर्शन GPU की उत्कृष्ट मेमोरी विशेषताओं का पूरी तरह से उपयोग करता है, अनुकूलित CPU कार्यान्वयन की तुलना में 10-100 गुना प्रदर्शन सुधार के साथ।
  2. बड़ी बैंडविड्थ मैट्रिसेस के लिए कैश-कुशल bulge-chasing रणनीति: क्रमिक बैंडविड्थ कमी की नई कैश-कुशल बड़ी बैंडविड्थ रणनीति के माध्यम से, GPU एल्गोरिदम पहले की तुलना में बड़ी बैंडविड्थ को संभाल सकता है, बड़े SVD में पहले और दूसरे चरण के बीच इष्टतम बैंडविड्थ व्यापार को बदलता है।
  3. ओपन-सोर्स हार्डवेयर-अज्ञेयवादी और डेटा-सटीकता-अज्ञेयवादी कार्यान्वयन: Julia भाषा अमूर्तता पर आधारित ओपन-सोर्स लाइब्रेरी, एकल फ़ंक्शन परिभाषा NVIDIA, AMD, Intel और Apple GPU पर एकल-सटीकता, आधा-सटीकता और दोहरी-सटीकता कंप्यूटिंग का समर्थन करती है।

विधि विवरण

कार्य परिभाषा

एक बैंडेड मैट्रिक्स A ∈ ℝⁿˣⁿ दिया गया है, बैंडविड्थ BW के साथ, लक्ष्य सही ऑर्थोगोनल परिवर्तन के माध्यम से इसे द्विविकर्ण मैट्रिक्स B में कम करना है, जैसे कि A = UBVᵀ, जहां U और V ऑर्थोगोनल मैट्रिसेस हैं।

एल्गोरिदम आर्किटेक्चर

मुख्य एल्गोरिदम प्रवाह

एल्गोरिदम 1: Householder वेक्टर का उपयोग करके बैंडेड मैट्रिक्स से द्विविकर्ण मैट्रिक्स कमी
इनपुट: बैंडविड्थ BW, आंतरिक टाइल चौड़ाई TW, मैट्रिक्स आकार n
1: बैंडविड्थ कमी के लिए i = (BW-1)/TW → 1 do
2:   लक्ष्य बैंडविड्थ TBW = 1 + i·TW  
3:   समानांतर के लिए: प्रत्येक पंक्ति R = 1→n do
4:     पंक्ति bulge k = R
5:     प्रत्येक पंक्ति bulge के लिए: j = 0, j+=1 do
6:       यदि 3(R-1) < j और k ≤ n तो
7:         TW तत्वों को समाप्त करने के लिए k पंक्ति के HH वेक्टर की गणना करें और नीचे की पंक्तियों पर लागू करें
8:         सबसे बाएं उत्पन्न स्तंभ bulge के HH वेक्टर की गणना करें और दाईं ओर के स्तंभों पर लागू करें
9:         k मान को अपडेट करें
10:      अंत यदि
11:    अंत के लिए
12:  अंत के लिए
13: अंत के लिए

मेमोरी-जागरूक GPU कर्नेल कार्यान्वयन

एल्गोरिदम 2: मेमोरी-जागरूक GPU कर्नेल, प्रति ब्लॉक TPB थ्रेड्स के साथ
1: थ्रेड मेमोरी: Ai (TW+1)
2: ब्लॉक मेमोरी: X (TW+1)  
3: ब्लॉक के भीतर सभी थ्रेड्स सहयोग: X ← A[k,..]
4: थ्रेड्स को सिंक्रोनाइज़ करें
5: ब्लॉक के भीतर सभी थ्रेड्स सहयोग: HH(X)
6: ब्लॉक के भीतर सभी थ्रेड्स सहयोग: A[k,..]← X
7: थ्रेड्स को सिंक्रोनाइज़ करें
8: l के लिए: 0→(CBW + TW)/TPB - 1 do
9:   थ्रेड i: पंक्ति r = k + l·CPB + i की गणना करें
10:  Ai ← A[r, ...]
11:  HH(X, Ai)  
12:  A[r, ...]← Ai
13: अंत के लिए

तकनीकी नवाचार बिंदु

1. बैंडविड्थ खंडन रणनीति

मैट्रिक्स को बैंडविड्थ टाइलों में विभाजित करता है, क्रमिक बैंडविड्थ ब्लॉक द्वारा कमी को निष्पादित करता है, पूरी बैंडविड्थ को एक बार में कम करने के बजाय। यह खंडन रणनीति प्राप्त करती है:

  • बेहतर कैश पुनः उपयोग
  • सुधारी गई मेमोरी स्थानीयता
  • कम सिंक्रोनाइज़ेशन ओवरहेड

2. नियंत्रित ब्लॉक शेड्यूलिंग

Max blocks पैरामीटर को प्रस्तुत करता है जो प्रत्येक GPU निष्पादन इकाई पर समवर्ती थ्रेड ब्लॉक की संख्या को सीमित करता है। जब एल्गोरिदम द्वारा आवश्यक bulge-chasing ब्लॉक संख्या सीमा से अधिक हो, तो सॉफ्टवेयर-स्तर लूप अनरोलिंग को अपनाता है, एकल ब्लॉक को कई कार्य दिए जाते हैं और एक ही कर्नेल लॉन्च में क्रमिक रूप से निष्पादित होते हैं।

3. तीन-चक्र अलगाव रणनीति

सही होना सुनिश्चित करने और समानांतरता को सक्षम करने के लिए, एल्गोरिदम क्रमिक पंक्तियों की स्कैनिंग के बीच तीन-चक्र अलगाव को लागू करता है। अर्थात्, प्रत्येक तीन पंक्ति bulge पूर्ण होने के बाद, अगली पंक्ति डेटा पहुंच को ओवरलैप किए बिना स्कैन करना शुरू कर सकती है।

प्रायोगिक सेटअप

हार्डवेयर वातावरण

  • CPU: Intel Xeon Platinum 8462Y+ 32-कोर 64-थ्रेड
  • GPU: NVIDIA A100/H100/RTX4060, AMD MI250X/MI300X, Intel PVC 1100, Apple M1 सहित

तुलना बेंचमार्क

  • PLASMA (v25.5.27): समानांतर रैखिक बीजगणित सॉफ्टवेयर पैकेज
  • SLATE (v2024.10.29): स्केलेबल रैखिक बीजगणित लाइब्रेरी
  • CUBLAS geam: मेमोरी बैंडविड्थ संदर्भ के रूप में मैट्रिक्स जोड़ कर्नेल

मूल्यांकन मेट्रिक्स

  • रन टाइम और त्वरण अनुपात
  • मेमोरी थ्रूपुट (DRAM, L1, L2)
  • संख्यात्मक सटीकता (सापेक्ष त्रुटि)
  • हार्डवेयर संसाधन उपयोग दर

परीक्षण कॉन्फ़िगरेशन

  • मैट्रिक्स आकार: 1024×1024 से 65k×65k
  • बैंडविड्थ श्रेणी: 32 से 512
  • डेटा सटीकता: FP16, FP32, FP64

प्रायोगिक परिणाम

मुख्य प्रदर्शन परिणाम

GPU बनाम CPU लाइब्रेरी प्रदर्शन तुलना

  • छोटी बैंडविड्थ (32): GPU कार्यान्वयन PLASMA की तुलना में 100-1000 गुना तेज़, SLATE की तुलना में 10-300 गुना तेज़
  • बड़ी बैंडविड्थ (512): GPU संस्करण SLATE की तुलना में 2-9 गुना तेज़, PLASMA की तुलना में 0.9-6 गुना तेज़
  • मैट्रिक्स आकार प्रभाव: GPU प्रदर्शन मैट्रिक्स आकार के साथ CPU कार्यान्वयन की तुलना में तेजी से बढ़ता है

क्रॉस-हार्डवेयर प्रदर्शन

  • NVIDIA H100: बेंचमार्क प्रदर्शन
  • AMD MI300X: लगभग 1.5-2 गुना प्रदर्शन में कमी
  • Intel PVC: लगभग 20 गुना प्रदर्शन में कमी (बड़े कैश के बावजूद)
  • Apple M1: उपभोक्ता-स्तर GPU में अच्छा प्रदर्शन

हाइपरपैरामीटर ट्यूनिंग परिणाम

मुख्य निष्कर्ष:

  1. आंतरिक टाइल चौड़ाई सबसे महत्वपूर्ण प्रदर्शन कारक है
    • FP32 इष्टतम मान: 32 (128-बाइट कैश लाइन के अनुरूप)
    • FP64 इष्टतम मान: 16 (128-बाइट कैश लाइन के अनुरूप)
  2. पैरामीटर महत्व बैंडविड्थ के साथ भिन्न होता है:
    • बैंडविड्थ 32: अधिकतम ब्लॉक संख्या अधिक महत्वपूर्ण
    • बैंडविड्थ 128: प्रति ब्लॉक थ्रेड संख्या अधिक महत्वपूर्ण

संख्यात्मक सटीकता विश्लेषण

  • FP64: त्रुटि मशीन सटीकता के करीब
  • FP32: अनुमानित आकार-निर्भर त्रुटि वृद्धि
  • FP16: 16k×16k मैट्रिक्स के भीतर स्वीकार्य सटीकता बनाए रखता है

हार्डवेयर विकास प्रभाव

  • MI300X MI250X की तुलना में महत्वपूर्ण सुधार (L1 कैश दोगुना, एकीकृत L2.5 स्तर जोड़ा गया)
  • H100 A100 की तुलना में निरंतर बेहतर (L1 कैश 33% वृद्धि, L2 25% वृद्धि)

संबंधित कार्य

SVD समाधानकर्ता विकास

  • CPU कार्यान्वयन: PLASMA, SBR, FLAME, ELPA, LAPACK आदि ब्लॉक Householder परिवर्तन और bulge-chasing एल्गोरिदम पर ध्यान केंद्रित करते हैं
  • GPU कार्यान्वयन: मुख्य रूप से पहले चरण (सघन से बैंडेड) या पूर्ण एक-चरण SVD पर केंद्रित, अनियमित मेमोरी पहुंच से बचते हैं

विशेषमान समाधानकर्ता तुलना

SVD समाधानकर्ताओं के विपरीत, सममित बैंडेड विशेषमान समस्या के द्वि-चरण समाधानकर्ता मिश्रित CPU-GPU सिस्टम पर बड़े पैमाने पर काम करते हैं, लेकिन गैर-सममित बैंडेड से द्विविकर्ण कमी अनुसंधान पिछड़ा है।

Bulge-chasing एल्गोरिदम

मूल रूप से एक समानांतर एल्गोरिदम के रूप में प्रस्तावित, लेकिन CPU पर द्विविकर्ण मामले का अनुसंधान अत्यंत दुर्लभ है। इसके विपरीत, सममित बैंडेड से त्रि-विकर्ण और ऊपरी Hessenberg रूप के bulge-chasing अनुसंधान अधिक व्यापक हैं।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. मेमोरी बैंडविड्थ बाधा को तोड़ना: साबित करता है कि मेमोरी-बाधित रैखिक बीजगणित एल्गोरिदम आधुनिक GPU पर न केवल व्यावहारिक हैं, बल्कि CPU प्रदर्शन को महत्वपूर्ण रूप से पार कर सकते हैं
  2. हार्डवेयर विशेषताओं का महत्व: L1/L2 कैश विलंबता आकार से अधिक महत्वपूर्ण है, कम विलंबता तेज़ मेमोरी पहुंच के महत्व पर जोर देता है
  3. एल्गोरिदम डिजाइन सिद्धांत: इष्टतम प्रदर्शन सिद्धांतपूर्ण एल्गोरिदम डिजाइन, कैश-जागरूक पैरामीटरकरण और पोर्टेबल कंपाइलर बुनियादी ढांचे से आता है

सीमाएं

  1. GPU व्यस्तता मॉडल: एल्गोरिदम प्रारंभिक चरण में GPU ब्लॉक संख्या उपलब्ध निष्पादन इकाइयों से काफी कम है, GPU संसाधनों का पूरी तरह से उपयोग करने के लिए पर्याप्त बड़े मैट्रिक्स की आवश्यकता है
  2. रजिस्टर ओवरफ्लो: उच्च आंतरिक टाइल चौड़ाई रजिस्टर ओवरफ्लो का कारण बन सकती है, प्रदर्शन को प्रभावित करती है
  3. हार्डवेयर निर्भरता: विभिन्न GPU आर्किटेक्चर के बीच प्रदर्शन में महत्वपूर्ण अंतर, हार्डवेयर-विशिष्ट ट्यूनिंग की आवश्यकता है

भविष्य की दिशाएं

  1. आर्किटेक्चर अनुकूलन: CUDA 13.0 जैसी नई विशेषताओं का उपयोग करना जैसे साझा मेमोरी रजिस्टर ओवरफ्लो
  2. एल्गोरिदम विस्तार: बड़ी बैंडविड्थ प्रसंस्करण रणनीतियों की खोज करना
  3. पूर्ण SVD पाइपलाइन: पूरी तरह से GPU-निवासी SVD पाइपलाइन का निर्माण

गहन मूल्यांकन

शक्तियां

  1. अग्रणी योगदान: पहली बार GPU-निवासी बैंडेड से द्विविकर्ण कमी एल्गोरिदम को लागू करता है, महत्वपूर्ण तकनीकी अंतराल को भरता है
  2. उच्च व्यावहारिक मूल्य: महत्वपूर्ण प्रदर्शन सुधार (10-1000 गुना) इसे महत्वपूर्ण अनुप्रयोग मूल्य देता है
  3. तकनीकी नवाचार: बुद्धिमान बैंडविड्थ खंडन और मेमोरी-जागरूक डिजाइन GPU आर्किटेक्चर विशेषताओं के अनुकूल हैं
  4. मजबूत पोर्टेबिलिटी: Julia-आधारित एकल-स्रोत कार्यान्वयन कई विक्रेता GPU और कई सटीकता का समर्थन करता है

कमियां

  1. अपर्याप्त सैद्धांतिक विश्लेषण: एल्गोरिदम जटिलता के सैद्धांतिक विश्लेषण और अभिसरण प्रमाण की कमी
  2. सीमित परीक्षण श्रेणी: मुख्य रूप से सिंथेटिक मैट्रिसेस पर परीक्षण, वास्तविक अनुप्रयोग परिदृश्य सत्यापन की कमी
  3. जटिल पैरामीटर ट्यूनिंग: विभिन्न हार्डवेयर के लिए जटिल हाइपरपैरामीटर ट्यूनिंग की आवश्यकता

प्रभाव

  1. शैक्षणिक महत्व: GPU पर मेमोरी-बाधित एल्गोरिदम के प्रदर्शन सीमा को पुनः परिभाषित करता है
  2. व्यावहारिक मूल्य: बड़े पैमाने पर वैज्ञानिक कंप्यूटिंग और AI अनुप्रयोगों के लिए महत्वपूर्ण तकनीकी समर्थन प्रदान करता है
  3. पारिस्थितिकी योगदान: ओपन-सोर्स कार्यान्वयन क्रॉस-प्लेटफॉर्म GPU रैखिक बीजगणित पारिस्थितिकी विकास को बढ़ावा देता है

प्रयोज्य परिदृश्य

  • बड़े पैमाने पर मैट्रिक्स SVD गणना
  • वैज्ञानिक कंप्यूटिंग और इंजीनियरिंग सिमुलेशन
  • मशीन लर्निंग में आयाम में कमी और विशेषता निष्कर्षण
  • उच्च-प्रदर्शन रैखिक बीजगणित की आवश्यकता वाले GPU अनुप्रयोग

संदर्भ

पेपर 86 संबंधित संदर्भों का हवाला देता है, जो GPU कंप्यूटिंग, रैखिक बीजगणित एल्गोरिदम, Julia भाषा पारिस्थितिकी और अन्य क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करता है, अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करता है।