दिलचस्प पोस्ट
क्या कोई क्रॉस-डोमेन iframe ऊँचाई ऑटो-रीसाइज़र है जो काम करता है? DllMain में एक धागा बनाना है? सी ++ में सरणियों या std :: vectors का उपयोग करना, प्रदर्शन अंतर क्या है? Form2 से form2 में टेक्स्टबॉक्स को अपडेट कैसे करें? संदर्भ पैरामीटर के साथ varargs का उपयोग कर वहाँ gotchas हैं संपत्ति घोषणापत्र और स्वचालित बैकिंग संग्रहण आवंटन मैं SSL फ़ॉलबैक कैसे अक्षम कर सकता हूँ और .NET में आउटबाउंड कनेक्शन के लिए केवल TLS का उपयोग कैसे करूं? (पूडल शमन) पूर्णांक के लिए कारक कन्वर्ट Linq कास्ट <T> ऑपरेशन क्यों विफल हो जाता है जब मेरे पास एक अंतर्निहित डाली परिभाषित है? सरल सी scanf काम नहीं करता है? सीएसएस या जावास्क्रिप्ट का उपयोग कर वेबपेज में कर्सर छिपाना संभव है? दो स्मार्ट फोन से जुड़े होने पर एडीबी को दो समान सीरियल नंबर मिलते हैं ASP.NET MVC नियंत्रक कार्य जो JSON या आंशिक HTML वापस आते हैं फ़ाइलों को ज़िप / अनझिप करने के लिए एक अच्छा जावा लाइब्रेरी क्या है? टेक्स्टव्यू में एक शब्द का पाठ रंग बदलें

मैट्रिक्स गुणा में MATLAB इतनी तेज़ी क्यों है?

मैं सीयूडीए, सी ++, सी # और जावा के साथ कुछ मानदंड बना रहा हूं और मैटैब सत्यापन और मैट्रिक्स पीढ़ी के लिए उपयोग कर रहा हूं। लेकिन जब मैं MATLAB, 2048×2048 के साथ गुणा करता हूँ और यहां तक ​​कि बड़े मैट्रिक्स लगभग तुरंत गुणा होते हैं।

1024x1024 2048x2048 4096x4096 --------- --------- --------- CUDA C (ms) 43.11 391.05 3407.99 C++ (ms) 6137.10 64369.29 551390.93 C# (ms) 10509.00 300684.00 2527250.00 Java (ms) 9149.90 92562.28 838357.94 MATLAB (ms) 75.01 423.10 3133.90 

केवल सीयूडीए प्रतियोगी है, लेकिन मुझे लगता है कि कम से कम सी ++ कुछ हद तक बंद हो जाएगा और 60x धीमा नहीं होगा।

तो मेरा सवाल है – MATLAB यह तेज़ कैसे कर रहा है?

सी ++ कोड:

 float temp = 0; timer.start(); for(int j = 0; j < rozmer; j++) { for (int k = 0; k < rozmer; k++) { temp = 0; for (int m = 0; m < rozmer; m++) { temp = temp + matice1[j][m] * matice2[m][k]; } matice3[j][k] = temp; } } timer.stop(); 

संपादित करें: मुझे यह भी पता नहीं है कि सी # परिणामों के बारे में क्या सोचना है एल्गोरिदम केवल सी ++ और जावा के समान है, लेकिन 1024 से एक विशाल छलांग 2048 है?

संपादित करें 2: अपडेट किया गया MATLAB और 4096×4096 परिणाम

वेब के समाधान से एकत्रित समाधान "मैट्रिक्स गुणा में MATLAB इतनी तेज़ी क्यों है?"

यहां टेसेला सी 2070 के साथ मशीन पर MATLAB R2011a + समानांतर कंप्यूटिंग टूलबॉक्स का उपयोग करते हुए मेरे परिणाम हैं:

 >> A = rand(1024); gA = gpuArray(A); % warm up by executing the operations a couple of times, and then: >> tic, C = A * A; toc Elapsed time is 0.075396 seconds. >> tic, gC = gA * gA; toc Elapsed time is 0.008621 seconds. 

