बड़े मैट्रिक्स इनवर्जन

Question

मैं 1000 x 1000 के सामान्य आकार, एक बड़े मैट्रिक्स के विपरीत को ले रहा हूं, लेकिन कभी-कभी 100000 x 100000 (जो वर्तमान में समय और स्मृति के कारण विफल रहता है) से अधिक है। मुझे पता है कि सामान्य भावना 'उलटा नहीं लेती है, इसे करने का कोई और तरीका ढूंढती है', लेकिन इस समय यह संभव नहीं है। इसका कारण सॉफ़्टवेयर के उपयोग के कारण है जो पहले से ही बनाई गई है जो मैट्रिक्स उलटा पाने की अपेक्षा करता है। (ध्यान दें: मैं इसे बदलने के तरीकों की तलाश में हूं, लेकिन इसमें काफी समय लगेगा)

फिलहाल हम संख्यात्मक रिकॉपी से एक LU अपघटन विधि का उपयोग कर रहे हैं, और मैं वर्तमान में ईजिन लाइब्रेरी का परीक्षण करने की प्रक्रिया में हूं । ईजिन पुस्तकालय अधिक स्थिर और थोड़ा तेज़ प्रतीत होता है, लेकिन मैं अभी भी सटीकता के लिए परीक्षण चरण में हूं। मैंने एटलस और लैपैक जैसे अन्य पुस्तकालयों पर एक त्वरित नज़र डाली है लेकिन अभी तक इनके साथ कोई महत्वपूर्ण परीक्षण नहीं किया है।

ऐसा लगता है कि ईजिन पुस्तकालय उलटा गणना करने के लिए समवर्ती तरीकों का उपयोग नहीं करता है (हालांकि उलटा के LU कारक भाग के लिए करता है) और जहां तक ​​मैं एटलस और लैपैक को बता सकता हूं, इस सीमा में समान है। (मैं वर्तमान में ओपन के साथ ओपनएमपी के बिना गति अंतर का परीक्षण कर रहा हूं।)

पहला सवाल यह है कि कोई भी समझा सकता है कि समांतरता द्वारा मैट्रिक्स उलटा को अनुकूलित करना कैसे संभव होगा। मुझे एक लेख here मिला जो मैट्रिक्स उलटा समांतर एल्गोरिदम के बारे में बात करता है, लेकिन मुझे समझ में नहीं आया। ऐसा लगता है कि this लेख किसी अन्य विधि के बारे में बात करता है? मुझे यह भी यकीन नहीं है कि स्कैलापैक या पीईटीएससी उपयोगी हैं या नहीं?

दूसरा प्रश्न, मैंने प्रदर्शन बढ़ाने के लिए जीपीयू का उपयोग करने के लिए this लेख पढ़ा है, लेकिन मैंने कभी GPUs के लिए कोड नहीं किया है और इसलिए पता नहीं है कि क्या व्यक्त करने की कोशिश कर रहा है, लेकिन नीचे चार्ट चार्ट को खतरनाक लग रहा था। यह कैसे संभव है, और अगर यह सच होना है तो इस तरह कुछ लागू करने के बारे में कहां जाना है।

मैं भी this लेख मिला, फिर भी समय को समझने के लिए यह माध्यम से पढ़ने के लिए पड़ा है, लेकिन यह आशाजनक लगता है, के रूप में स्मृति हमारे सॉफ्टवेयर के साथ एक वर्तमान मुद्दा है।

इन लेखों या सामान्य रूप से समस्याओं के बारे में कोई भी जानकारी बहुत मददगार होगी। और फिर मैं क्षमा चाहता हूं कि यह प्रश्न अस्पष्ट लगता है, यदि आवश्यक हो तो मैं और अधिक विस्तार करने की कोशिश करूंगा।

Answer 1

पहला सवाल यह है कि कोई भी समझा सकता है कि समांतरता द्वारा मैट्रिक्स उलटा को अनुकूलित करना कैसे संभव होगा।

मुझे लगता है कि यह, और रैखिक बीजगणित में संबंधित विषय समानांतर कंप्यूटिंग में सबसे अधिक अध्ययन किए गए विषयों में से एक है। यदि आप पढ़ना शुरू करने के लिए कहीं और देख रहे हैं, तो अच्छी तरह से पुराने Golub and Van Loan विषय पर एक अध्याय है। स्केलपैक और पेट्सक उपयोगी होने की संभावना है, निश्चित रूप से पूर्व, शायद बाद वाले। बेशक, वे दोनों एमपीआई पर निर्भर करते हैं लेकिन इस तरह के क्षेत्र में इस तरह के लिए लिया जाता है।

दूसरा सवाल ...

