👨🏼‍💼 🌧️ 🗽 जल्दी या सरल कार्यक्रम अनुकूलन को गुणा करें 👩🏾‍🤝‍👨🏻 👨 🤪

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

निश्चित रूप से अधिकांश पूरे लेख को पढ़ने के लिए बहुत आलसी होंगे, लेकिन मैं आपको नीचे स्क्रॉल करने और निष्कर्ष पढ़ने की सलाह देता हूं - मैं वहां दिलचस्प संख्याओं को समझूंगा।

तो कार्य: डबल्स के दो बड़े मेट्रिक्स को गुणा करना (तीसरे क्रम के आकारों में)। सादगी के लिए, हम वर्ग मैट्रिसेस पर विचार करेंगे, हालांकि सभी एल्गोरिदम आयताकार लोगों के लिए भी उपयुक्त हैं। एल्गोरिथ्म C ++ में लिखा गया था, लेकिन कभी भी कहीं भी कक्षाओं का उपयोग नहीं किया गया, इसलिए कोड को C- संगत माना जा सकता है (शायद केवल cout ने इसका उपयोग किया है)।

मैं यहां यह नहीं बताऊंगा कि एक मैट्रिक्स क्या है और उन्हें कैसे गुणा करना है - जो लोग यह नहीं जानते हैं, वे शायद ही कभी इस बात में दिलचस्पी लेंगे कि गुणा को कैसे तेज किया जाए ...

इसके साथ शुरू करने के लिए, हम यह निर्धारित करते हैं कि मैट्रिसेस को आकार n * n के एक-आयामी सरणी में संग्रहीत किया जाएगा। तत्व A (i, j) को [i * n + j] के रूप में संदर्भित किया जाएगा। दो-आयामी सरणी की तुलना में एक-आयामी तेज़ी से संग्रहीत करें, क्योंकि एक पूर्णांक गुणन और एक मेमोरी एक्सेस दो मेमोरी एक्सेस की तुलना में तेज़ है।

गुणा करने का पहला सबसे तार्किक तरीका है

 int मल्टीमैट्रिक्स एसबड (डबल * ए, कॉन्स्ट इंट एन, डबल * बी, डबल * सी) {
	 int i, j, k;
	 के लिए (i = 0; मैं <n; i ++) {
		 के लिए (j = 0; j <n; j ++) {
			 c [i * n + j] = 0;
			 के लिए (k = 0; k <n; k ++) {
				 c [i * n + j] + = a [i * n + k] * b [k * n + j];
			 }
		 }
	 }
	 वापसी 0;
 }