मैटल मैट्रिक्स गुणा के लिए अत्यधिक अनुकूलित लाइब्रेरी का उपयोग करता है जिससे सादे मैटलॉग मैट्रिक्स गुणा इतना तेज हो। gpuArray संस्करण gpuArray का उपयोग करता है

Tesla K20c, और नए समय और gputimeit फ़ंक्शंस के साथ मशीन पर R2014a का उपयोग करके अपडेट करें:

 >> A = rand(1024); gA = gpuArray(A); >> timeit(@()A*A) ans = 0.0324 >> gputimeit(@()gA*gA) ans = 0.0022 

इस प्रकार का प्रश्न आवर्ती है और "मटैब अत्यधिक अनुकूलित लाइब्रेरी का उपयोग करता है" या "मैटलब एमकेएल का उपयोग करता है" स्टैकेवरफ्लो पर एक बार के लिए अधिक स्पष्ट रूप से जवाब देना चाहिए।

इतिहास:

मैट्रिक्स गुणा (मैट्रिक्स-वेक्टर, वेक्टर-वेक्टर गुणा और मैट्रिक्स अपघटन से कई) एक साथ रैखिक अल्ग्रेब्रा में सबसे महत्वपूर्ण समस्याएं हैं (हैं) इंजीनियर्स शुरुआती दिनों के बाद से इन समस्याओं को कंप्यूटर के साथ हल कर रहे हैं

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

BLAS:

स्तर 1 (पहला संस्करण जो स्केलर-वेक्टर और वेक्टर-वेक्टर परिचालन को परिभाषित करता है) स्तर 2 (वेक्टर-मैट्रिक्स संचालन) से लेकर 3 स्तर (मैट्रिक्स-मैट्रिक्स संचालन) से विकसित हुआ है, और अधिक से अधिक "कर्नेल" प्रदान किए गए हैं ताकि मानकीकृत अधिक और अधिक मौलिक रैखिक बीजगणित संचालन मूल फोरट्रान 77 कार्यान्वयन अभी भी नेटलिब की वेबसाइट पर उपलब्ध हैं।

बेहतर प्रदर्शन की ओर:

वर्षों में (विशेषकर बीएलएएस स्तर 1 और स्तर 2 रिलीज: शुरुआती 80 के बीच), वेक्टर ऑपरेशन और कैशे पदानुक्रम के आगमन के साथ हार्डवेयर बदल दिया गया। इन एवोल्यूशन ने बीएलएस उप-रूटिनों के प्रदर्शन को काफी बढ़ाया है। इसके बाद विभिन्न विक्रेताओं ने बीएलएएस डेलीटाइन्स के कार्यान्वयन के साथ साथ आया जो कि अधिक से अधिक कुशल थे।

मुझे सभी ऐतिहासिक कार्यान्वयन (मैं जन्म नहीं हुआ या फिर एक बच्चा नहीं) नहीं जानता था, लेकिन दो सबसे उल्लेखनीय लोगों में से 2,000 के दशक के शुरुआती दौर में बाहर आया: इंटेल एमकेएल और गोटोब्लैएस आपका Matlab इंटेल एमकेएल का उपयोग करता है, जो एक बहुत अच्छा, ऑप्टिमाइज़ किए गए BLAS है, और जो आपके द्वारा देखे जाने वाले महान प्रदर्शन की व्याख्या करता है।

मैट्रिक्स गुणा पर तकनीकी विवरण:

तो क्यों Matlab ( dgemm ) dgemm (डबल परिशुद्धता सामान्य मैट्रिक्स-मैट्रिक्स गुणा) में इतनी तेज है? सरल शब्दों में: क्योंकि यह सदिश और डेटा के अच्छे कैशिंग का उपयोग करता है। अधिक जटिल शब्दों में: जोनाथन मूर द्वारा दिए गए आलेख देखें

