🔯 👨‍👩‍👦 ✨ अनुकूलन तकनीकों के बारे में 👨‍⚕️ ⚒️ 🗞️

अनुकूलन तकनीकों के बारे में एक शिक्षाप्रद कहानी स्पष्ट है।

संदर्भ की शर्तें

विषय के भाग के रूप में, हम वास्तुकला-उन्मुख सॉफ्टवेयर अनुकूलन के लिए एक छोटी प्रतियोगिता की घोषणा करेंगे।

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

मूल कोड निष्पादित ... किया गया

निष्पादित कोड अनुकूलित किया गया ... किया गया

परिणामों की जाँच कर रहा है ... पास किया गया

रन की संख्या: 3

मूल कोड औसत समय: 11.954537 सेकंड।

अनुकूलित कोड औसत समय: 1.052994 सेकंड।

स्पीडअप: 11.35

यह किसी भी अनुकूलन तकनीक, किसी भी विकल्प के साथ एक जीसीसी संकलक का उपयोग करने की अनुमति है, और कहते हैं, दो क्वाड-कोर इंटेल Xeon E5420 2.5 गीगाहर्ट्ज प्रोसेसर वाले सर्वर।

यहाँ, वैसे, कोड है:

/* * contestopt.c: */ #include "contest.h" void function3( double a[][NUM], double b[][NUM], double c[][NUM]); void function2( double a[][NUM]); double function4(unsigned int second); double ***p; double ****x; double ****y; double ****z; double ***wrk1; double ***wrk2; double ***bnd; static double a[NUM][NUM], b[NUM][NUM]; void function1( double result[][NUM], double gos[2], unsigned int second) { function2(a); function2(b); function3(a, b, result); gos[0] = function4(second); } void function3( double a[][NUM], double b[][NUM], double result[][NUM]) { int i, j, k; for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { for (k = 0; k < NUM; k++) { result[i][j] = result[i][j] + a[i][k] * b[k][j]; } } } } void function2( double a[][NUM]) { int i, j; double first = 0.0; double second = 1.0; a[0][0] = first; a[0][1] = second; for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { if (!(i == 0 && (j == 0 || j == 1))) { a[i][j] = first + second; first = second; second = a[i][j]; } if (j % 20 == 0 && j != 0) { first = first * (j + 1) / (NUM); second = second * (j + 1) / (NUM); } } first = ((i + 1) * NUM) / first; second = ((i + 1) * NUM) / second; } } void function5( double ***A, double val) { int i, j, k; for (i = 0; i < XX; i++) for (j = 0; j < YY; j++) for (k = 0; k < ZZ; k++) A[i][j][k] = val; } void function6(unsigned int second) { int mimax = XX; int mjmax = YY; int mkmax = ZZ; int imax = mimax - 1; int jmax = mjmax - 1; int kmax = mkmax - 1; int i, j, k, l; double val; srand((unsigned int ) second); p = ( double ***) malloc( sizeof ( double **) * XX); wrk1 = ( double ***) malloc( sizeof ( double **) * XX); wrk2 = ( double ***) malloc( sizeof ( double **) * XX); bnd = ( double ***) malloc( sizeof ( double **) * XX); x = ( double ****) malloc( sizeof ( double ***) * XX); y = ( double ****) malloc( sizeof ( double ***) * XX); z = ( double ****) malloc( sizeof ( double ***) * XX); for (i = 0; i < XX; i++) { p[i] = ( double **) malloc( sizeof ( double *) * YY); wrk1[i] = ( double **) malloc( sizeof ( double *) * YY); wrk2[i] = ( double **) malloc( sizeof ( double *) * YY); bnd[i] = ( double **) malloc( sizeof ( double *) * YY); x[i] = ( double ***) malloc( sizeof ( double **) * YY); y[i] = ( double ***) malloc( sizeof ( double **) * YY); z[i] = ( double ***) malloc( sizeof ( double **) * YY); for (j = 0; j < YY; j++) { p[i][j] = ( double *) malloc( sizeof ( double ) * ZZ); wrk1[i][j] = ( double *) malloc( sizeof ( double ) * ZZ); wrk2[i][j] = ( double *) malloc( sizeof ( double ) * ZZ); bnd[i][j] = ( double *) malloc( sizeof ( double ) * ZZ); x[i][j] = ( double **) malloc( sizeof ( double *) * ZZ); y[i][j] = ( double **) malloc( sizeof ( double *) * ZZ); z[i][j] = ( double **) malloc( sizeof ( double *) * ZZ); for (k = 0; k < ZZ; k++) { x[i][j][k] = ( double *) malloc( sizeof ( double ) * 4); y[i][j][k] = ( double *) malloc( sizeof ( double ) * 3); z[i][j][k] = ( double *) malloc( sizeof ( double ) * 3); } } } val = ( double ) rand() / (10.0 * RAND_MAX); for (i = 0; i < XX; i++) for (j = 0; j < YY; j++) for (k = 0; k < ZZ; k++) { for (l = 0; l < 3; l++) { x[i][j][k][l] = 1.0; y[i][j][k][l] = val; z[i][j][k][l] = 1.0; } x[i][j][k][3] = 1.0; } function5(bnd, 1.0); function5(wrk1, 0.0); function5(wrk2, 0.0); for (i = 0; i < imax; i++) for (j = 0; j < jmax; j++) for (k = 0; k < kmax; k++) p[i][j][k] = ( double ) (k * k) / ( double ) (kmax * kmax); } void function7() { int i, j, k; for (i = 0; i < XX; i++) { for (j = 0; j < YY; j++) { free(p[i][j]); free(wrk1[i][j]); free(wrk2[i][j]); free(bnd[i][j]); for (k = 0; k < ZZ; k++) { free(x[i][j][k]); free(y[i][j][k]); free(z[i][j][k]); } free(x[i][j]); free(y[i][j]); free(z[i][j]); } free(p[i]); free(wrk1[i]); free(wrk2[i]); free(bnd[i]); free(x[i]); free(y[i]); free(z[i]); } free(x); free(y); free(z); free(p); free(wrk1); free(wrk2); free(bnd); } double function4(unsigned int second) { int nn = NN; double gosa, s0, ss; int mimax = XX; int mjmax = YY; int mkmax = ZZ; int imax = mimax - 1; int jmax = mjmax - 1; int kmax = mkmax - 1; int iCount, jCount, kCount, loop, i, j, k; function6(second); for (loop = 0; loop < nn; loop++) { gosa = 0.0; for (k = 1; k < kmax - 1; k++) for (j = 1; j < jmax - 1; j++) for (i = 1; i < imax - 1; i++) { s0 = x[i][j][k][0] * p[i + 1][j][k] + x[i][j][k][1] * p[i][j][k] + x[i][j][k][2] * p[i][j][k] + y[i][j][k][0] * (p[i + 1][j + 1][k] - p[i + 1][j - 1][k] - p[i - 1][j + 1][k] + p[i - 1][j - 1][k]) + y[i][j][k][1] * (p[i][j + 1][k + 1] - p[i][j - 1][k + 1] - p[i][j + 1][k - 1] + p[i][j - 1][k - 1]) + y[i][j][k][2] * (p[i + 1][j][k + 1] - p[i - 1][j][k + 1] - p[i + 1][j][k - 1] + p[i - 1][j][k - 1]) + z[i][j][k][0] * p[i - 1][j][k] + z[i][j][k][1] * p[i][j - 1][k] + z[i][j][k][2] * p[i][j][k - 1] + wrk1[i][j][k]; ss = (s0 * x[i][j][k][3] - p[i][j][k]) * bnd[i][j][k]; gosa = gosa + ss; wrk2[i][j][k] = p[i][j][k] + 0.1 * ss; } for (iCount = 1; iCount < imax - 1; iCount++) for (jCount = 1; jCount < jmax - 1; jCount++) for (kCount = 1; kCount < kmax - 1; kCount++) p[iCount][jCount][kCount] = wrk2[iCount][jCount][kCount]; } function7(); return gosa; } double exponent( int i, double x) { double z = 1.0; int j; for (j = 0; j < i; j++) { z = z * x; } return z; } double function8( float *a, float p) { int i, j; double h, x; double s = p; h = 1.0 / VAL; for (i = 1; i <= VAL; i++) { x = h * (i - 0.5); for (j = 0; j < ORDER; j++) { s = (a[j] * exponent(j, x)) + s; } } return s * h; } * This source code was highlighted with Source Code Highlighter .