ध्यान दें, सबसे पहले, चक्र में हम कई बार i * n गुणा करते हैं। प्रत्येक बार, c [i * n + j] को जोड़कर मेमोरी को एक्सेस करना वैकल्पिक है - आप इस सब को एक वेरिएबल में जोड़ सकते हैं, और उसके बाद ही इसे c [i * n + j] से समान कर सकते हैं। हम यह भी ध्यान देते हैं कि अब संकलक हमारे कोड को बहुत अच्छी तरह से अनुकूलित करते हैं, लेकिन प्रदर्शन में सुधार के लिए शाखा बिंदुओं (यदि, आदि,) पर समस्याएं उत्पन्न होती हैं, तो आपको निर्देश पाइपलाइन की गहराई बढ़ाने की कोशिश करनी चाहिए, अर्थात्। एल्गोरिथ्म का रैखिक हिस्सा (जब गणना बिना किसी स्थिति या चक्र के एक पंक्ति में जाती है) इसलिए, हम अपने मुख्य चक्र का विस्तार करेंगे ताकि एक नहीं बल्कि 4 गुणा तीसरे चक्र के अंदर हो। ठीक है, हम स्मृति को यथासंभव कम और गुणा करने की कोशिश करेंगे, और स्थानीय चर और संकेत में सब कुछ बचाएंगे, जो काम को गति भी देते हैं। हम मैट्रिस के सम और विषम आकारों के लिए कोड डबिंग करते हैं, ताकि लूप के अंदर समता की जांच न हो, लेकिन एक बार जांच लें। हमें यह फ़ंक्शन मिलता है:

 int मल्टीमैट्रिक्स एसक (डबल * ए, कॉन्स्ट इंट एन, डबल * बी, डबल * सी) {
	 double s1 = 0, s2 = 0, s3 = 0, s4 = 0;
	 डबल * एफ, * जी, * एच;
	 int i, j, k;
	 अगर (n% 2 == 0) {
		 के लिए (i = 0; मैं <n-1; मैं + = 2)
		 {
			 f = a + i * n;
			 के लिए (j = 0; j <n-1; j + = 2)
			 {
				 जी = बी + जे;
				 के लिए (k = 0; k <n; k ++) {
					 s1 + = f [k] * g [n * k];	
					 s2 + = f [n + k] * g [n * k];	
					 s3 + = f [k] * g [n * k + 1];	
					 s4 + = f [n + k] * g [n * k + 1];	
				 }
				 h = c + i * n + j;
				 h [0] = s1;  s1 = 0;
				 h [n] = s2;  s2 = 0;
				 h [१] = s3;  s3 = 0;
				 h [n + 1] = s4;  s4 = 0;
			 }
		 }
	 }
	 और {
		 के लिए (i = 0; मैं <n-1; मैं + = 2)
			 {
				 f = a + i * n;
				 के लिए (j = 0; j <n-1; j + = 2)
				 {
					 जी = बी + जे;
					 के लिए (k = 0; k <n; k ++) {
						 s1 + = f [k] * g [n * k];
						 s2 + = f [n + k] * g [n * k];
						 s3 + = f [k] * g [n * k + 1];
						 s4 + = f [n + k] * g [n * k + 1];
					 }
					 h = c + i * n + j;
					 h [0] = s1;  s1 = 0;
					 h [n] = s2;  s2 = 0;
					 h [१] = s3;  s3 = 0;
					 h [n + 1] = s4;  s4 = 0;
				 }
				 अगर (j == n-1) {
					 जी = बी + जे;
					 के लिए (k = 0; k <n; k ++) {
						 s1 + = f [k] * g [n * k];	
						 s2 + = f [n + k] * g [n * k];	
					 }
					 h = c + i * n + j;
					 h [0] = s1;  s1 = 0;
					 h [n] = s2;  s2 = 0;
				 }
			 }
			 अगर (i == n-1) {
				 f = a + i * n;
				 के लिए (j = 0; j <n-1; j + = 2)
				 {
					 जी = बी + जे;
					 के लिए (k = 0; k <n; k ++) {
						 s1 + = f [k] * g [n * k];	
						 s3 + = f [k] * g [n * k + 1];	
					 }
					 h = c + i * n + j;
					 h [0] = s1;  s1 = 0;
					 h [१] = s3;  s3 = 0;
				 }
				 अगर (j == n-1) {
					 जी = बी + जे;
					 के लिए (k = 0; k <n; k ++) {
						 s1 + = f [k] * g [n * k];	
					 }
					 h = c + i * n + j;
					 h [0] = s1;  s1 = 0;
				 }
			 }
		 }
	 वापसी 0;
 }

