क्या यह सिम योग्य है? क्या कोई बेहतर विकल्प है?

Question

मेरे पास कुछ कोड है जो काफी अच्छी तरह से चलता है, लेकिन मैं इसे बेहतर चलाने के लिए चाहता हूं। मेरे साथ बड़ी समस्या यह है कि इसे लूप के लिए घोंसला होना चाहिए। बाहरी एक पुनरावृत्तियों के लिए है (जो क्रमशः होना चाहिए), और आंतरिक एक विचार के तहत प्रत्येक बिंदु कण के लिए है। मैं वहाँ ज्यादा मैं बाहरी एक के बारे में क्या कर सकते हैं नहीं है पता है, लेकिन अगर वहाँ की तरह कुछ के अनुकूलन का एक तरीका है मैं सोच रहा हूँ: मैं SIMD देखा है

void collide(particle particles[], box boxes[], 
     double boxShiftX, double boxShiftY) {/*{{{*/ 
      int i; 
      double nX; 
      double nY; 
      int boxnum; 
      for(i=0;i<PART_COUNT;i++) { 
        boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+ 
         BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
         //copied and pasted the macro which is why it's kinda odd looking 

        particles[i].vX -= boxes[boxnum].mX; 
        particles[i].vY -= boxes[boxnum].mY; 
        if(boxes[boxnum].rotDir == 1) { 
          nX = particles[i].vX*Wxx+particles[i].vY*Wxy; 
          nY = particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } else { //to make it randomly pick a rot. direction 
          nX = particles[i].vX*Wxx-particles[i].vY*Wxy; 
          nY = -particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } 
        particles[i].vX = nX + boxes[boxnum].mX; 
        particles[i].vY = nY + boxes[boxnum].mY; 
      } 
    }/*}}}*/ 

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

मैंने इसे शम और pthread_barrier के साथ कई धागे में तोड़ने की कोशिश की (विभिन्न चरणों को सिंक्रनाइज़ करने के लिए, जिसमें उपर्युक्त कोड एक है), लेकिन यह सिर्फ धीमा हो गया।

मेरा वर्तमान कोड बहुत तेज़ी से चला जाता है; यह एक सेकंड प्रति 10 एम कण * पुनरावृत्तियों के क्रम में है, और मैं जीप्रोफ से क्या कह सकता हूं, मेरे समय का 30% अकेले उस समारोह में खर्च किया जाता है (5000 कॉल; PART_COUNT = 8192 कण 1.8 सेकेंड लेते हैं)। मैं छोटी, निरंतर समय की चीजों के बारे में चिंतित नहीं हूं, यह सिर्फ 512 के कण * 50 के पुनरावृत्तियों * 1000 प्रयोगों ने पिछले हफ्ते एक सप्ताह से अधिक समय लिया था।

मुझे लगता है कि मेरा सवाल यह है कि यदि इन लंबे वैक्टरों से निपटने का कोई तरीका है जो उनके माध्यम से लूपिंग से अधिक कुशल है। मुझे लगता है कि ऐसा होना चाहिए, लेकिन मुझे यह नहीं मिल रहा है।

Answer 1

मुझे यकीन नहीं है कि कितना सिम लाभ होगा; आंतरिक पाश बहुत छोटा और सरल है, इसलिए मुझे लगता है (बस देखकर) कि आप शायद किसी और चीज़ की तुलना में अधिक स्मृति-बाध्य हैं। कि ध्यान में रखते हुए मैं पाश के मुख्य भाग को फिर से लिखने की जरूरत की तुलना में कणों सरणी अधिक स्पर्श नहीं करने की कोशिश करेंगे:

const double temp_vX = particles[i].vX - boxes[boxnum].mX; 
const double temp_vY = particles[i].vY - boxes[boxnum].mY; 

if(boxes[boxnum].rotDir == 1) 
{ 
    nX = temp_vX*Wxx+temp_vY*Wxy; 
    nY = temp_vX*Wyx+temp_vY*Wyy; 
} 
else 
{ 
    //to make it randomly pick a rot. direction 
    nX = temp_vX*Wxx-temp_vY*Wxy; 
    nY = -temp_vX*Wyx+temp_vY*Wyy; 
} 
particles[i].vX = nX; 
particles[i].vY = nY; 