मूल्यों पर परीक्षण किया गया:

# डेफिन NUM 600

# डेफिन XX 65

# डेफिन YY 33

# डेफिन जेडजेड 33

# डेफिन एनएन 50

# डेफिन वैल 10000000

# डेफ़िन ओडर 30

# डेफिन टोलेरेंस 1e-8

ड्राइवर का एक अनुमानित प्रकार:

/* * driver.c: Contest driver. */ #include <sys/time.h> #include <stdio.h> #include <stdlib.h> #include <inttypes.h> #include <time.h> #include "contest.h" #include "hpctimer.h" double _RES[NUM][NUM] = { 0.0 }; double _GOS[2] = { 0.0, 0.0 }; double RES[NUM][NUM] = { 0.0 }; double GOS[2] = { 0.0, 0.0 }; float A[ORDER] = { 0.0 }; double function8( float *a, float p); void function1( double result[][NUM], double gos[2], unsigned int second); int is_results_eq( double _res[][NUM], double _gos[2], float _p, double res[][NUM], double gos[2], float p) { int i, j; if (fabsf(_p - p) > 1E-1) { printf( "_p p\n" ); printf( "%f\n" , _p); printf( "%f\n" , p); return 0; } if (fabs(_gos[0] - gos[0]) > 1E-1) { printf( "_gos gos\n" ); printf( "%f\n" , _gos[0]); printf( "%f\n" , gos[0]); return 0; } for (i = 0; i < NUM; i++) for (j = 0; j < NUM; j++) { if (fabs(_RES[i][j] - RES[i][j]) > TOLERANCE) { printf( "[%d, %d] =\n%f\n%f\n" , i, j, _RES[i][j], RES[i][j]); return 0; } } return 1; } int main( int argc, char **argv) { unsigned int second; unsigned int i, j; float p = 9.0; double _res, res; int nruns = 3; hpctimer_time_t t0, t1; double torig = 0.0, topt = 0.0; srand(time(NULL)); second = 1219304613 + (1000 - (2000.0 * ( double ) rand() / ( double ) (RAND_MAX + 1.0))); for (i = 0; i < ORDER; i++) { A[i] = ( float )i; } for (i = 0; i < NUM; i++) { for (j = 0; j < NUM; j++) { _RES[i][j] = 0.0; RES[i][j] = 0.0; } } /* Original code */ printf( "Executing original code ... " ); fflush(stdout); t0 = hpctimer_gettime(); for (i = 0; i < nruns; i++) { _function1(_RES, _GOS, second); _res = _function8(A, p); } t1 = hpctimer_gettime(); torig = hpctimer_getdiff(t0, t1) / nruns; printf( "done\n" ); fflush(stdout); /* Optimized code */ printf( "Executing optimized code ... " ); fflush(stdout); t0 = hpctimer_gettime(); for (i = 0; i < nruns; i++) { function1(RES, GOS, second); res = function8(A, p); } t1 = hpctimer_gettime(); topt = hpctimer_getdiff(t0, t1) / nruns; printf( "done\n" ); fflush(stdout); printf( "Checking results ... " ); fflush(stdout); if (!is_results_eq(_RES, _GOS, _res, RES, GOS, res)) { printf( "RESULTS ARE DIFFERENT!\n" ); } else { printf( "PASSED\n" ); printf( "Number of runs: %d\n" , nruns); printf( "Original code average time: %.6f sec.\n" , torig); printf( "Optimized code average time: %.6f sec.\n" , topt); printf( "Speedup: %.2f\n" , torig / topt); } return 0; } * This source code was highlighted with Source Code Highlighter .

त्वरण, नियम एक

स्रोत कोड स्तर पर अनुकूलन के बारे में कोई भी कह सकता है: "इससे कोई फर्क नहीं पड़ता कि कोड क्या करता है - यह मायने रखता है कि यह कैसे करता है।" लेकिन पहला अनुकूलन नियम जो मैं लेकर आया था वह इस कथन के विपरीत है:

पहला नियम

धूम्रपान करने वाले मैटरियल और एल्गोरिदम

पहली नज़र में कोड के लिए, यह स्पष्ट हो जाता है कि वह गुदा के माध्यम से कुछ सरल क्रियाएं करता है।

तो, यहां तक कि एक सरसरी नज़र भी घातांक के साथ घातांक फ़ंक्शन को काटने के लिए पर्याप्त है, जो महत्वपूर्ण इशारों की संख्या निर्धारित करता है (कुछ प्रोफाइलर चलाकर, आप पा सकते हैं कि यह कुल गिनती के समय का 80% खाता है)। जिस एक्सपोजर से वह निपटती है वह आसानी से फ़ंक्शन 8 में गतिशील रूप से कार्यान्वित होता है।

फ़ंक्शन 8 में ही, इंटीग्रल की गणना अवचेतन रूप से देखी जाती है, लेकिन हम बाद में इसके अनुकूलन की गुंजाइश पर चर्चा करेंगे।

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

फ़ंक्शन 3 में मैट्रिक्स गुणन कई अलग-अलग तरीकों से त्वरित होता है, लेकिन पहले चरण में यह ध्यान देने के लिए पर्याप्त है कि गुणा मैट्रिक्स बिल्कुल समान हैं, और इस फ़ंक्शन में खर्च की गई मेमोरी को आधा कर देते हैं। और यहां तक कि मैट्रिक्स को स्क्वॉयर करने के लिए सुरुचिपूर्ण एल्गोरिदम भी। मैं स्ट्रैसेन, कोपरस्मिथ-विनोह्राद और अन्य पर्चों के बारे में बात नहीं कर रहा हूं।

त्वरण, नियम दो

मुझे पता नहीं है कि क्या कोड के लेखक ने इसमें अतिरेक किया है, लेकिन प्राप्त त्वरण का मुख्य भाग दूसरे नियम के कारण है:

दूसरा नियम

डेटा संरचनाओं को नष्ट करें जो सार्थक नहीं हैं

नियम, वैसे, सुंदर है, और यह न केवल अनुकूलन पर, बल्कि पठनीयता और बेहतर संकलन पर भी काम करता है। तर्कसंगत रूप से एक अद्भुत महिला को उद्धृत करते हुए, "पुनरावृत्ति का उपयोग करने का कोई मतलब नहीं है जहां यह कोई मतलब नहीं है"।

इस अर्थ में, function4 को अभद्रता के लिए लोड किया जाता है। चार आयामी सरणियों x, y और z को कैसे आरम्भ किया जाता है, यह जानने के लिए भयभीत होकर उन्हें तुरंत नष्ट कर दें। उनका पालन wrk1 और bnd द्वारा किया जा सकता है। मैं इस तरह के trifles के बारे में बात नहीं कर रहा हूँ जैसे कि mimax, iCount, ss और अन्य अतिरिक्त। नतीजतन, कोड बहुत कम और अधिक सौंदर्य हो जाता है।

फ़ंक्शन 6 और फ़ंक्शन 7 पूरी तरह से समाप्त हो जाते हैं, उपयोगी कार्यों के अवशेष फ़ंक्शन 4 को या तो तार्किक या समय पर लोड नहीं करेंगे, इसलिए वे दर्द रहित रूप से इसे स्थानांतरित कर रहे हैं। फ़ंक्शन 5 अचानक स्वयं को नष्ट कर देता है। फ़ंक्शन 3 में, जैसा कि पहले ही उल्लेख किया गया है, आप एक स्रोत मैट्रिक्स का उपयोग कर सकते हैं, और फ़ंक्शन 2 को एक बार बुलाया जा सकता है।

यह पहले से ही साँस लेने में बहुत आसान है, और परिणामस्वरूप स्पीडअप कारनामों को प्रेरित करना शुरू कर देता है।

त्वरण, नियम तीन

तीसरा नियम

रूपांतरण भविष्यवाणी त्रुटियों को कम करें

मैं अब सब कुछ समझाता हूँ। यह एक शाखा अनुकूलन तकनीक है। संकलित लूप या शाखा ऑपरेटर कुछ इस तरह दिखता है (बहुत सरलीकृत):

1 mov eax, ebx 
      

        
        
        
      

     2 jne $a 
      

        
        
        
      

     3 mov ecx, ebx 
      

        
        
        
      

     4 jmp b 
      

        
        
        
      

     5 a: ... 
      

        
        
        
      

     6 b: ...

कल्पना कीजिए कि इस समय पाइपलाइन में क्या हो रहा है। निर्देश कई चरणों में संसाधित किए जाते हैं (फ़ेच - डिकोड - एक्ज़्यूट - राइट-बैक), और निर्देश 2 को लोड करने के बाद, संक्रमण भविष्यवाणी मॉड्यूल को काम करना चाहिए, क्योंकि हम अभी तक इस ऑपरेशन के परिणाम को नहीं जानते हैं और अगले एक का चयन नहीं कर सकते हैं।

क्या होता है जब संक्रमण पूर्वानुमान मॉड्यूल "गलत" होता है? यह सही है - कन्वेयर अनलोडिंग है। और यह ओवरहेड है। हम संक्रमण पूर्वानुमान मॉड्यूल में त्रुटियों की संख्या को कम करके इसकी संख्या को कम कर सकते हैं।

कैसे?

शाखाओं की शुरुआत में सबसे संभावित शाखाओं को रखें
उच्चतर (छोरों में घोंसले के शिकार के मामले में) अपरिवर्तनीय शाखाएं बनाएं
लूप अपरिवर्तन का उपयोग करें

मुझे अंतिम समझाएं: यदि इसके बजाय

for (i = 0; i < n; i++) { sum += p[i]; }

लिखना

for (i = 0; i < n; i+=4) { sum += p[i]; sum += p[i + 1]; sum += p[i + 2]; sum += p[i + 3]; }

हम संक्रमण की भविष्यवाणियों की संख्या को चार गुना कम कर देंगे।

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

फ़ंक्शन 3 के अनुकूलित संस्करण में लूप अनफॉलोिंग का एक उदाहरण देखा जा सकता है।

अक्रियाशील शाखाओं के चक्रों से निष्कासन को जोड़ना अच्छा होगा, जो फ़ंक्शन 2 में बहुत ही सरल हैं, लेकिन उन्हें वहां से खरोंच करना इतना आसान नहीं है। मुझसे बेहतर कौन लागू करता है - अच्छा किया।

पढ़ने के लिए: आर। गेरबर, ए। बिल "सॉफ्टवेयर अनुकूलन: व्यंजनों का संग्रह । " 2010, इंटेल

त्वरण नियम चार

चौथा नियम

स्मृति के साथ कुशलता से काम करें

विशेष रूप से, कैश मेमोरी के साथ। लिंक की स्थानीयता की ऐसी संपत्ति है - समान वस्तुओं को बार-बार / अक्सर एक्सेस करने के कार्यक्रमों की संपत्ति; और एक अस्थायी (टेम्पोरल) स्थानीयकरण और स्थानिक (स्थानिक) स्थानीयकरण है। कैशिंग प्रीमेप्टिव है, और इस आधार पर, कैश मिस से बचने के लिए धारावाहिक पते से संपर्क करना समझ में आता है।

एक ही मैट्रिक्स गुणा में, पंक्ति क्रमिक रूप से मेमोरी में स्थित है, और कॉलम बिखरा हुआ है, और दूसरे मैट्रिक्स का ट्रांसपोज़ेशन ज्ञात त्वरण प्रभाव देता है।

अब जब मैंने बात की है, तो मैं आपको एक उदाहरण देता हूं: यदि संरचना (संरचना) कैश में फिट नहीं होती है और इसके अंदर एक सरणी होती है, तो संरचना में एक सरणी के बजाय - संरचनाओं के एक सरणी का उपयोग करना बेहतर होता है।

और यह भी, एक पोर्टेबल प्रोग्राम लिखने के लिए, कैश के आकार से संलग्न न हों।

और कई अन्य सूक्ष्मताएं। पढ़ें - क्रिस कैसपर्सकी "सॉफ्टवेयर अनुकूलन तकनीक। स्मृति का कुशल उपयोग । ” 2003, बीएचवी-पीटर्सबर्ग

त्वरण नियम पांच

हमारे पास क्या प्रोसेसर वास्तुकला है?

पांचवां नियम

जहां संभव हो वहां गणनाएं करें

यह एसएसई का उपयोग करने का समय है, सौभाग्य से, आप लगभग किसी भी कोड को वेक्टर के साथ काम कर सकते हैं।

एक छोटा सा शैक्षिक कार्यक्रम।

SSE आर्किटेक्चर (x86):

MMX - पूर्णांक वेक्टर प्रसंस्करण (64-बिट रजिस्टर)
SSE - वास्तविक और पूर्णांक वैक्टर (128 बिट्स) के साथ कार्य करें

निर्देश स्केलर के साथ-साथ पैक्ड वैक्टर के साथ काम कर सकते हैं। उदाहरण के लिए:

 mulss xmm1, xmm0 | mulps xmm1, xmm0 XMM0 4.0 3.0 2.0 1.0 | 4.0 3.0 2.0 1.0 * | * * * * XMM1 5.0 5.0 5.0 5.0 | 5.0 5.0 5.0 5.0 = | = = = = XMM1 4.0 3.0 2.0 5.0 | 20.0 15.0 10.0 5.0

SSE निर्देश कॉपी, अंकगणित, तुलना, बिटवाइज़ ऑपरेशन्स और सभी प्रकार के ट्रिकी रूपांतरणों को कॉपी कर सकते हैं।

उनका उपयोग कैसे करें? कोडांतरक वेक्टर निर्देश हैं, विशेष C ++ वर्ग हैं, सब के बाद, स्वचालित वेक्टराइजेशन है - सबसे पोर्टेबल। मैं आंतरिक का उपयोग करना चाहता था।

