एक्स 64 असेंबलर एडीडी लूप

Question

गति मैं बहुत लंबे पूर्णांक (कुछ 100,000 दशमलव अंक) के गुणा के लिए अंकगणित पर काम कर रहा हूं। मेरी लाइब्रेरी के हिस्से के रूप में मैं दो लंबी संख्याओं को जोड़ना चाहता हूं।

प्रोफाइलिंग से पता चलता है कि मेरा कोड ऐड() और उप() दिनचर्या में 25% तक चलता है, इसलिए यह महत्वपूर्ण है कि वे जितनी जल्दी हो सके। लेकिन मुझे अभी तक बहुत संभावना नहीं दिख रही है। शायद आप मुझे कुछ मदद, सलाह, अंतर्दृष्टि या विचार दे सकते हैं। मैं उनका परीक्षण करूंगा और आपको वापस ले जाऊंगा।

अब तक मेरी ऐड दिनचर्या कुछ सेटअप करता है और फिर एक 8-बार unrolled पाश का उपयोग करता है:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov r10, QWORD PTR [r8+r11*8-64] 
adc rax, r10 
mov QWORD PTR [rcx+r11*8-64], rax 

7 अधिक विभिन्न ऑफसेट के साथ ब्लॉक का पालन करें और फिर इसे लूप।

मैंने पहले स्मृति से मूल्यों को लोड करने का प्रयास किया, लेकिन इससे मदद नहीं मिली। मुझे लगता है कि अच्छा prefetching के कारण है। मैं इंटेल i7-3770 आइवी ब्रिज 4-कोर सीपीयू का उपयोग करता हूं। लेकिन मैं कोड लिखना चाहता हूं जो किसी भी आधुनिक सीपीयू पर अच्छा काम करता है।

संपादित करें: मैंने कुछ समय किया: यह लगभग 2.25 चक्र/शब्द में 1k शब्द जोड़ता है। अगर मैं एडीसी हटा देता हूं, तो केवल एमओवी ही रहती है, फिर भी इसमें लगभग 1.95 चक्र/शब्द लगते हैं। तो मुख्य बाधा स्मृति पहुंच प्रतीत होता है। एक पुस्तकालय memcpy() लगभग 0.65 चक्र/शब्द में काम करता है, लेकिन इसमें केवल एक इनपुट है, दो नहीं। फिर भी, एसएसई रजिस्टरों के उपयोग के कारण यह बहुत तेज है, मुझे लगता है।

कुछ सवाल:

