513x513 के मैट्रिक्स को ट्रांसपोज़ करने से 512x512 की धीमी गति से मैट्रिक्स क्यों ट्रांसफर कर रहा है?

Question

विभिन्न आकारों के वर्ग मैट्रिस पर कुछ प्रयोग करने के बाद, एक पैटर्न आया। अनिवार्य रूप से, आकार 2^n के मैट्रिक्स को स्थानांतरित करने से आकार 2^n+1 आकार में से एक को स्थानांतरित करने से धीमा है। n के छोटे मूल्यों के लिए, अंतर प्रमुख नहीं है।

बिग मतभेद (कम से कम मेरे लिए) 512 के एक मूल्य से अधिक लेकिन तब हो

अस्वीकरण: मैं जानता हूँ कि समारोह वास्तव में तत्वों की डबल स्वैप की वजह से मैट्रिक्स स्थानांतरित नहीं है, लेकिन यह कोई बनाता है अंतर।

#define SAMPLES 1000 
#define MATSIZE 512 

#include <time.h> 
#include <iostream> 
int mat[MATSIZE][MATSIZE]; 

void transpose() 
{ 
    for (int i = 0 ; i < MATSIZE ; i++) 
    for (int j = 0 ; j < MATSIZE ; j++) 
    { 
     int aux = mat[i][j]; 
     mat[i][j] = mat[j][i]; 
     mat[j][i] = aux; 
    } 
} 

int main() 
{ 
    //initialize matrix 
    for (int i = 0 ; i < MATSIZE ; i++) 
    for (int j = 0 ; j < MATSIZE ; j++) 
     mat[i][j] = i+j; 

    int t = clock(); 
    for (int i = 0 ; i < SAMPLES ; i++) 
     transpose(); 
    int elapsed = clock() - t; 

    std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed/SAMPLES; 
} 

बदलने MATSIZE हमें आकार (ओह!) को बदल देता है:

कोड का पालन करता है। मैं ideone पर दो संस्करणों तैनात: - औसत 2.46 एमएस - http://ideone.com/1PV7m

आकार 513 -

• आकार 512 औसत 0.75 एमएस - http://ideone.com/NShpo

मेरी वातावरण में (एमएसवीएस 2010, पूर्ण अनुकूलन), अंतर समान है:

• आकार 512 - औसत 2.19 एमएस
• आकार 513 - औसत 0.57 एमएस

क्यों हो रहा है?

Answer 1

स्पष्टीकरण Optimizing software in C++ में एग्नेर फॉग से आता है और यह कैश में डेटा को कैसे एक्सेस और संग्रहीत किया जाता है, यह कम कर देता है।

नियम और विस्तृत जानकारी के लिए, wiki entry on caching देखें, मैं इसे यहां संकुचित कर रहा हूं।

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

एक विशेष स्मृति पता है, हम गणना कर सकते हैं जो सेट यह फार्मूले के साथ में नजर आता किया जाना है:,

set = (address/lineSize) % numberOfsets 

सूत्र इस तरह की है सेट भर में आदर्श के रूप में समान रूप से वितरित देता है क्योंकि प्रत्येक स्मृति पता पढ़ने की संभावना है (मैंने कहा आदर्श)।

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

मैं कुछ हद तक Agner से उदाहरण का अनुसरण करने की कोशिश करेंगे:

मान लें प्रत्येक सेट 4 लाइनों है, प्रत्येक 64 बाइट्स पकड़े। हम पहले 0x2710 पते को पढ़ने का प्रयास करते हैं, जो 28 सेट में जाता है। और फिर हम 0x2F00, 0x3700, 0x3F00 और 0x4700 पते पढ़ने का भी प्रयास करते हैं। ये सभी एक ही सेट के हैं। 0x4700 पढ़ने से पहले, सेट में सभी लाइनों पर कब्जा कर लिया गया होगा। पढ़ना कि स्मृति सेट में मौजूदा लाइन को बताती है, जिस पंक्ति में शुरुआत में 0x2710 था। समस्या इस तथ्य में निहित है कि हम ऐसे पते पढ़ते हैं जो (इस उदाहरण के लिए) 0x800 अलग हैं। यह महत्वपूर्ण चरण (फिर से, इस उदाहरण के लिए) है।

महत्वपूर्ण कदम भी गणना की जा सकती:

criticaStride = numberOfSets * lineSize 

चर criticalStride स्थान दिया गया है या एक से अधिक अलग ही कैश लाइनों के लिए संघर्ष।

यह सिद्धांत हिस्सा है। इसके बाद, स्पष्टीकरण (एग्नेर, मैं गलतियों से बचने के लिए इसे बारीकी से पालन कर रहा हूं):

एक 8kb कैश के साथ 64x64 (याद रखें, प्रभाव कैश के अनुसार भिन्न होते हैं) का एक मैट्रिक्स मानें, प्रति सेट 4 लाइनें * 64 बाइट्स के लाइन आकार। प्रत्येक पंक्ति में मैट्रिक्स के तत्वों में से 8 तत्व हो सकते हैं (64-बिट int)।

महत्वपूर्ण कदम 2048 बाइट्स होगा, जो मैट्रिक्स की 4 पंक्तियों (जो स्मृति में निरंतर है) के अनुरूप है।

मान लें कि हम पंक्ति 28 को संसाधित कर रहे हैं। हम इस पंक्ति के तत्वों को लेने और स्तंभ 28 से तत्वों के साथ उन्हें स्वैप करने का प्रयास कर रहे हैं। पंक्ति के पहले 8 तत्व कैश लाइन बनाते हैं, लेकिन वे कॉलम 28 में 8 अलग-अलग कैश लाइनों में जाएं। याद रखें, महत्वपूर्ण प्रगति 4 पंक्तियों को अलग करती है (कॉलम में लगातार 4 तत्व)।

जब कॉलम 16 में स्तंभ 16 तक पहुंच जाता है (4 कैश लाइन प्रति सेट & 4 पंक्तियों अलग = परेशानी) पूर्व-0 तत्व कैश से निकाल दिया जाएगा। जब हम कॉलम के अंत तक पहुंच जाते हैं, तो सभी पिछली कैश लाइनें खो जातीं और अगले तत्व तक पहुंच पर पुनः लोड करने की आवश्यकता होती है (पूरी लाइन ओवरराइट की जाती है)।

एक आकार है कि महत्वपूर्ण कदम की एक बहु नहीं है आपदा के लिए इस सही परिदृश्य को खराब करता आ रहा है, के रूप में हम अब तत्वों कि ऊर्ध्वाधर पर अलग महत्वपूर्ण कदम हैं के साथ काम कर रहे हैं, इसलिए कैश पुनः लोड की संख्या गंभीर रूप से कम हो गया है।

एक अन्य अस्वीकरण - मुझे अभी स्पष्टीकरण के आसपास अपना सिर मिला और उम्मीद है कि मैंने इसे दबाया है, लेकिन मुझे गलत हो सकता है। वैसे भी, मैं Mysticial से एक प्रतिक्रिया (या पुष्टि) की प्रतीक्षा कर रहा हूं। :)

Answer 2

Luchian का एक विवरण क्यों इस व्यवहार होता है देता है, लेकिन मैंने सोचा कि यह इस समस्या का एक संभव समाधान को दिखाने के लिए एक अच्छा विचार होगा और एक ही समय में कैश अनजान एल्गोरिदम के बारे में थोड़ा दिखा।

आपका एल्गोरिथ्म मूल रूप से करता है:

for (int i = 0; i < N; i++) 
    for (int j = 0; j < N; j++) 
     A[j][i] = A[i][j]; 

जो सिर्फ एक आधुनिक सीपीयू के लिए भयानक है। एक समाधान है कि आप अपने कैश सिस्टम के बारे में विवरण जान सकें और उन समस्याओं से बचने के लिए एल्गोरिदम को ट्विक करें। जब तक आप उन विवरणों को जानते हैं तब तक बढ़िया काम करता है .. विशेष रूप से पोर्टेबल नहीं।

क्या हम उससे बेहतर कर सकते हैं? हाँ हम कर सकते हैं: इस समस्या का एक सामान्य दृष्टिकोण cache oblivious algorithms हैं कि जैसा कि नाम से कहते हैं बचा जाता है [1]

समाधान इस प्रकार दिखाई देगा विशिष्ट कैश आकार पर निर्भर किया जा रहा है:

void recursiveTranspose(int i0, int i1, int j0, int j1) { 
    int di = i1 - i0, dj = j1 - j0; 
    const int LEAFSIZE = 32; // well ok caching still affects this one here 
    if (di >= dj && di > LEAFSIZE) { 
     int im = (i0 + i1)/2; 
     recursiveTranspose(i0, im, j0, j1); 
     recursiveTranspose(im, i1, j0, j1); 
    } else if (dj > LEAFSIZE) { 
     int jm = (j0 + j1)/2; 
     recursiveTranspose(i0, i1, j0, jm); 
     recursiveTranspose(i0, i1, jm, j1); 
    } else { 
    for (int i = i0; i < i1; i++) 
     for (int j = j0; j < j1; j++) 
      mat[j][i] = mat[i][j]; 
    } 
} 