खैर, अंतिम स्पर्श। जब हम एक चक्र में मैट्रिक्स से गुजरते हैं, तो हमें किसी तरह रैम से जानकारी लेनी होती है (विशेषकर जब हम कॉलम के माध्यम से पढ़ते हैं)। रैम से कैश तक, जानकारी लाइनों में संग्रहीत होती है (यानी जब हम एक तत्व पढ़ते हैं - इसके बाद कई तत्व कैश में डाल दिए जाते हैं), और जब हम कॉलम से गुजरते हैं - तो हमें हर बार मेमोरी में चढ़ना पड़ता है। ऐसा होने से रोकने के लिए, और सबसे अधिक बार हमें कैश के साथ काम करना पड़ता था, और रैम के साथ नहीं, हम निम्नलिखित करेंगे: हम अपने मैट्रिक्स को लगभग 100 से उप-मेट्रिक्स में 100 से विभाजित करते हैं (आकार फ़ंक्शन तर्क में निर्दिष्ट होता है)। यदि यह पूरी तरह से साझा नहीं किया गया है, तो यह डरावना नहीं है, हम नीचे और दाईं ओर से आयताकार टुकड़े छोड़ते हैं। हम अपने उपमात्राओं A (1,1), ..., A (n, n) को क्रमशः कहते हैं। और हम सामान्य नियम के अनुसार सबमेट्रिसेस से मैट्रिक्स को गुणा करेंगे। गणितीय रूप से यह साबित करना मुश्किल नहीं है कि इसका उत्तर सामान्य गुणा के समान होगा, लेकिन अब जब हम दो छोटे मेट्रिसेस को गुणा करते हैं, तो वे दोनों कैश में फिट होते हैं और बहुत तेजी से बढ़ते हैं। गुणन के लिए, हमें "एक सबमेट्रिक्स ले लो" और "क्या है, यह कहते हुए, एक सबमेट्रिक्स डालिए" कार्यों की आवश्यकता होगी। मैट्रिक्स को शून्य करने के कार्य, साथ ही आयताकार मैट्रिक्स को गुणा करने का कार्य। क्योंकि चूंकि बहुत सारे आयताकार गुणन नहीं हैं, इसलिए मैंने इसे उसी तरह से अनुकूलित करना शुरू नहीं किया जैसे कि वर्ग के लोगों के लिए। अब ऐसा लगता है कि निश्चित रूप से आयताकार लोगों के लिए एक अच्छा कार्य लिखना अधिक सही था, और वर्ग के लोगों के लिए सिर्फ एक उपनाम बनाने के लिए, मुझे याद नहीं है कि क्यों, लेकिन मैंने नहीं किया। इसलिए हम अंतिम कार्य लिखते हैं:

 int मल्टीमैट्रिक्सब्लॉक (डबल * ए, कॉन्स्ट इन्ट एन, डबल * बी, कास्ट इंट एम, डबल * रेस, डबल * सी, डबल * डी, डबल * ई) {
	 int n_block = n / m;
	 int m_small;
	 int i, j, k, o;
	 m_small = n-n_block * m;
	 clearMatrix (रेस, एन * एन);
	 के लिए (i = 0; मैं <= n_block; मैं ++)
	 {
		 के लिए (j = 0; j <= n_block; j ++)
		 {
			 के लिए (k = 0; k <= n_block; k ++)
			 {
				 अगर (i <n_block && j <n_block && k <n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्स एस (सी, एम, डी, ई);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);
				 }
				 और अगर (i <n_block && j <n_block && k == n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्सRect (c, m, d, m_small, m, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);	
				 }
				 और अगर (i == n_block && j <n_block && k <n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्सRect (c, m_small, d, m, m, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);
				 }
				 अगर (i == n_block && j <n_block && k == n_block) {	
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्सRect (c, m_small, d, m_small, m, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);	
				 }
				 और अगर (i <n_block && j == n_block && k <n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्सRect (c, m, d, m, m_small, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);
				 }
				 और अगर (i <n_block && j == n_block && k == n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्सRect (c, m, d, m_small, m_small, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);
				 }
				 और अगर (i == n_block && j == n_block && k <n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 multMatrixRect (c, m_small, d, m, m_small, e);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);	
				 }
				 और अगर (i == n_block && j == n_block && k == n_block) {
					 getSubMatrix (ए, एन, सी, एम, आई, के);
					 getSubMatrix (b, n, d, m, k, j);
					 मल्टीमैट्रिक्स एस (सी, एम_स्मॉल, डी, ई);
					 setSubMatrixAdded (रेस, एन, ई, एम, आई, जे);	
				 }
			 }
		 }
	 }
	 वापसी 0;
 }

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

 दोहरा फार्मूला (इंट मैं, इंट जे, इंट एन) {
	 वापसी 1 / (डबल (i + j + 1));
 }

यहां या यहां कार्यक्रम का पूरा पाठ

इस तरह से संकलित किया गया मैट्रिक्स_test.cpp फ़ाइल:

  g ++ मैट्रिक्स_test.cpp -O3

यहां मेरे कंप्यूटरों पर परीक्षण के परिणाम हैं (आईमैक और तोशिबा के लिए सबमेट्रिसेस का आकार 200 है, यह इष्टतम लगता है, एथलॉन के लिए यह 115 से अधिक इष्टतम है, लेकिन उपमात्राओं के बिना भी यह खुद को सर्वश्रेष्ठ पक्ष से नहीं दिखाया गया है):

टेस्ट कंप्यूटर:

जैसा कि आप देख सकते हैं, प्रदर्शन में बढ़ोतरी बहुत अधिक है (सबसे आधुनिक प्रोसेसर पर 10 गुना से अधिक का त्वरण)। यह विचार करने योग्य है कि यह सब एक प्रक्रिया में माना जाता था, जिसका अर्थ है कि दोहरे कोर Core2Duo ने एक भूमिका नहीं निभाई थी। भविष्य में, निश्चित रूप से, मल्टीथ्रेड या एमपीआई का उपयोग करके कार्यक्रम को समानांतर करना सही होगा और 1.8-1.9 गुना की वृद्धि प्राप्त होगी। यह भी ध्यान देने योग्य है कि प्रगति अभी भी खड़ा नहीं है, और अधिक आधुनिक प्रोसेसर 5 साल पहले सिर से मॉडल से आगे निकल जाते हैं। सामान्य तौर पर, जैसा कि आप देख सकते हैं, कोड भयानक है, लेकिन यह इसके लायक है। और यह मैट्रिक्स गुणन विधि खुद नहीं है जो मायने रखता है, लेकिन कार्यक्रम के अनुकूलन के लिए संभव तकनीकें।

जल्दी या सरल कार्यक्रम अनुकूलन को गुणा करें

More articles: