कैश इलाके के साथ सी फ़ंक्शन प्रदर्शन में सुधार करें?

Question

मैं एक मैट्रिक्स 2 डी सरणी और समारोह प्रोटोटाइप के रूप में प्रतिनिधित्व में एक विकर्ण अंतर खोजने के लिए

int diagonal_diff(int x[512][512]) 

मैं एक 2d सरणी का उपयोग करना है, और डेटा 512x512 है। यह एक एसपीएआरसी मशीन पर परीक्षण किया जाता है: मेरा वर्तमान समय 6ms है लेकिन मुझे 2ms से कम होने की आवश्यकता है।

नमूना डेटा:

[3][4][5][9] 
[2][8][9][4] 
[6][9][7][3] 
[5][8][8][2] 

अंतर है:

|4-2| + |5-6| + |9-5| + |9-9| + |4-8| + |3-8| = 2 + 1 + 4 + 0 + 4 + 5 = 16 

आदेश है कि, मैं निम्नलिखित कलन विधि का उपयोग करने के लिए:

int i,j,result=0; 
for(i=0; i<4; i++) 
    for(j=0; j<4; j++) 
     result+=abs(array[i][j]-[j][i]); 

return result; 

लेकिन इस एल्गोरिथ्म तक पहुँचने रहता है कॉलम, पंक्ति, कॉलम, पंक्ति, आदि जो कैश का अक्षम उपयोग करते हैं।

मेरे कार्य में सुधार करने के लिए एक रास्ता है?

Answer 1

संपादित करें: ब्लॉक उन्मुख दृष्टिकोण तेजी से क्यों है? हम यह सुनिश्चित करके सीपीयू के डेटा कैश का लाभ उठा रहे हैं कि क्या हम पंक्ति या कॉलम द्वारा ब्लॉक पर फिर से प्रयास करते हैं, हम गारंटी देते हैं कि पूरा ब्लॉक कैश में फिट बैठता है।

उदाहरण के लिए, यदि आपके पास 32-बाइट्स की कैश लाइन है और int 4 बाइट्स है, तो आप 8 कैश लाइनों में 8x8 int मैट्रिक्स फिट कर सकते हैं। मान लीजिए कि आपके पास पर्याप्त डेटा कैश है, आप पंक्ति या कॉलम द्वारा उस मैट्रिक्स पर फिर से सक्रिय हो सकते हैं और गारंटी दी जाती है कि आप कैश को नहीं फेंकते हैं। इसके बारे में सोचने का एक और तरीका यह है कि यदि आपका मैट्रिक्स कैश में फिट बैठता है, तो आप इसे किसी भी तरह से पार कर सकते हैं।

आप एक मैट्रिक्स है कि बहुत बड़ा है, तो 512x512 तो आप धुन अपने मैट्रिक्स ट्रेवर्सल ऐसी है कि आप कैश पिटाई नहीं है की जरूरत है कहते हैं,। उदाहरण के लिए, यदि आप मैट्रिक्स के लेआउट के विपरीत क्रम में मैट्रिक्स को पार करते हैं, तो आप लगभग हर तत्व पर कैश को हमेशा याद करेंगे।

एक ब्लॉक उन्मुख दृष्टिकोण सुनिश्चित करता है कि आप केवल एक कैश याद आती है डेटा के लिए आप अंततः का दौरा करेंगे पहले सीपीयू कि कैश लाइन फ्लश करने के लिए है है। दूसरे शब्दों में, कैश लाइन आकार में ट्यून किए गए ब्लॉक उन्मुख दृष्टिकोण से यह सुनिश्चित होगा कि आप कैश को नहीं फेंक दें।

इसलिए, यदि आप मशीन आप पर चल रहे हैं की कैश लाइन आकार के लिए अनुकूलन करने के लिए कोशिश कर रहे हैं, तो आप ब्लॉक के रूप में मैट्रिक्स से अधिक पुनरावृति और सुनिश्चित करें कि आप केवल एक बार प्रत्येक मैट्रिक्स तत्व पर जा सकते हैं:

int sum_diagonal_difference(int array[512][512], int block_size) 
{ 
    int i,j, block_i, block_j,result=0; 

    // sum diagonal blocks 
    for (block_i= 0; block_i<512; block_i+= block_size) 
     for (block_j= block_i + block_size; block_j<512; block_j+= block_size) 
      for(i=0; i<block_size; i++) 
       for(j=0; j<block_size; j++) 
        result+=abs(array[block_i + i][block_j + j]-array[block_j + j][block_i + i]); 

    result+= result; 

    // sum diagonal 
    for (int block_offset= 0; block_offset<512; block_offset+= block_size) 
    { 
     for (i= 0; i<block_size; ++i) 
     { 
      for (j= i+1; j<block_size; ++j) 
      { 
       int value= abs(array[block_offset + i][block_offset + j]-array[block_offset + j][block_offset + i]); 
       result+= value + value; 
      } 
     } 
    } 

    return result; 
} 

आपको block_size के लिए विभिन्न मानों के साथ प्रयोग करना चाहिए। मेरी मशीन पर, 8 सबसे बड़ी गति को (2.5x) के नेतृत्व में 1 की block_size (और ~ 5x पूरे मैट्रिक्स से अधिक मूल पुनरावृति की तुलना में) की तुलना में। block_size आदर्श रूप से cache_line_size_in_bytes/sizeof(int) होना चाहिए।

Answer 2

एक मामूली परिवर्तन के साथ आप अपने छोरों केवल वांछित सूचकांक पर काम हो सकता है। मैंने अभी j लूप प्रारंभिकता बदल दी है।

int i, j, result = 0; 
for (i = 0; i < 4; ++i) { 
    for (j = i + 1; j < 4; ++j) { 
     result += abs(array[i][j] - array[j][i]); 
    } 
} 

Answer 3

आप इंटेल MKL की तरह एक अच्छा वेक्टर/मैट्रिक्स पुस्तकालय है, तो भी vectorized तरह से प्रयास करें।

matlab में बहुत सरल: परिणाम = योग (योग (abs (x-x ')));

मैं भी matlab में हंस की विधि और MSN की विधि पुन: उत्पादित, और परिणाम हैं:

Elapsed time is 0.211480 seconds. (Hans) 

Elapsed time is 0.009172 seconds. (MSN) 

Elapsed time is 0.002193 seconds. (Mine)