एक अनुकूलन की कहानी

अमूर्त

लेख जावा में कम्प्यूटेशनल एल्गोरिदम के उच्च-स्तरीय अनुकूलन की सुविधाओं का खुलासा करता है जो एक क्यूबिक मैट्रिक्स गुणन एल्गोरिथ्म के उदाहरण का उपयोग करता है।

चरण 0. एक संदर्भ बिंदु सेट करें!

पर्यावरण का निर्धारण करें:

• हार्डवेयर: 1-सॉकेट / 2-कोर इंटेल कोर 2 डुओ T7300 2GHz, 2 जीबी रैम;
• जावा: हॉटस्पॉट (टीएम) क्लाइंट वीएम (बिल्ड 17.0-बी 17, मिश्रित मोड, साझाकरण);

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

for (int i = 0; i < A.rows(); i++) { for (int j = 0; j < A.columns(); j++) { double summand = 0.0; for (int k = 0; k < B.columns(); k++) { summand += A[i][k] * B[k][j]; } C[i][j] = summand; } } 

वर्कलोड के रूप में हम दो सघन वर्ग मेट्रिसेस N x N को दोहरी परिशुद्धता में लेते हैं, जहाँ N = 1000 है।

इस मामले में, एक साधारण घन एल्गोरिथ्म का रनटाइम 18.921 है । हम बाद के अनुकूलन के लिए इस संख्या को संदर्भ बिंदु (आधार रेखा) के रूप में मानेंगे।

चरण 1. 20/80 नियम को जानें!

यह ज्ञात है कि 20% समय कोड का 80% काम करता है। डेवलपर का कार्य कुल कोड के इन 20% की गणना करना है। हमारे मामले में, सब कुछ स्पष्ट है - वांछित 20% आंतरिक कंप्यूटिंग चक्र में केंद्रित हैं। जेवीएम के दृष्टिकोण से, यह कोड सिर्फ-इन-टाइम संकलन के लिए सबसे अधिक संभावना वाला उम्मीदवार है। आप चेक कर सकते हैं कि बायटेकोड देशी के विकल्पों का उपयोग करके संकलित किया गया है - XX: + PrintCompilation -XX: + CITime ।

 $ java -XX:+PrintCompilation la4j.Demo 1 java.lang.String::hashCode (64 bytes) 2 java.lang.String::charAt (33 bytes) 3 java.lang.String::indexOf (151 bytes) 4 java.lang.String::indexOf (166 bytes) 5 java.util.Random::next (47 bytes) 6 java.util.concurrent.atomic.AtomicLong::get (5 bytes) 7 java.util.concurrent.atomic.AtomicLong::compareAndSet (13 bytes) 8 java.util.Random::nextDouble (24 bytes) 9 la4j.matrix.DenseMatrix::set (10 bytes) 1% la4j.matrix.MatrixFactory::createRandomDenseMatrix @ 30 (68 bytes) 10 la4j.matrix.MatrixFactory::createRandomDenseMatrix (68 bytes) 2% la4j.matrix.DenseMatrix::multiply @ 81 (152 bytes) 

यह लिस्टिंग से देखा जा सकता है कि मैट्रिक्स गुणन विधि (la4j.matrix.DenseMatrix :: गुणा) सफलतापूर्वक संकलित की गई थी। यह हमें आगे की कार्रवाई के लिए कुछ गुंजाइश देता है। पहले, चलो अंतिम चर का लाभ उठाने की कोशिश करते हैं। यह ज्ञात है कि जब मूल कोड में संकलित किया जाता है, तो उन्हें सीधे मूल्यों में अनुवादित किया जाता है। सैद्धांतिक रूप से, अंतिम मूल्यों के साथ मैट्रिसेस की सीमाओं को बदलने से 1000x1000x1000 बार मेमोरी एक्सेस कम हो जाएगी। इसके बजाय, मूल्यों को सीधे प्रतिस्थापित किया जाएगा। सिद्धांत की जाँच करें।

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); for (int i = 0; i < aRows; i++) { for (int j = 0; j < aColumns; j++) { double summand = 0.0; for (int k = 0; k < bColumns; k++) { summand += A[i][k] * B[k][j]; } C[i][j] = summand; } } 

एल्गोरिदम रनटाइम : 16.996 एस ;
प्रदर्शन में वृद्धि: ~ 11% ;

चरण 2. कैशे याद रखें!

वास्तव में, ऐसा कार्यान्वयन हमेशा धीरे-धीरे काम करेगा। कॉलम में मैट्रिक्स बी के तत्वों को संदर्भित करता है "के" पर Iteration। इस तरह की रीडिंग बहुत महंगी है, क्योंकि प्रोसेसर को हर बार मेमोरी से डेटा को प्रीफ़ेक करना पड़ता है, बजाय इसे कैश से तैयार करने के।

उल्लेखनीय है कि फोरट्रान को ऐसी कोई समस्या नहीं है। इसमें बहुआयामी सरणियों को कॉलम में संग्रहीत किया जाता है। इसलिए, कैश को ठीक से संचालित किया जाएगा और क्यूबिक एल्गोरिदम का मानक कार्यान्वयन कई गुना तेजी से काम करेगा।