असल में, जब आप आपके द्वारा प्रदत्त सी ++ कोड में गुणन करते हैं, तो आप सभी कैश-मैत्रीपूर्ण नहीं होते हैं। चूंकि मुझे संदेह है कि आप पंक्ति सरणियों के लिए पॉइंटर्स की एक सरणी बनाते हैं, तो "मैटिस 2" के के-वें कॉलम में आपके आंतरिक लूप में आपके एक्सेस: matice2[m][k] बहुत धीमी गति से हैं दरअसल, जब आप matice2[0][k] तक matice2[0][k] , तो आपको अपने मैट्रिक्स के सरणी 0 के कश्मीर तत्व प्राप्त करना चाहिए। फिर अगले matice2[1][k] , आपको matice2[1][k] उपयोग करना होगा, जो कि अन्य सरणी (एरे 1) का कश्मीर तत्व है। फिर अगले matice2 आप एक और सरणी तक पहुंच सकते हैं, और इसी तरह … क्योंकि पूरे मैट्रिक्स matice2 उच्चतम कैश में फिट नहीं हो सकता (यह 8*1024*1024 बाइट्स बड़े है), प्रोग्राम को वांछित तत्व को मुख्य से प्राप्त करना चाहिए स्मृति, बहुत समय खोने

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

 timer.start(); float temp = 0; //transpose matice2 for (int p = 0; p < rozmer; p++) { for (int q = 0; q < rozmer; q++) { tempmat[p][q] = matice2[q][p]; } } for(int j = 0; j < rozmer; j++) { for (int k = 0; k < rozmer; k++) { temp = 0; for (int m = 0; m < rozmer; m++) { temp = temp + matice1[j][m] * tempmat[k][m]; } matice3[j][k] = temp; } } timer.stop(); 

तो आप देख सकते हैं कि कैश इलाके में सिर्फ आपके कोड के प्रदर्शन में काफी वृद्धि हुई है। अब वास्तविक dgemm कार्यान्वयन एक बहुत ही व्यापक स्तर पर फायदा उठाते हैं: वे टीएलबी के आकार के द्वारा परिभाषित मैट्रिक्स के ब्लॉक पर गुणा करते हैं (अनुवाद लुकसाइड बफर, लंबी कहानी छोटी: प्रभावी रूप से कैश की जाती है), ताकि वे प्रोसेसर, जिस पर डेटा की प्रक्रिया हो सकती है दूसरा पहलू वेक्टरिंग है, वे इष्टतम अनुदेश थ्रूपूट के लिए प्रोसेसर के वेक्टर वाले निर्देशों का उपयोग करते हैं, जो आप वास्तव में अपने क्रॉस-प्लेटफ़ॉर्म C ++ कोड से नहीं कर सकते हैं।

अंत में, लोग यह दावा करते हैं कि स्ट्रैसन या कॉपरस्मिथ-विनोग्रेड एल्गोरिथम के कारण यह गलत है, इन दोनों एल्गोरिदम को व्यवहार में लागू नहीं किया जा सकता है, क्योंकि ऊपर उल्लेखित हार्डवेयर के मामले हैं।

यही कारण है कि MATLAB प्रत्येक एक तत्व को अपने सी ++ कोड में आपके द्वारा किए गए तरीके से पाशन करके एक भोलेदार मैट्रिक्स गुणा नहीं करता है।

बेशक मैं मान रहा हूँ कि आपने C=A*B उपयोग केवल एक गुणन समारोह को लिखने के बजाय किया था

Matlab कुछ समय पहले शामिल LAPACK, तो मैं मानता हूँ कि उनके मैट्रिक्स गुणा कम से कम उस तेजी से कुछ का उपयोग करता है LAPACK स्रोत कोड और प्रलेखन आसानी से उपलब्ध है।

आप गोटो और वान डे गीइज के पेपर "एनाटॉमी ऑफ हाई-परफॉर्मेंस मैट्रिक्स गुणा" पर भी देख सकते हैं http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.11.1785&rep=rep1&type=pdf