इंट्रिंसिक्स एसएसई निर्देशों को उच्च-स्तरीय पहुंच प्रदान करने के लिए कंपाइलर द्वारा समर्थित कार्यों और डेटा प्रकारों का एक समूह है।

हम xmmintrin.h कनेक्ट करते हैं, एक वेक्टर कोड लिखते हैं, -msse3 ध्वज के साथ संकलित करते हैं। कंपाइलर XMM # रजिस्टर, शेड्यूल कमांड और एड्रेसिंग मोड आवंटित करता है। सुविधाजनक, सहज ज्ञान युक्त सरल।

उदाहरण के लिए, एक निर्देश के साथ चार फ्लोट संख्याएं जोड़ें:

#include <xmmintrin.h> void add( float *a, float *b, float *c) { __mm128 t0, t1; t0 = _mm_load_ps(a); t1 = _mm_load_ps(b); t0 = _mm_add_ps(t0, t1); _mm_store_ps(c, t0); }

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

इस स्तर पर, कोड सपने देखना शुरू कर देता है, और प्रत्येक ऑपरेटर एक मोटे चक्र से कट कर उत्पादकता में एक ठोस छलांग देता है।

त्वरण, नियम छह

सीमा की स्थिति देखें। जहाँ संभव हो वहाँ डेटा संरचनाओं को सरल से बदलें। उन समस्याओं की संगणना कम करें जिनके लिए तेज़ एल्गोरिदम मौजूद हैं।

छठा नियम

मस्क का उपयोग करें

चालक में, मैट्रिक्स गुणन के परिणामों की तुलना TOLERANCE से की जाती है, और अन्य दो संख्याएं दसवीं तक सटीक होती हैं। वैज्ञानिक प्रहार विधि का उपयोग करते हुए, यह पता चलता है कि फ़ंक्शन 8 में, अंतराल के दो तिहाई आवश्यक सटीकता प्राप्त करने के लिए पर्याप्त है, और पहले तीन मिलियन (बस कुछ) पुनरावृत्तियों को त्याग दिया जा सकता है। इसके अलावा, यह हर छह-सात हजारवें पुनरावृत्ति को ध्यान में रखने के लिए पर्याप्त है।

हमें मिलता है

double function8( float *a, float p) { int i, j, val, step; double h, x, z; double s = p; h = 1.0 / VAL; val = 0.33 * VAL; step = val / 500; for (i = val; i <= VAL; i += step) { x = h * i; z = 1.0; for (j = 1; j < ORDER; j++) { z *= x; s += j * z; } } return s * h * step; }

और आनन्द मनाओ। क्या आपको यह पसंद है? मैं नहीं करता आप के लिए पूरी तरह से घातांक के संचालन से छुटकारा पा सकते हैं।

double function8( float *a, float p) { unsigned int j; double s = p / VAL; for (j = 0; j < ORDER; j++) { s += (a[j] / (j + 1)); } return s; }

यह O (ORDER) की जटिलता को दर्शाता है - मूल O (VAL) * O (ORDER ^ 2) की तुलना में। बर्नौली नंबरों का उपयोग करके एक ही परिणाम प्राप्त किया जा सकता है (जो इतना तुच्छ नहीं हैं, लेकिन आप अभी भी एल्गोरिथ्म लिखकर नोटिस कर सकते हैं)।

आप एक चुकता मैट्रिक्स को भरने की ख़ासियत पर ध्यान दे सकते हैं और यहां तक कि पंक्तियों में शून्य भी देख सकते हैं।

आप तीन आयामी सरणियों को एक आयामी वाले के साथ बदल सकते हैं, उन्हें संबोधित करते हुए जैसे:

m1 = (YY - 1) * (ZZ - 1); एम 2 = (जेडजेड - 1); p [i * m1 + j * m2 + k]। यह छोटी सी चाल बहुआयामी मैट्रिक्स में भरने की अनुमति देती है।

आपको छोटे कार्यों के लिए भी __inline का उपयोग करने की आवश्यकता हो सकती है।

और अधिक। चूंकि इस मामले में एक आठ-कोर मशीन उपलब्ध है, आप ओपनएमपी का उपयोग नहीं कर सकते। फ़ंक्शन 3, फ़ंक्शन 4 और फ़ंक्शन 8 के समानांतरकरण को बहुत अधिक कल्पना की आवश्यकता नहीं है। फ़ंक्शन 1 में समानांतर वर्गों का उपयोग करने की संभावना थोड़ी कम है (क्योंकि फ़ंक्शन 3 और फ़ंक्शन 4 डेटा निर्भर नहीं हैं)।