• इसका इस्तेमाल करने के लिए उपयोगी है "लोड, लोड,, स्टोर जोड़ें" संरचना या एक "लोड, जोड़ने करने वाली स्मृति" मदद मिलेगी? अब तक मेरे परीक्षणों ने कोई लाभ नहीं दिखाया है।
• सामान्य रूप से, एसएसई (2,3,4) से अपेक्षित होने की कोई मदद नहीं है?
• क्या पता (स्केल किए गए इंडेक्स प्लस बेस प्लस ऑफसेट) को बुरी तरह प्रभावित किया जाता है? मैं इसके बजाय ADD r11, 8 का उपयोग कर सकता था।
• लूप अनोलिंग के बारे में क्या? मैंने पढ़ा है सैंडी ब्रिज आर्किटेक्चर (एग्नेर फॉग http://www.agner.org/optimize/) के लिए अनोलिंग खराब था। क्या इसे प्राथमिकता दी जानी चाहिए या इससे बचा जा सकता है?
• (संपादित करें) क्या मैं एसएसई रजिस्टरों का उपयोग स्मृति से बड़े हिस्सों में लोड और स्टोर करने के लिए कर सकता हूं और सामान्य प्रयोजन रजिस्टरों और एसएसई रजिस्टरों के साथ कुशलता से शब्दों का आदान-प्रदान कर सकता हूं?

मैं किसी भी टिप्पणी की अत्यधिक सराहना करता हूं।

Answer 1

पहले डेटा को प्रीफ़ेच करने का प्रयास करें (आप पहले x64 रजिस्टरों को अधिक डेटा ब्लॉक पढ़ने की कोशिश कर सकते हैं तो गणना करें), जांचें कि डेटा मेमोरी में ठीक से संरेखित है या नहीं, 16 पर गठबंधन लेबल पर लूप कोड डालें, एसआईबी को संबोधित

तुम भी करने के लिए अपने कोड को छोटा करने की कोशिश कर सकते निकालें:

mov rax, QWORD PTR [rdx+r11*8-64] 
adc rax, QWORD PTR [r8+r11*8-64] 
mov QWORD PTR [rcx+r11*8-64], rax 

Answer 2

सबसे कठिन निर्भरता हर स्मृति ब्लॉक के बीच कैरी के प्रसार है; मैं पहले डिवाइस से निपटने की एक विधि को आजमाने की कोशिश करता हूं।

निम्नलिखित खंड अनुकरण प्रसार को अनुकरण करता है, लेकिन लेयर ध्वज का उपयोग न करने के "लाभ" के साथ। यह तीन या चार अलग-अलग धागे के लिए समानांतर किया जा सकता है, प्रत्येक में आधा उत्पादन लगभग 25000 दशमलव अंक (या 10000 बाइट) अलग होता है।फिर उन लोगों की संभावना केवल एक बाइट, शब्द, शब्द इत्यादि को प्रभावित करती है, जो असीम रूप से शून्य तक पहुंच जाएंगी।

long long carry=0; 
for (int i=0;i<N;i++) { 
    carry += (long long)*a++ + (long long)*b++; 
    *c++ = carry; carry>>=32; 
} 

मेरी रूपरेखा के अनुसार, XMM का उपयोग कर carryless अलावा ले जाएगा ~ 550ms (1e9 शब्द), नकली कैरी ले ~ 1020ms और 4-मार्गी parallelized संस्करण (किसी भी कोडांतरक अनुकूलन के बिना) ~ 820ms ले जाएगा होगा।

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

Answer 3

मुझे यकीन है कि memcpy तेज़ है क्योंकि यह अगले ऑपरेशन करने से पहले डेटा प्राप्त होने पर निर्भरता नहीं रखता है।

इतना है कि यह कुछ इस तरह करता है आप अपने कोड की व्यवस्था कर सकते हैं:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov rbx, QWORD PTR [rdx+r11*8-56] 
mov r10, QWORD PTR [r8+r11*8-64] 
mov r12, QWORD PTR [r8+r11*8-56] 
adc rax, r10 
adc rbx, r12 
mov QWORD PTR [rcx+r11*8-64], rax 
mov QWORD PTR [rcx+r11*8-56], rbx 

मैं 100% यकीन नहीं है कि -56 की भरपाई अपने कोड के लिए सही है, लेकिन अवधारणा है " सही"।

मैं कैश-हिट/कैश-टकराव पर भी विचार करूंगा। जैसे यदि आपके पास डेटा के तीन ब्लॉक हैं [जो ऐसा लगता है कि आप करते हैं], तो आप सुनिश्चित करते हैं कि वे कैश में उसी ऑफ़सेट से गठबंधन नहीं हैं। एक बुरा उदाहरण होगा यदि आप कैश में उसी स्थान से कैश-आकार के एकाधिक पर अपने सभी ब्लॉक आवंटित करते हैं। अधिक आवंटित करने और सुनिश्चित करने के लिए कि आपके अलग-अलग डेटा ब्लॉक कम से कम 512 बाइट द्वारा ऑफ़सेट किए जाते हैं [इसलिए 4K oversize आवंटित करें, और 4K सीमा प्रारंभ पता तक गोल करें, फिर दूसरे बफर में 512 जोड़ें, और 1024 को तीसरे बफर में जोड़ें]

यदि आपका डेटा पर्याप्त बड़ा है (L2 कैश से बड़ा), तो आप अपने डेटा को लाने/स्टोर करने के लिए MOVNT का उपयोग करना चाह सकते हैं। यह कैश में पढ़ने से बच जाएगा - यह केवल तभी लाभ होता है जब आपके पास बहुत बड़ा डेटा होता है, जहां अगला पठन केवल कुछ और कारण बनता है जिसे आपको कैश से बाहर निकालने के लिए "उपयोगी" मिल सकता है, और आपको नहीं मिलेगा इसे कैश से बाहर निकालने से पहले इसे वापस लाएं - इसलिए कैश में मान को संग्रहीत करने में वास्तव में मदद नहीं होगी ...

संपादित करें: एसएसई या इसी तरह का उपयोग करने से यहां सहायता नहीं होगी, जैसा कि यहां शामिल है: Can long integer routines benefit from SSE?