सरणी ट्रांसपोज़िंग फ़ंक्शन को अनुकूलित करना

Question

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

समस्या:

//transpose a dim x dim matrix into dist by swapping all i,j with j,i 
void transpose(int *dst, int *src, int dim) { 
    int i, j; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
    } 
} 

क्या मैं अब तक है:

//attempt 1 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id, jd; 

    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     jd = 0; 
     for(j = 0; j < dim; j++, jd+=dim) { 
       dst[jd + i] = src[id + j]; 
     } 
    } 
} 

//attempt 2 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id; 
    int *pd, *ps; 
    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     pd = dst + i; 
     ps = src + id; 
     for(j = 0; j < dim; j++) { 
       *pd = *ps++; 
       pd += dim; 
     } 
    } 
} 

कुछ विचार, मुझे सही करें यदि मैं गलत हूँ:

मैं पाश unrolling लेकिन मैं बारे में सोचा है ऐसा न सोचें कि इससे मदद मिलेगी, क्योंकि हम नहीं जानते कि एनएक्सएन मैट्रिक्स में प्रमुख आयाम हैं या नहीं। यदि मैंने इसके लिए चेक किया है, तो इसमें अतिरिक्त गणना शामिल होगी जो फ़ंक्शन को धीमा कर देगी।

कैश ब्लॉक बहुत उपयोगी नहीं होंगे, क्योंकि इससे कोई फर्क नहीं पड़ता कि हम एक सरणी को रैखिक रूप से (1,2,3,4) तक पहुंचेंगे जबकि दूसरा हम एन के कूद में पहुंचेंगे। जबकि हम प्राप्त कर सकते हैं कैश का दुरुपयोग करने और src block को तेज़ी से एक्सेस करने के लिए फ़ंक्शन, फिर भी उन्हें डीएसटी मैट्रिक्स में रखने के लिए एक लंबा समय लगेगा।

मैंने सरणी एक्सेसर्स के बजाय पॉइंटर्स का उपयोग करने का भी प्रयास किया है, लेकिन मुझे नहीं लगता कि वास्तव में प्रोग्राम को किसी भी तरह से गति देता है।

किसी भी मदद की सराहना की जाएगी।

धन्यवाद

Answer 1

कैश अवरोधन उपयोगी हो सकता है। उदाहरण के लिए, मान लें कि हमारे पास 64 बाइट्स का कैश लाइन आकार है (जो x86 इन दिनों उपयोग करता है)। तो एक बड़े पर्याप्त मैट्रिक्स के लिए, जैसे कि यह कैश आकार से बड़ा है, फिर यदि हम 16x16 ब्लॉक (आकार (int) == 4 के बाद से ट्रांसफर करते हैं, तो इस प्रकार 16 इंच एक कैश लाइन में फिट होते हैं, मानते हैं कि मैट्रिक्स कैशलाइन सीमा पर गठबंधन है) हमें 32 (16 स्रोत स्रोत मैट्रिक्स से 16) गंतव्य मैट्रिक्स से 16 लोड करने की आवश्यकता है इससे पहले कि हम उन्हें गंदे कर सकें) मेमोरी से कैश लाइनें और अन्य 16 लाइनों को स्टोर करें (भले ही स्टोर्स अनुक्रमिक नहीं हैं)। इसके विपरीत, बराबर 16 * 16 तत्वों को ट्रांसपोज़ करने के लिए कैश अवरुद्ध किए बिना हमें स्रोत मैट्रिक्स से 16 कैश लाइनों को लोड करने की आवश्यकता होती है, लेकिन 16 * 16 = 256 कैश लाइनों को लोड किया जाना चाहिए और फिर गंतव्य मैट्रिक्स के लिए संग्रहीत किया जाना चाहिए।

Answer 2

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

पहुंच की दिशा के बारे में - यह विपरीत रूप से पढ़ने और एन के विपरीत कूदने के बजाय बेहतर हो सकता है। ऐसा इसलिए है क्योंकि पढ़ना ऑपरेशन सीपीयू को अवरुद्ध करता है, जबकि लिखने के संचालन (सीमा तक) नहीं होते हैं।

अन्य सुझाव:
1. क्या आप समांतरता का उपयोग कर सकते हैं? ओपनएमपी मदद कर सकता है (हालांकि यदि आपको सिंगल सीपीयू प्रदर्शन देने की उम्मीद है, तो यह अच्छा नहीं है)।
2. फ़ंक्शन को अलग करें और इसे पढ़ें, अंतर्निहित पाश पर ध्यान केंद्रित करें। आपको उन चीजें मिल सकती हैं जिन्हें आप सी कोड में नहीं देखते हैं।
3. घटते काउंटर (0 पर रोकना) का उपयोग करना थोड़ा अधिक कुशल हो सकता है जो काउंटरों को बढ़ा रहा है।
4. कंपाइलर को यह मानना ​​चाहिए कि src और dst उपनाम (उसी या ओवरलैपिंग मेमोरी को इंगित करें), जो इसके अनुकूलन विकल्पों को सीमित करता है। यदि आप किसी भी तरह संकलक को बता सकते हैं कि वे ओवरलैप नहीं कर सकते हैं, तो यह बहुत मददगार हो सकता है। हालांकि, मुझे यकीन नहीं है कि यह कैसे करें (शायद restrict क्वालीफायर का उपयोग करें)।

Answer 3

बस एक विचार unrolling लागू करने के लिए कैसे:

void transpose(int *dst, int *src, int dim) { 
    int i, j; 
    const int dim1 = (dim/4) * 4; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim1; j+=4) { 
       dst[j*dim + i]  = src[i*dim + j]; 
       dst[(j+1)*dim + i] = src[i*dim + (j+1)]; 
       dst[(j+2)*dim + i] = src[i*dim + (j+2)]; 
       dst[(j+3)*dim + i] = src[i*dim + (j+3)]; 
     } 
     for(; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
     __builtin_prefetch (&src[(i+1)*dim], 0, 1); 
    } 
} 

cource के

आप गिनती निकाल देना चाहिए (जैसे i*dim) भीतरी पाश से, जैसा कि आप पहले से ही अपने प्रयास में किया था।

कैश प्रीफेच का उपयोग स्रोत मैट्रिक्स के लिए किया जा सकता है।

Answer 4

आपको शायद यह पता है लेकिन register int (आप संकलक को बताते हैं कि इसे रजिस्टर में रखना स्मार्ट होगा)। और int unsigned बनाने से, चीज़ें थोड़ा तेज़ी से हो सकती हैं।

Answer 5

मेसीनेस कोई समस्या नहीं है, इसलिए: मैं प्रत्येक मैट्रिक्स में transposed ध्वज जोड़ूंगा। यह ध्वज इंगित करता है कि क्या मैट्रिक्स की संग्रहीत डेटा सरणी को सामान्य या ट्रांसपोज़र ऑर्डर में व्याख्या किया जाना है।

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

इस नए कार्यान्वयन में, मैट्रिक्स ट्रांसपोज़शन केवल ध्वज को टॉगल करता है: ट्रांसपोजर ऑपरेशन के लिए आवश्यक स्थान और समय स्थिर है।