थोड़ा और अधिक जटिल है, लेकिन आकार के प्रभाव के बारे में:: एक छोटी परीक्षण MATSIZE 8192

int main() { 
    LARGE_INTEGER start, end, freq; 
    QueryPerformanceFrequency(&freq); 
    QueryPerformanceCounter(&start); 
    recursiveTranspose(0, MATSIZE, 0, MATSIZE); 
    QueryPerformanceCounter(&end); 
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart)/(double(freq.QuadPart)/1000)); 

    QueryPerformanceCounter(&start); 
    transpose(); 
    QueryPerformanceCounter(&end); 
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart)/(double(freq.QuadPart)/1000)); 
    return 0; 
} 

results: 
recursive: 480.58ms 
iterative: 3678.46ms 

के लिए कुछ VS2010 64 रिलीज के साथ मेरी प्राचीन E8400 पर काफी रोचक, testcode संपादित चलता यह बहुत कम, हालांकि अभी भी ध्यान देने योग्य कुछ हद तक स्पष्ट है, ऐसा इसलिए है क्योंकि हम 1 (रिकर्सिव एल्गोरिदम के लिए सामान्य अनुकूलन) को रिकर्स करने के बजाए एक पत्ता नोड के रूप में पुनरावृत्त समाधान का उपयोग कर रहे हैं। अगर हम LEAFSIZE = 1 सेट करते हैं, तो कैश का मेरे लिए कोई प्रभाव नहीं पड़ता है [8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms - यह त्रुटि के मार्जिन के अंदर है, उतार-चढ़ाव 100ms क्षेत्र में हैं; यह "बेंचमार्क" ऐसा कुछ नहीं है जिसे हम पूरी तरह सटीक मान चाहते हैं, तो मैं बहुत सहज महसूस करूंगा]

[1] इस सामग्री के लिए स्रोत: ठीक है अगर आप किसी ऐसे व्यक्ति से व्याख्यान नहीं ले सकते जो काम करता है Leiserson और इस पर सह .. मैं अपने कागजात एक अच्छा प्रारंभिक बिंदु मानते हैं। उन एल्गोरिदम अभी भी बहुत ही कम वर्णित हैं - सीएलआर के बारे में उनके बारे में एक फुटनोट है। फिर भी लोगों को आश्चर्यचकित करने का यह एक शानदार तरीका है।

---

संपादित (ध्यान दें: मैं एक है जो इस उत्तर पोस्ट नहीं हूँ, मैं सिर्फ इस जोड़ना चाहते थे):
यहां एक संपूर्ण सी ++ उपरोक्त कोड का संस्करण है:

template<class InIt, class OutIt> 
void transpose(InIt const input, OutIt const output, 
    size_t const rows, size_t const columns, 
    size_t const r1 = 0, size_t const c1 = 0, 
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0, 
    size_t const leaf = 0x20) 
{ 
    if (!~c2) { c2 = columns - c1; } 
    if (!~r2) { r2 = rows - r1; } 
    size_t const di = r2 - r1, dj = c2 - c1; 
    if (di >= dj && di > leaf) 
    { 
     transpose(input, output, rows, columns, r1, c1, (r1 + r2)/2, c2); 
     transpose(input, output, rows, columns, (r1 + r2)/2, c1, r2, c2); 
    } 
    else if (dj > leaf) 
    { 
     transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2)/2); 
     transpose(input, output, rows, columns, r1, (c1 + c2)/2, r2, c2); 
    } 
    else 
    { 
     for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns); 
      i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns) 
     { 
      for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows); 
       j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows) 
      { 
       output[j2 + i1] = input[i2 + j1]; 
      } 
     } 
    } 
} 

Answer 3

Luchian Grigore's answer में स्पष्टीकरण के एक उदाहरण के रूप में, मैट्रिक्स कैश उपस्थिति 64x64 और 65x65 मैट्रिक्स के दो मामलों के लिए दिखती है (संख्याओं पर विवरण के लिए उपरोक्त लिंक देखें)। , संचय में नहीं

- -

• कैश में,
• - कैश हिट,
• - बस रैम से पढ़ें: एनिमेशन में

  रंग नीचे मतलब निम्नलिखित ,

• - कैश मिस।

64x64 मामला:

सूचना कैसे लगभग हर एक कैश याद आती है में एक नई पंक्ति परिणामों के लिए उपयोग।और अब कैसे यह सामान्य मामले के लिए लग रहा है, एक 65x65 मैट्रिक्स:

यहाँ आप देख सकते हैं कि प्रारंभिक वार्मिंग-अप के बाद पहुंच से ज्यादातर कैश हिट कर रहे हैं। इस प्रकार सीपीयू कैश का सामान्य रूप से काम करना है।