यह अंत में अतिरिक्त इसके अलावा नहीं कर रही के छोटे संभावित पक्ष प्रभाव पड़ता है।

---

एक अन्य संभावित speedup, कण सरणी पर __restrict उपयोग करने के लिए इतना है कि संकलक बेहतर वेग को लिखता अनुकूलन कर सकते हैं होगा। इसके अलावा, यदि Wxx आदि वैश्विक चर हैं, तो उन्हें संभवतः रजिस्टरों में संग्रहीत होने के बजाय लूप के माध्यम से पुनः लोड करना पड़ सकता है; __restrict का उपयोग करके भी इसमें मदद मिलेगी।

---

आप क्रम में कणों पहुँच बना रहे हैं के बाद से, आप (जैसे __builtin_prefetch जीसीसी पर) आगे कुछ कणों प्रीफ़ेचिंग कैश छूट जाए कम करने की कोशिश कर सकते हैं। बक्से पर प्रीफेचिंग थोड़ा मुश्किल है क्योंकि आप उन्हें अप्रत्याशित क्रम में एक्सेस कर रहे हैं; आप

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc... 
// prefetch boxes[nextBoxnum] 

की तरह कुछ की कोशिश कर सकते

---

एक आखिरी एक है कि मैं सिर्फ देखा - बॉक्स :: rotDir हमेशा +/- 1.0 है अगर है, तो आप तुलना और इस तरह भीतरी पाश में शाखा समाप्त कर सकते हैं:

const double rot = boxes[boxnum].rotDir; // always +/- 1.0 
nX =  particles[i].vX*Wxx + rot*particles[i].vY*Wxy; 
nY = rot*particles[i].vX*Wyx +  particles[i].vY*Wyy; 

---

स्वाभाविक रूप से, पहले की रूपरेखा के सामान्य चेतावनियां और बाद लागू होते हैं। लेकिन मुझे लगता है कि ये सभी मदद कर सकते हैं, और इस पर ध्यान दिए बिना किया जा सकता है कि आप सिम पर स्विच करते हैं या नहीं।

Answer 2

क्या आपके पास यह बताने के लिए पर्याप्त प्रोफाइलिंग है कि उस समारोह में समय कहाँ बिताया जाता है?

उदाहरण के लिए, क्या आप वाकई बॉक्सनम गणना में अपने divs और mods नहीं हैं, जहां समय बिताया जा रहा है? कभी-कभी कंपाइलर्स संभावित शिफ्ट/और विकल्पों को खोजने में विफल रहता है, यहां तक ​​कि जहां एक मानव (या कम से कम, जो BOX_SIZE और BWIDTH/BHEIGHT जानता था, जो मैं नहीं कर सकता) हो सकता है।

यह एक दया कोड के गलत बिट SIMDifying पर बहुत समय खर्च करने के लिए किया जाएगा ...

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

Answer 3

((int)(particles[i].sX+boxShiftX))/BOX_SIZE 

यह महंगा है अगर एसएक्स एक int (बता नहीं सकता)। लूप में प्रवेश करने से पहले एक int में बॉक्सशफ्टएक्स/वाई को छंटनी करें।

Answer 4

बस रिकॉर्ड के लिए, libSIMDx86 भी है!

http://simdx86.sourceforge.net/Modules.html

(आप भी कोशिश कर सकते हैं संकलन पर: जीसीसी -O3 -msse2 या समान)।

Answer 5

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

यादृच्छिक करने के लिए एक और अधिक प्रभावी तरीका ढूंढना सूची के शीर्ष पर होगा। फिर, फ्लोट या int में काम करने की कोशिश करें, लेकिन दोनों नहीं। अंकगणित के रूप में रिकस्ट सशर्त, या कम से कम एक चयन ऑपरेशन के रूप में। केवल तभी सिम एक यथार्थवादी प्रस्ताव बन जाता है