मैट्रिक्स गुणा करते समय, आप सरल गुणा पद्धति का उपयोग करते हैं जो O(n^3) का समय लगता है।

मैट्रिक्स गुणा एल्गोरिथ्म मौजूद है जो O(n^2.4) लेता है। जिसका अर्थ है कि n=2000 आपके एल्गोरिथम को ~ 100 गुना जितना सबसे अच्छा एल्गोरिथ्म के रूप में गणना की आवश्यकता है।
मैट्रिक्स गुणा के लिए आपको वास्तव में इसे कार्यान्वित करने के कुशल तरीके से अधिक जानकारी के लिए विकिपीडिया पेज की जांच करनी चाहिए।

सी ++ के साथ निष्पक्ष तुलना करने के बारे में आपको सावधान रहने की जरूरत है क्या आप सी ++ कोड पोस्ट कर सकते हैं जो मैट्रिक्स गुणन के लिए उपयोग किए जा रहे कोर इनर लूप को दर्शाता है? अधिकतर, मैं आपकी मेमोरी लेआउट से चिंतित हूं और आप चीजों को बेकार कर रहे हैं या नहीं।

मैंने सी ++ मैट्रिक्स गुणा लिखा है जो कि जितना तेज़ Matlab है उतना ही है, लेकिन यह कुछ ध्यान रखता है। (संपादित करें: इससे पहले Matlab इस के लिए GPU का उपयोग कर रहा था।)

आप वस्तुतः गारंटी दे सकते हैं कि इन "बिल्ट-इन" फ़ंक्शंस पर Matlab बहुत ही कम चक्र बर्बाद कर रहा है मेरा सवाल है, तुम कहाँ चकाचियां बर्बाद कर रहे हो? (कोई अपराध नहीं)

इसका जवाब है LAPACK और BLAS पुस्तकालय MATLAB अंधाधुंध रूप से मैट्रिक्स परिचालन पर तेजी से बनाते हैं, MATLAB में लोगों द्वारा कोई स्वामित्व कोड नहीं।

मैट्रिक्स संचालन के लिए आपके C ++ कोड में LAPACK और / या BLAS पुस्तकालयों का उपयोग करें और आपको MATLAB के समान प्रदर्शन प्राप्त करना चाहिए। इन पुस्तकालयों को किसी भी आधुनिक प्रणाली पर स्वतंत्र रूप से उपलब्ध होना चाहिए और कुछ दशकों से शिक्षाविदों में भागों का विकास किया गया। ध्यान दें कि कई बंदरगाहों जैसे इंटेल एमकेएल जैसे कई कार्यान्वयन हैं

क्यों इतनी तेजी से बल्ले / LAPACK है? (i) कुशल एल्गोरिदम और (ii) ठीक ट्यूनिंग जो CPU वास्तुकला का शोषण करता है। उदाहरण के लिए। यह पता चला है कि मैट्रिक्स गुणन हे (एन ^ 3) एल्गोरिथम के बजाय ओ (एन ^ 2.807) के साथ किया जा सकता है, और यह कई बीएलएएस लागूकरणों में शामिल है। संचालन के चालाक समूह, सीपीयू रजिस्टरों आदि पर संख्याओं को स्थानांतरित करने की आवश्यकता को कम करता है …


बीटीडब्लू, यह मेरे अनुभव में एक गंभीर दर्द है, जो सीधे सी (लेकिन इसके लायक) से लैपैक पुस्तकालयों को कॉल करने के लिए है। आपको दस्तावेज़ को बहुत ही सटीक रूप से पढ़ना होगा।

Matlab के आपके संस्करण के आधार पर, मेरा मानना ​​है कि यह आपके GPU का उपयोग पहले से कर सकता है