उपयोग GPUs आप उन्हें मिल गया है और आप अपने GPUs द्वारा समर्थित प्रोग्रामिंग मॉडल में अपने कोड का अनुवाद करने में खर्च कर सकते हैं यदि। यदि आपने कभी GPU के लिए कोड नहीं किया है और कमोडिटी-प्रकार CPUs के क्लस्टर तक पहुंच प्राप्त की है तो आप उपन्यास तकनीक के साथ कुश्ती के मुकाबले क्लस्टर का उपयोग कर तेजी से तेज़ी से बढ़ेंगे।

अंतिम लेख के रूप में आप संदर्भित करते हैं, अब यह एक ऐसे क्षेत्र में 10 वर्ष का है जो बहुत तेज़ी से बदलता है (मैट्रिक्स उलटा के लिए जीपीयू का उपयोग करने पर 10 वर्षीय शोध पत्र खोजने का प्रयास करें)। मैं इसकी उत्कृष्टता या अन्य विशेषताओं पर टिप्पणी नहीं कर सकता, लेकिन आपके द्वारा बताए गए समस्या आकार में मुझे आधुनिक क्लस्टर की क्षमता के भीतर अच्छी तरह से होना चाहिए (पुराने शब्द का उपयोग करने के लिए) गणना। यदि आपकी matrices बहुत बड़ी हैं, तो वे भी स्पैस हैं?

अंत में, मैं अपने स्वयं के विकास के प्रयास के बजाय मौजूदा ऑफ-द-शेल्फ कोड का उपयोग करने के आपके स्पष्ट इरादे का दृढ़ समर्थन करता हूं।

Answer 2

100000 x 100000 डबल परिशुद्धता पर 80 जीबी है। आपको एक लाइब्रेरी की आवश्यकता है जो डिस्क पर मेमोरी-मैप किए गए मैट्रिक्स का समर्थन करता है। मैं एक विशेष पुस्तकालय की सिफारिश नहीं कर सकता और मुझे त्वरित Google खोजों के साथ कुछ भी नहीं मिला। लेकिन संख्यात्मक व्यंजनों से कोड निश्चित रूप से पर्याप्त नहीं होगा।

Answer 3

पहला सवाल के बारे में

(कैसे उलटा कंप्यूटिंग parallellize के लिए):

मैं कहाँ एक मान आप अपने मैट्रिक्स की एक LU अपघटन करने से उलटा परिकलित कर रहे हैं और उसके बाद हल करने के लिए एक * बी अपघटन का उपयोग कर = मैं आपका मूल मैट्रिक्स है, बी वह मैट्रिक्स है जिसे आप हल करते हैं, और मैं पहचान मैट्रिक्स हूं। फिर बी उलटा है।

अंतिम चरण समानांतर करना आसान है। कॉलम के साथ अपनी पहचान मैट्रिक्स को विभाजित करें। यदि आपके पास पीपीयू हैं और आपका मैट्रिक्स एन-बाय-एन है, तो प्रत्येक भाग में एन/पी कॉलम और एन पंक्तियां होती हैं। चलिए भागों I1, I2, आदि को कॉल करते हैं। प्रत्येक सीपीयू पर, फॉर्म ए * बी 1 = आई 1 की एक प्रणाली को हल करें, यह आपको बी 1, बी 2 इत्यादि देता है, और आप उन्हें बी बनाने के लिए जोड़ सकते हैं जो उलटा है ।

Answer 4

एक जीपीयू पर एक LU decomp एक CPU पर ~ 10x तेज हो सकता है। यद्यपि यह अब बदल रहा है, जीपीयू परंपरागत रूप से एकल परिशुद्धता अंकगणितीय के आसपास डिजाइन किया गया है, और इसलिए पुराने हार्डवेयर एकल परिशुद्धता अंकगणित पर डबल परिशुद्धता अंकगणित से अधिक तेज़ होता है। साथ ही, स्टोरेज आवश्यकताओं और प्रदर्शन को आपके मैट्रिक्स की संरचना से बहुत प्रभावित किया जाएगा। एक छेड़छाड़ 100,000 x 100,000 मैट्रिक्स LU decomp हल करने के लिए एक उचित समस्या है और अधिक स्मृति की आवश्यकता नहीं होगी।

जब तक आप एक विशेषज्ञ बनना नहीं चाहते हैं और हार्डवेयर अपडेट के लिए समय ट्यूनिंग के बहुत सारे खर्च करते हैं, तो मैं दृढ़ता से एक वाणिज्यिक पुस्तकालय का उपयोग करने की अनुशंसा करता हूं। मैं CULA tools का सुझाव दूंगा। उनके पास दोनों स्पैस और घने जीपीयू पुस्तकालय हैं और वास्तव में उनके free library एसजीईटीआरएफ प्रदान करते हैं - एक सटीक (घने) LU decomp routine। आपको अपने डबल परिशुद्धता पुस्तकालयों के लिए भुगतान करना होगा।

