मेरे मैट्रिक्स गुणा को धीमा क्यों करता है?

Question

मैं boost::numeric::ublas::matrix के साथ एक आव्यूह गुणन को लागू किया है (my full, working boost code देख)

Result result = read(); 

boost::numeric::ublas::matrix<int> C; 
C = boost::numeric::ublas::prod(result.A, result.B); 

और मानक एल्गोरिथ्म के साथ एक दूसरे से (full standard code देखें):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
            vector< vector<int> > B) { 
    int n = A.size(); 

    // initialise C with 0s 
    vector<int> tmp(n, 0); 
    vector< vector<int> > C(n, tmp); 

    for (int i = 0; i < n; i++) { 
     for (int k = 0; k < n; k++) { 
      for (int j = 0; j < n; j++) { 
       C[i][j] += A[i][k] * B[k][j]; 
      } 
     } 
    } 
    return C; 
} 

यह मैं कैसे गति का परीक्षण है:

time boostImplementation.out > boostResult.txt 
diff boostResult.txt correctResult.txt 

time simpleImplementation.out > simpleResult.txt 
diff simpleResult.txt correctResult.txt 

दोनों प्रोग्राम एक हार्ड-कोडेड टेक्स्टफाइल पढ़ते हैं जिसमें दो 2000 x 2000 matri सीईएस। दोनों कार्यक्रमों इन झंडे के साथ संकलित किया गया:

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic 

मैं अपने कार्यान्वयन के लिए और बढ़ावा-कार्यान्वयन के लिए से अधिक 4 मिनट15 सेकंड मिल गया है!

संपादित करें:

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out 

साथ यह संकलन करने के बाद मैं 28.19 सेकंड ikj-एल्गोरिथ्म के लिए और 60.99 सेकंड बूस्ट के लिए मिला है। तो बूस्ट अभी भी काफी धीमी है।

मेरे कार्यान्वयन से इतना धीमा क्यों है?

Answer 1

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

यहाँ समय पर डिबगिंग साथ uBLAS संस्करण द्वारा उठाए गए है:

real 0m7.061s 
user 0m6.936s 
sys  0m0.096s 

साथ

तो:

real 0m19.966s 
user 0m19.809s 
sys  0m0.112s 

यहाँ समय डिबगिंग साथ uBLAS संस्करण द्वारा उठाए गए (-DNDEBUG -DBOOST_UBLAS_NDEBUG संकलक झंडे जोड़ा) है डीबगिंग बंद, यूबीएलएस संस्करण लगभग 3 गुना तेजी से है।

ublas का एक महत्वपूर्ण डिजाइन लक्ष्य के रूप में के रूप में सामान्य हो रहा है:

शेष प्रदर्शन अंतर uBLAS FAQ के निम्न अनुभाग के हवाले से समझाया जा सकता "क्यों uBLAS से (atlas-) BLAS तो बहुत धीमी है" मुमकिन।

यह सामान्यता लगभग हमेशा लागत के साथ आता है। विशेष रूप से prod फ़ंक्शन टेम्पलेट विभिन्न प्रकार के मैट्रिक्स, जैसे स्पैस या त्रिभुज को संभाल सकता है। सौभाग्य से uBLAS घने मैट्रिक्स गुणा के लिए अनुकूलित विकल्प प्रदान करता है, विशेष रूप से, axpy_prod और block_prod।

ijkalgorithm prod axpy_prod block_prod 
    1.335  7.061 1.330  1.278 

आप देख सकते हैं दोनों axpy_prod और block_prod कुछ हद तक तेजी से अपने कार्यान्वयन से कर रहे हैं: यहाँ विभिन्न तरीकों की तुलना के परिणाम हैं।I/O के बिना गणना समय को मापना, block_prod (मैंने 64 का उपयोग किया) के लिए ब्लॉक आकार की अनावश्यक प्रतिलिपि और सावधानीपूर्वक विकल्प को हटाकर अंतर को और अधिक गहरा कर सकता है।

uBLAS FAQ और Effective uBlas and general code optimization भी देखें।

Answer 2

मेरा मानना ​​है कि आपका कंपाइलर पर्याप्त अनुकूलित नहीं करता है। यूब्लैस कोड टेम्पलेट्स का भारी उपयोग करता है और टेम्पलेट्स को अनुकूलन के भारी उपयोग की आवश्यकता होती है। मैं 1000x1000 मैट्रिक्स के लिए रिलीज़ मोड में एमएस कुलपति 7.1 संकलक के माध्यम से अपने कोड भाग गया, यह मुझे देता है uBLAS के लिए

10.064 रों वेक्टर

के लिए

7.851 रों अंतर अभी भी वहाँ है, लेकिन कोई भारी तरह से । यूबीएलएएस की मूल अवधारणा आलसी मूल्यांकन है, इसलिए prod(A, B) केवल तभी परिणाम का मूल्यांकन करता है जब आवश्यक हो, उदा। prod(A, B)(10,100) किसी भी समय निष्पादित नहीं होगा, क्योंकि केवल एक तत्व की गणना की जाएगी। इस प्रकार वास्तव में पूरे मैट्रिक्स गुणा के लिए कोई समर्पित एल्गोरिदम नहीं है जिसे अनुकूलित किया जा सकता है (नीचे देखें)। लेकिन आप पुस्तकालय एक छोटे से मदद कर सकता है,

matrix<int, column_major> B; 

घोषित 4.426 रों जो एक हाथ बंधे के साथ अपने समारोह धड़कता करने के लिए चल रहा है समय कम हो जाएगा। कैश उपयोग को अनुकूलित करने, मैट्रिक्स को गुणा करते समय यह घोषणा स्मृति को अधिक क्रमिक तक पहुंच प्रदान करती है।

पीएस अंत में यूबीएलएस दस्तावेज पढ़ने के बाद;), आपको यह पता होना चाहिए था कि वास्तव में पूरे मैट्रिक्स को गुणा करने के लिए वास्तव में एक समर्पित फ़ंक्शन है। 2 फ़ंक्शन - axpy_prod और opb_prod। तो

opb_prod(A, B, C, true); 

भी unoptimized row_major बी मैट्रिक्स पर

8.091 सेकंड में निष्पादित करता है और अपने वेक्टर एल्गोरिथ्म

P.P.S. के समान है वहाँ और भी अधिक अनुकूलन है:

C = block_prod<matrix<int>, 1024>(A, B); 

4.4 रों में कार्यान्वित करता है, कोई फर्क नहीं पड़ता कि क्या बी column_ या row_ प्रमुख है। विवरण पर विचार करें: "फ़ंक्शन block_prod बड़े घने मैट्रिक्स के लिए डिज़ाइन किया गया है।" विशिष्ट कार्यों के लिए विशिष्ट उपकरण चुनें!

Answer 3

मैंने एक छोटी वेबसाइट Matrix-Matrix Product Experiments with uBLAS बनाई। यह यूआरएलएएस में मैट्रिक्स-मैट्रिक्स उत्पाद के लिए एक नया कार्यान्वयन एकीकृत करने के बारे में है। यदि आपके पास पहले से ही बूस्ट लाइब्रेरी है तो इसमें केवल 4 अतिरिक्त फ़ाइलें शामिल हैं। तो यह बहुत ज्यादा आत्मनिर्भर है।

मुझे दिलचस्पी होगी यदि अन्य अलग-अलग मशीनों पर सरल मानक चला सकें।