एक और बात; Matlab आपके मैट्रिक्स के कई गुणों का ट्रैक रखता है; इसकी विकर्ण, हेमेटीयन, और इसके आगे की तरफ, और इसके आधार पर इसके एल्गोरिदम का विशेषज्ञ करती है। शायद इसकी विशेषज्ञता शून्य मैट्रिक्स के आधार पर आप इसे पारित कर रहे हैं, या ऐसा कुछ? शायद यह दोहराए जाने वाले फ़ंक्शन कॉल्स को कैशिंग कर रहा है, जो आपके समय को खराब करता है? शायद यह दोहराया अप्रयुक्त मैट्रिक्स उत्पादों का अनुकूलन करता है?

ऐसा होने वाली चीजों से रक्षा करने के लिए, यादृच्छिक संख्या का एक मैट्रिक्स का उपयोग करें, और सुनिश्चित करें कि आप परिणाम को स्क्रीन या डिस्क या कुछ समय के लिए प्रिंट करके निष्पादन को बल देते हैं।

सी ++ / जावा (आपके कोड के साथ: 1024 – थोड़ी सी तेजी से, 2048 – लगभग 140 और 4096 – लगभग 22 मिनट था) के रूप में लगभग तीन अलग-अलग परिणामों में डबल्स और एक ठोस सरणी का उपयोग किया जाता है।

                 1024x1024 2048x2048 4096x4096
                 --------- --------- ---------
 आपका सी ++ (एमएस) 6137.10 64369.29 551390.93
 मेरी सी # (एमएस) 9730.00 90875.00 1062156.00

यहां मेरा कोड है:

  const int rozmer = 1024; double[][] matice1 = new double[rozmer * 3][]; Random rnd = new Random(); public Form1() { InitializeComponent(); System.Threading.Thread thr = new System.Threading.Thread(new System.Threading.ThreadStart(() => { string res = ""; Stopwatch timer = new Stopwatch(); timer.Start(); double temp = 0; int r2 = rozmer * 2; for (int i = 0; i < rozmer*3; i++) { if (matice1[i] == null) { matice1[i] = new double[rozmer]; { for (int e = 0; e < rozmer; e++) { matice1[i][e] = rnd.NextDouble(); } } } } timer.Stop(); res += timer.ElapsedMilliseconds.ToString(); int j = 0; int k = 0; int m = 0; timer.Reset(); timer.Start(); for (j = 0; j < rozmer; j++) { for (k = 0; k < rozmer; k++) { temp = 0; for (m = 0; m < rozmer; m++) { temp = temp + matice1[j][m] * matice1[m + rozmer][k]; } matice1[j + r2][k] = temp; } } timer.Stop(); this.Invoke((Action)delegate { this.Text = res + " : " + timer.ElapsedMilliseconds.ToString(); }); })); thr.Start(); } 

क्या आपने जांच की है कि सभी कार्यान्वयन एल्गोरिदम के लिए बहु-थ्रेडिंग ऑप्टिमाइज़ेशन का उपयोग करते हैं? और क्या उन्होंने एक ही गुणा एल्गोरिथ्म का उपयोग किया?

मुझे सचमुच संदेह है।

Matlab स्वाभाविक रूप से तेज नहीं है, शायद आप धीमी क्रियान्वयन का उपयोग करते हैं

कुशल मैट्रिक्स गुणा के लिए एल्गोरिदम

"अन्य कार्यक्रमों की तुलना में xxx करने पर मैटलैब तेज़ क्यों है" का सामान्य जवाब यह है कि मैटलैब में बहुत से निर्मित, अनुकूलित फ़ंक्शन हैं।

अन्य कार्यक्रमों का इस्तेमाल अक्सर इन फ़ंक्शन नहीं होते हैं, ताकि लोग अपने स्वयं के रचनात्मक समाधान लागू कर सकें, जो कि पेशेवर रूप से अनुकूलित कोड से बढ़कर धीमी हो।

इसे दो तरीकों से व्याख्या किया जा सकता है:

1) सामान्य / सैद्धांतिक तरीका: Matlab काफी तेज नहीं है, आप केवल बेंचमार्क गलत कर रहे हैं