मिठाई के लिए - अनुकूलित कार्यक्रम का संस्करण। यह आदर्श होने का दिखावा नहीं करता है, लेकिन ईमानदार मुद्दों में कई सौ बार त्वरण होता है।

/* * contestopt.c: */ #include <sys/time.h> #include <omp.h> #include "contest.h" void function3( double a[][NUM], double c[][NUM]); void function2( double a[][NUM]); double function4(unsigned int second); static double p[XX][YY][ZZ] __attribute__ ((aligned(64))); static double wrk2[XX][YY][ZZ] __attribute__ ((aligned(64))); static double a[NUM][NUM] __attribute__ ((aligned(64))); void function1( double result[][NUM], double gos[2], unsigned int second) { #pragma omp parallel sections { #pragma omp section function3(a,result); #pragma omp section gos[0] = function4(second); } } void function3( double a[][NUM], double result[][NUM]) { int i, i2, j, j2, k, k2; double *restrict rres; double *restrict rmul1; double *restrict rmul2; unsigned int BS = 8; int remainder = NUM % 8; int limit = NUM - remainder; function2(a); if (!(NUM & 1)) { #pragma omp for private (k, j, i, i2, j2, k2, rres, rmul1, rmul2) for (i = 0; i < limit; i += BS) for (j = 0; j < limit; j += BS) for (k = 0; k < limit; k += BS) for (i2 = 0, rres = &result[i][j], rmul1 = &a[i][k]; i2 < BS; ++i2, rres += NUM, rmul1 += NUM) { _mm_prefetch (&rmul1[8], _MM_HINT_NTA); if (!(NUM & 1)) for (k2 = 0, rmul2 = &a[k][j]; k2 < BS; ++k2, rmul2 += NUM) { __m128d m1d = _mm_load_sd (&rmul1[k2]); m1d = _mm_unpacklo_pd (m1d, m1d); j2 = 0; __m128d m2 = _mm_load_pd (&rmul2[j2]); __m128d r2 = _mm_load_pd (&rres[j2]); _mm_store_pd (&rres[j2], _mm_add_pd (_mm_mul_pd (m2, m1d), r2)); j2 +=2; m2 = _mm_load_pd (&rmul2[j2]); r2 = _mm_load_pd (&rres[j2]); _mm_store_pd (&rres[j2], _mm_add_pd (_mm_mul_pd (m2, m1d), r2)); j2 +=2; m2 = _mm_load_pd (&rmul2[j2]); r2 = _mm_load_pd (&rres[j2]); _mm_store_pd (&rres[j2], _mm_add_pd (_mm_mul_pd (m2, m1d), r2)); j2 +=2; m2 = _mm_load_pd (&rmul2[j2]); r2 = _mm_load_pd (&rres[j2]); _mm_store_pd (&rres[j2], _mm_add_pd (_mm_mul_pd (m2, m1d), r2)); } } } else { #pragma omp for private (k, j, i, i2, j2, k2, rres, rmul1, rmul2) for (i = 0; i < limit; i += BS) for (j = 0; j < limit; j += BS) for (k = 0; k < limit; k += BS) for (i2 = 0, rres = &result[i][j], rmul1 = &a[i][k]; i2 < BS; ++i2, rres += NUM, rmul1 += NUM) { _mm_prefetch (&rmul1[8], _MM_HINT_NTA); for (k2 = 0, rmul2 = &a[k][j]; k2 < BS; ++k2, rmul2 += NUM) { for (j2 = 0; j2 < BS; j2++ ) { rres[j2] += rmul1[k2] * rmul2[j2]; } } } } if (remainder) { #pragma omp for private (i,j,k) for (i = 0; i < limit; ++i) for (k = NUM - remainder; k < NUM; ++k) for (j = 0; j < limit; ++j) result[i][j] += a[i][k] * a[k][j]; #pragma omp for private (i,j,k) for (i = limit; i < NUM; ++i) for (k = 0; k < NUM; ++k) for (j = 0; j < NUM; ++j) result[i][j] += a[i][k] * a[k][j]; #pragma omp for private (i,j,k) for (i = 0; i < limit; ++i) for (k = 0; k < NUM; ++k) for (j = limit; j < NUM; ++j) result[i][j] += a[i][k] * a[k][j]; } } void function2( double a[][NUM]) { int i, j ; double first = 0.0; double second = 1.0; __assume_aligned(a, 64); a[0][0]=first; a[0][1]=second; for (j = 2; j < NUM; j++) { a[0][j] = first + second; first = second; second = a[0][j]; if ( j%20 == 0 && j != 0) { first = first * (j + 1) / (NUM); second = second * (j + 1) / (NUM); } } first = NUM / first; second = NUM / second; for (i = 1; i < NUM; i++) { for (j = 0; j < NUM; j++) { a[i][j] = first + second; first = second; second = a[i][j]; if ( j%20 == 0 && j != 0 ) { first = first * (j + 1) / (NUM); second = second * (j + 1) / (NUM); } } first = ((i + 1) * NUM) / first; second = ((i + 1) * NUM) / second; } } __inline void function6(unsigned int second) { int imax = XX - 1; int jmax = YY - 1; int kmax = ZZ - 1; int i, j, k; double kmaxDoubled = kmax * kmax; for (k = 0; k < kmax; k++) p[0][0][k] = (k * k) / kmaxDoubled; for (i = 0; i < imax; i++) for (j = 0; j < jmax; j++) for (k = 1; k < kmax; k++) p[i][j][k] = p[0][0][k]; } double function4(unsigned int second) { int nn = NN; double gosa = 0.0, val; int imax = XX - 2; int jmax = YY - 2; int kmax = ZZ - 2; int loop, i, j, k; function6(second); srand((unsigned int )second); val = ( double ) rand() / (10.0 * RAND_MAX); for (loop = 1; loop < nn; loop++) { for (k = 1; k < kmax; k++) for (j = 1; j < jmax; j++) for (i = 1; i < imax; i++) { wrk2[i][j][k] = 0.1 * ( p[i + 1][j][k] + p[i][j][k] + val * (p[i + 1][j + 1][k] - p[i + 1][j - 1][k] - p[i - 1][j + 1][k] + p[i - 1][j - 1][k] + p[i][j + 1][k + 1] - p[i][j - 1][k + 1] - p[i][j + 1][k - 1] + p[i][j - 1][k - 1] + p[i + 1][j][k + 1] - p[i - 1][j][k + 1] - p[i + 1][j][k - 1] + p[i - 1][j][k - 1]) + p[i - 1][j][k] + p[i][j - 1][k] + p[i][j][k - 1]); } for (i = 1; i < imax; i++) for (j = 1; j < jmax; j++) for (k = 1; k < kmax; k++) p[i][j][k] += wrk2[i][j][k]; } for (k = 1; k < kmax; k++) for (j = 1; j < jmax; j++) for (i = 1; i < imax; i++) { gosa += p[i + 1][j][k] + p[i][j][k] + val * (p[i + 1][j + 1][k] - p[i + 1][j - 1][k] - p[i - 1][j + 1][k] + p[i - 1][j - 1][k] + p[i][j + 1][k + 1] - p[i][j - 1][k + 1] - p[i][j + 1][k - 1] + p[i][j - 1][k - 1] + p[i + 1][j][k + 1] - p[i - 1][j][k + 1] - p[i + 1][j][k - 1] + p[i - 1][j][k - 1]) + p[i - 1][j][k] + p[i][j - 1][k] + p[i][j][k - 1]; } return gosa; } double function8( float *a, float p) { unsigned int j; double s = 0.0; #pragma omp parallel { #pragma omp for private (j) reduction (+:s) for (j = 0; j < ORDER; j++) { s += (a[j] /(j + 1)); } } return (s + p / VAL); } * This source code was highlighted with Source Code Highlighter .

यहाँ इस तरह के एक मजेदार और बहुत उपयोगी व्यावहारिक उदाहरण है। कोड अनुकूलन योजना को सारांशित करें:

एल्गोरिथम अनुकूलन
वास्तुकला-स्वतंत्र अनुकूलन:
- समानांतर धारा I / O
- साथ में चलाना
- कुशल मेमोरी हैंडलिंग, कुशल कैशिंग
वास्तुकला-उन्मुख अनुकूलन:
- वेक्टर निर्देश
- संक्रमण भविष्यवाणी त्रुटियों की संख्या को कम करना
- प्रोसेसर निर्माताओं से पुस्तकालय का कार्य
- एक ग्राफिक्स कार्ड पर गणना करना
- आदि

और यह अभी भी दिलचस्प था। उपरोक्त Driver.c प्रोग्राम में एक भेद्यता होती है, जिसके उपयोग से बिना अधिक तनाव के हज़ारों बार त्वरण प्राप्त करना संभव है। हालांकि यह पहले से ही शोषण होगा।

आपका ध्यान देने के लिए धन्यवाद।

अनुकूलन तकनीकों के बारे में