Answer 5

मुझे पता है कि यह पुरानी पोस्ट है - लेकिन वास्तव में - ओपनसीएल (आप अपने ग्राफिक्स कार्ड के आधार पर प्रासंगिक डाउनलोड करते हैं) + ओपनएमपी + वेक्टरेशन (उस क्रम में नहीं) जाने का तरीका है।

किसी भी तरह - मेरे लिए मैट्रिक्स के साथ मेरा अनुभव वास्तव में सिस्टम में और बाहर डबल डबल एरे की प्रतिलिपि बनाने के लिए ओवरहेड के साथ करना है और गणना के किसी भी प्रारंभ से पहले 0s के साथ मैट्रिक्स को पैड अप या प्रारंभ करना है - खासकर जब मैं काम कर रहा हूं एक्सेल उपयोग के लिए .xll बनाने के साथ।

मैं reprioritize करने के लिए शीर्ष थे, तो -

1. कोड (विजुअल स्टूडियो vectorize करने के लिए कोशिश 2012 और इंटेल सी ++ autovectorization है - मैं MinGW या जीसीसी बारे में निश्चित नहीं हूँ, लेकिन मुझे लगता है कि वहाँ के लिए झंडे हैं आपके प्रोसेसर के वेक्टर रजिस्टरों को पॉप्युलेट करने के लिए, सामान्य डेटा के बजाय सामान्य रजिस्टरों के बजाय उपयोग करने के लिए सही असेंबली कोड उत्पन्न करने के लिए आपके लिए लूप के लिए विश्लेषण करने के लिए संकलक। मुझे लगता है कि एक्सेल ऐसा कर रहा है क्योंकि जब मैंने MINVERSE() चलाते समय एक्सेल के धागे की निगरानी की थी , मुझे लगता है कि केवल 1 धागा का उपयोग किया जाता है। मुझे ज्यादा असेंबली भाषा नहीं पता - इसलिए मुझे नहीं पता कि मैन्युअल रूप से वेक्टर कैसे करें ... (अभी तक यह जानने के लिए समय नहीं है लेकिन sooooo इसे करना चाहते हैं!)
2. OpenMP (omp pragma) या एमपीआई या pthreads लाइब्रेरी (parallel_for) के साथ समानांतर - बहुत सरल - लेकिन ...यहां पकड़ है - मुझे एहसास है कि यदि आपकी मैट्रिक्स कक्षा पूरी तरह से पहले स्थान पर थ्रेड की गई है - तो मैट गुणा या उलटा जैसे ऑपरेशन को समानांतर करना स्क्रैप करने योग्य है - cuz समानांतर गति को खराब करने या प्रतिलिपि करने या केवल गैर- समांतर मैट्रिक्स कक्षा। लेकिन ... जहां समांतरता सहायता करता है - यदि आप अपनी खुद की मैट्रिक्स कक्षा तैयार कर रहे हैं और आप इसके कन्स्ट्रक्टर ऑपरेशन (0s आदि के साथ पैडिंग) को समानांतर करते हैं, तो LU (A^-1) = I की आपकी गणना भी तेज होगी। यह आपके ल्यू अपघटन को अनुकूलित करने के लिए भी गणितीय रूप से सरल है, और पहचान के विशेष मामले के लिए आपके आगे पिछड़े प्रतिस्थापन को भी अनुकूलित करता है। (मैं किसी भी पहचान मैट्रिक्स बनाने में समय बर्बाद नहीं करता - विश्लेषण करें कि आपका (पंक्ति = कोला) कहां है और 0 के साथ एक समारोह के साथ मूल्यांकन करें और शेष 0 के साथ मूल्यांकन करें।
3. एक बार यह समानांतर (बाहरी परतों पर) हो गया है - तत्व द्वारा तत्व की आवश्यकता वाले मैट्रिक्स परिचालनों को जीपीयू (एसएसएसएसएसएस) द्वारा गणना करने के लिए मैप किया जा सकता है - तत्वों की गणना करने के लिए सैकड़ों प्रोसेसर - इसे हराया! एटीआई की ओपनसीएल का उपयोग करते हुए अब एटीआई की वेबसाइट पर उपलब्ध नमूना मोंटे कार्लो कोड है - GeForce का उपयोग करने वाले किसी चीज़ को कोड पोर्ट करने के बारे में चिंता न करें - आपको बस इतना करना होगा।

2 के लिए

और 3 हालांकि - याद रखें कि ओवरहेड्स तो कोई मतलब नहीं जब तक आप संभाल रहे हैं * एफ * कश्मीर जी विशाल मैट्रिक्स खर्च कर रहे हैं - लेकिन मैं 100k^2 देखते हैं? वाह ...

जीन