2) यथार्थवादी तरीके: इस सामग्री के लिए मैटलब अभ्यास में तेजी से है क्योंकि भाषाओं के रूप में सी ++ अप्रभावी तरीकों में बहुत आसानी से उपयोग किया जाता है।

तीव्र विपरीत न केवल Matlab के अद्भुत अनुकूलन के कारण (जैसा कि पहले से ही कई अन्य जवाबों के द्वारा चर्चा की गई है), बल्कि जिस तरह से आपने एक वस्तु के रूप में मैट्रिक्स तैयार किया है

ऐसा लगता है कि आपने मैट्रिक्स सूची की सूची बनाई है? सूचियों की सूची में उन सूचियों के लिए संकेत दिए गए हैं, जिनमें आपके मैट्रिक्स तत्व शामिल होते हैं। निहित सूची के स्थानों को मनमाने ढंग से सौंपा गया है जैसा कि आप अपनी पहली इंडेक्स (पंक्ति संख्या?) पर पाशन कर रहे हैं, स्मृति एक्सेस का समय बहुत महत्वपूर्ण है तुलना में, आप निम्न पद्धति का उपयोग करके एक सूची / वेक्टर के रूप में मैट्रिक्स को लागू करने की कोशिश क्यों नहीं करते हैं?

 #include <vector> struct matrix { matrix(int x, int y) : n_row(x), n_col(y), M(x * y) {} int n_row; int n_col; std::vector<double> M; double &operator()(int i, int j); }; 

तथा

 double &matrix::operator()(int i, int j) { return M[n_col * i + j]; } 

समान गुणा एल्गोरिथ्म का उपयोग किया जाना चाहिए ताकि फ्लॉप की संख्या समान हो। (n ^ 3 आकार के वर्ग मैट्रिक्स के लिए)

मैं आपको समय देने के लिए कह रहा हूं ताकि परिणाम पहले की तुलना में तुलनीय हो (एक ही मशीन पर)। तुलना के साथ, आप दिखाएंगे कि स्मृति पहुंच का समय कितना महत्वपूर्ण हो सकता है!

मैटलप इंटेल मैथ कर्नल लाइब्रेरी (इंटेल एमकेएल ) के रूप में जाने वाले इंटेल मैसेज से LAPACK के अत्यधिक अनुकूलित कार्यान्वयन का उपयोग करता है – विशेष रूप से डीजीएमएम फ़ंक्शन । गति यह लाइब्रेरी प्रोसेसर सुविधाओं का लाभ लेती है जिसमें सिम निर्देश और मल्टी-कोर प्रोसेसर शामिल हैं। वे दस्तावेज नहीं करते हैं कि वे किस विशिष्ट एल्गोरिथम का उपयोग करते हैं। अगर आप इंटेल एमकेएल को सी ++ से कॉल करते हैं तो आपको समान प्रदर्शन दिखना चाहिए।

मुझे यकीन नहीं है कि जीपीयू गुणा करने के लिए MATLAB जीने वाली लाइब्रेरी है, लेकिन संभवतः एनवीआईडीएयू क्यूब्स जैसी कुछ चीज है ।

यह C ++ में धीमा है क्योंकि आप मल्टीथ्रेडिंग का उपयोग नहीं कर रहे हैं मूलतः, यदि ए = बीसी, जहां वे सभी मैट्रिक्स हैं, तो ए की पहली पंक्ति को दूसरी पंक्ति आदि से स्वतंत्र रूप से गिना जा सकता है। यदि ए, बी और सी सभी एन मैट्रिक्स से n हो जाते हैं, तो आप गुणा बढ़ा सकते हैं एन ^ 2 का एक कारक, जैसा कि

a_ {i, j} = sum_ {k} b_ {i, k} c_ {k, j}

यदि आप उपयोग करते हैं, तो कहें, ईगेन [ http://eigen.tuxfamily.org/dox/GettingStarted.html ], मल्टीथ्रेडिंग अंतर्निहित है और थ्रेड की संख्या समायोज्य है