विचाराधीन प्लेटफॉर्म पर, पहले स्तर (एल 1) की कैश लाइन का आकार - 64 बाइट्स - यह प्रोसेसर के लिए सबसे सस्ती मेमोरी है। हमारे मामले में, लगभग मुफ्त मेमोरी के 64 बाइट्स प्रीफ़ैचिंग से ओवरहेड द्वारा पीछा किए जाने के स्थान पर 8 मैट्रिक्स कोशिकाओं (साइज़ोफ़ (डबल) = 8) के रूप में कई प्राप्त करने की क्षमता देते हैं।

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

आइए, इसे ठीक करने और मैट्रिक्स तत्वों तक अनुक्रमिक पहुंच को लागू करने का प्रयास करें ताकि कैश का अधिकतम लाभ मिल सके। ऐसा करने के लिए, बस मैट्रिक्स बी को स्थानांतरित करें और हम इसके तत्वों को पंक्ति द्वारा संदर्भित करेंगे।

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double BT[][] = new double[bColumns][bRows]; for (int i = 0; i < bRows; i++) { for (int j = 0; j < bColumns; j++) { BT[j][i] = B[i][j]; } } for (int i = 0; i < aRows; i++) { for (int j = 0; j < aColumns; j++) { double summand = 0.0; for (int k = 0; k < bColumns; k++) { summand += A[i][k] * BT[j][k]; } C[i][j] = summand; } } 

एल्गोरिदम रनटाइम : 7.334 एस ;
प्रदर्शन में वृद्धि: ~ 232% ;

चरण 3. सोचो!

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

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double thatColumn[] = new double[bRows]; for (int j = 0; j < bColumns; j++) { for (int k = 0; k < aColumns; k++) { thatColumn[k] = B[k][j]; } for (int i = 0; i < aRows; i++) { double thisRow[] = A[i]; double summand = 0; for (int k = 0; k < aColumns; k++) { summand += thisRow[k] * thatColumn[k]; } C[i][j] = summand; } } 

एल्गोरिदम रनटाइम : 3.976 एस ;
प्रदर्शन में वृद्धि: ~ 190% ;

चरण 4. दूर फेंक दो!

हम जावा - अपवादों का एक और फायदा उठाते हैं। आइए, {} कैच {} ब्लॉक के साथ मैट्रिक्स की सीमाओं से परे जाने के लिए चेक को बदलने का प्रयास करें। यह हमारे मामले में तुलनात्मक संख्या को 1000 तक कम कर देगा। वास्तव में, क्यों 1000 बार की तुलना करें जो हमेशा झूठे लौटेंगे और 1001 बार सच लौटेंगे।

एक तरफ - हम तुलनाओं की संख्या को कम करते हैं, दूसरे पर - अपवादों को संभालने के लिए अतिरिक्त ओवरहेड है। एक तरीका या दूसरा, यह दृष्टिकोण कुछ वृद्धि देता है।

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double thatColumn[] = new double[bRows]; try { for (int j = 0; ; j++) { for (int k = 0; k < aColumns; k++) { thatColumn[k] = B[k][j]; } for (int i = 0; i < aRows; i++) { double thisRow[] = A[i]; double summand = 0; for (int k = 0; k < aColumns; k++) { summand += thisRow[k] * thatColumn[k]; } C[i][j] = summand; } } } catch (IndexOutOfBoundsException ignored) { } 

एल्गोरिदम रनटाइम: 3.594 एस ;
प्रदर्शन में वृद्धि: ~ 10% ;

चरण 5. मत रोको!

इस स्तर पर, मैं अभी के लिए रुक गया हूं, क्योंकि मैं वांछित लक्ष्य तक पहुंच गया हूं। मेरा लक्ष्य मैट्रिस के साथ काम करने के लिए सबसे लोकप्रिय पुस्तकालय से आगे निकल जाना था - जेएएमए ("जावा मैट्रिक्स" के लिए Google में पहली पंक्ति)। अब मेरा कार्यान्वयन JAMA की तुलना में लगभग 30% तेज काम करता है। इसके अलावा, अपेक्षाकृत छोटे अनुकूलन में शुरुआती संस्करण के सापेक्ष लगभग 600% की वृद्धि हुई।

निष्कर्ष के बजाय (यह एक विज्ञापन नहीं है)

कोड की समीक्षा खुले स्रोत laj4 परियोजना का हिस्सा है। यह जावा में रैखिक बीजगणित की समस्याओं को हल करने के लिए एक पुस्तकालय है। मैंने कम्प्यूटेशनल गणित में एक पाठ्यक्रम का अध्ययन करने की प्रक्रिया में 4 वें वर्ष में परियोजना पर काम करना शुरू कर दिया। अब la4j उत्कृष्ट प्रदर्शन दिखाता है और कई कार्यों पर अपने समकक्षों की तुलना में कई गुना तेजी से काम करता है।

अगर कोई दिलचस्पी रखता है और इस तरह से शाम बिताना चाहता है - एक व्यक्तिगत में लिखें :)