x86 अधिकतम/मिनट ASM निर्देश?

Question

क्या कोई एएसएम निर्देश हैं जो कोर i7 आर्किटेक्चर पर युगल/पूर्णांक के वेक्टर के न्यूनतम/अधिकतम की गणना को तेज कर सकते हैं?

अद्यतन:

मैं ऐसे अमीर जवाब उम्मीद नहीं थी, धन्यवाद। तो मुझे लगता है कि ब्रांचिंग के बिना अधिकतम/मिनट करना संभव है। मेरे पास उप-प्रश्न है:

क्या सरणी में सबसे बड़ा डबल इंडेक्स प्राप्त करने का कोई प्रभावी तरीका है?

Answer 1

एसएसई 4 में 32 बिट हस्ताक्षरित/हस्ताक्षरित पूर्णांक के लिए PMAXSD या PMAXUD है, जो उपयोगी हो सकता है।

SSE2 है MAXPD और MAXSD जो बीच और डबल्स की जोड़ी भर में तुलना है, तो आप n एक MAXSD साथ/2-1 MAXPDs भार और संचालन के सामान्य जुड़ाव के साथ, एन का एक वेक्टर की अधिकतम प्राप्त करने के लिए का पालन करें।

उपरोक्त के MIN समकक्ष हैं।

peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max 
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse 
peregrino:$ time bin/min_max 
0,40 

real 0m0.874s 
user 0m0.796s 
sys 0m0.004s 
peregrino:$ time bin/min_max_sse 
0,40 

real 0m0.457s 
user 0m0.404s 
sys 0m0.000s 

जहां min_max मिनट और 500 युगल की एक सरणी की अधिकतम गणना करता है:

डबल मामले के लिए, आप शायद SSE मोड में एक आधा सभ्य C++ कम्पाइलर से कोडांतरक में बेहतर करने के लिए नहीं जा रहे हैं एक अनुभवहीन पाश का उपयोग कर 100,000 बार:

bool min_max (double array[], size_t len, double& min, double& max) 
{ 
    double min_value = array [ 0 ]; 
    double max_value = array [ 0 ]; 

    for (size_t index = 1; index < len; ++index) { 
     if (array [ index ] < min_value) min_value = array [ index ]; 
     if (array [ index ] > max_value) max_value = array [ index ]; 
    } 

    min = min_value; 
    max = max_value; 
} 

---

जवाब में दो भाग के लिए, एक अधिकतम आपरेशन से शाखा दूर करने के लिए पारंपरिक अनुकूलन मानों की तुलना करने, एक गाना के रूप में ध्वज मिलता है ले बिट (0 या 1 देने), एक को घटाएं (0 या 0xffff_ffff दे रहा है) और 'और' इसे दो संभावित परिणामों के xor के साथ, ताकि आप (a > best ? (current_index^best_index) : 0)^best_index) के बराबर प्राप्त कर सकें। मुझे संदेह है कि ऐसा करने का एक सरल एसएसई तरीका है, क्योंकि बस एसएसई टैग किए गए मूल्यों के बजाय पैक किए गए मूल्यों पर काम करता है; कुछ क्षैतिज इंडेक्स ऑपरेशंस हैं, इसलिए आप अधिकतम वेक्टर ढूंढने का प्रयास कर सकते हैं, फिर मूल वेक्टर के सभी तत्वों से घटाकर, फिर साइन बिट इकट्ठा कर सकते हैं, और शून्य हस्ताक्षरित एक अधिकतम के सूचकांक के अनुरूप होगा, लेकिन शायद यह होगा जब तक आप शॉर्ट्स या बाइट्स का उपयोग नहीं कर रहे हों तब तक सुधार न करें।

Answer 2

एसएसई से MAXPS और MINPS दोनों पैक किए गए सिंगल-प्रेसिजन फ्लोटिंग पॉइंट नंबर पर काम करते हैं। पीएमएक्सएसडब्ल्यू, पीएमआईएनएसडब्ल्यू, पीएमएक्सयूबी और पीएमआईएनयूबी सभी 8-बिट शब्दों पर पैक करते हैं, या तो हस्ताक्षरित या हस्ताक्षरित। कृपया ध्यान दें कि ये दो इनपुट एसएसई रजिस्टरों या पता स्थान तत्व-वार की तुलना करते हैं और परिणाम को एसएसई रजिस्टर या मेमोरी लोकेशन में संग्रहीत करते हैं।

MAXPS और MINPS के एसएसई 2 संस्करणों को डबल-परिशुद्धता फ्लोट पर काम करना चाहिए।

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

Answer 3

अगर आपके इंटेल की IPP पुस्तकालय का उपयोग कर रहे आप वेक्टर मिनट/(अन्य बातों के अलावा) अधिकतम

Answer 4

गणना करने के लिए अपने दूसरे प्रश्न के उत्तर में वेक्टर statistical functions उपयोग कर सकते हैं: सबसे प्लेटफार्मों पर, वहाँ पुस्तकालयों पहले से ही अनुकूलित निहित है कि कर रहे हैं इस ऑपरेशन के कार्यान्वयन (और अन्य सरल वेक्टर ऑपरेशंस)। उन्हें का उपयोग करें।

• OS X पर, वहाँ है vDSP_maxviD() और में cblas_idamax() Accelerate.framework
• इंटेल compilers cblas_idamax()
• अधिकांश Linux सिस्टम cblas_idamax() होगा सहित IPP और MKL लाइब्रेरीज, जिसमें उच्च निष्पादन कार्यान्वयन है, शामिल हैं बीएलएएस लाइब्रेरी में, जो इसके उद्भव के आधार पर अच्छी तरह से ट्यून किया जा सकता है या नहीं; जो उपयोगकर्ता प्रदर्शन के बारे में परवाह करते हैं, उनके पास आमतौर पर एक अच्छा कार्यान्वयन होगा (या एक स्थापित करने के लिए राजी किया जा सकता है)
• यदि अन्य सभी विफल हो जाते हैं, तो आप लक्ष्य मंच
पर एक सभ्य प्रदर्शन कार्यान्वयन के लिए एटीएलएएस (स्वचालित रूप से ट्यूनेड लीनियर बीजगणित सॉफ़्टवेयर) का उपयोग कर सकते हैं।

Answer 5

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

आप डेटा को बी-पेड़ में संग्रहीत कर सकते हैं जो डेटा को हर समय सॉर्ट करता है, केवल लॉगरिदमिक तुलना संचालन की आवश्यकता होती है।

तब आप जानते हैं कि अधिकतम समय कहां है।

http://en.wikipedia.org/wiki/B_tree

Answer 6

अद्यतन: मैं बस एहसास हुआ कि आपने कहा "सरणी" भाग 2 में, नहीं "वेक्टर" मैं इस यहाँ वैसे भी मामले में यह उपयोगी है छोड़ देंगे।

---

पुन: भाग दो:

• एक क्षैतिज अधिकतम कार्य करें: एक SSE वेक्टर में अधिकतम/मिनट तत्व के सूचकांक पाते हैं। एक 128 बी वेक्टर 2 double तत्वों के लिए, यह केवल shufpd + maxpd दोनों परिणामों को प्रसारित करने के लिए छोड़ देता है।

  अन्य मामलों के लिए, यह निश्चित रूप से और अधिक कदम उठाएगा। विचारों के लिए Fastest way to do horizontal float vector sum on x86 देखें, addps को maxps या minps के साथ बदलें। (लेकिन ध्यान दें कि 16-बिट पूर्णांक विशेष है, क्योंकि आप एसएसई 4 phminposuw का उपयोग कर सकते हैं। अधिकतम के लिए, 255 से घटाएं)

• वेक्टर मूल वेक्टर और वेक्टर के बीच पैक-तुलना करें जहां प्रत्येक तत्व अधिकतम है।

  (pcmpeqq पूर्णांक बिट पैटर्न या सामान्य cmpeqpd दोनों double मामले के लिए काम करेंगे)।

• int _mm_movemask_pd (__m128d a) (movmskpd) तुलना परिणाम को एक पूर्णांक बिटमैप के रूप में प्राप्त करने के लिए।
• बिट-स्कैन (bsf) यह (पहले) मैच के लिए: index = _bit_scan_forward(cmpmask)। cmpmask = 0 असंभव है यदि आपने पूर्णांक तुलनाओं का उपयोग किया है (क्योंकि कम से कम एक तत्व तब भी मेल खाता है जब वे NaN हैं)।

यह केवल 6 निर्देशों (movapd सहित) को संकलित करना चाहिए। हाँ, बस the Godbolt compiler explorer पर चेक किया गया और यह एसएसई के साथ करता है।

#include <immintrin.h> 
#include <x86intrin.h> 

int maxpos(__m128d v) { 
    __m128d swapped = _mm_shuffle_pd(v,v, 1); 
    __m128d maxbcast = _mm_max_pd(swapped, v); 
    __m128d cmp = _mm_cmpeq_pd(maxbcast, v); 
    int cmpmask = _mm_movemask_pd(cmp); 
    return _bit_scan_forward(cmpmask); 
} 

नोट करें कि _mm_max_pd is not commutative with NaN inputs।यदि NaN संभव है, और आपको इंटेल नेहलेम पर प्रदर्शन की परवाह नहीं है, तो आप बिट-पैटर्न की तुलना करने के लिए _mm_cmpeq_epi64 का उपयोग करने पर विचार कर सकते हैं। फ्लोट से वीसी-इंट तक बायपास-देरी नेहलेम पर एक समस्या है, हालांकि।

NaN! = आईईईई फ्लोटिंग पॉइंट में NaN, इसलिए _mm_cmpeq_pd परिणाम मुखौटा सभी-NaN मामले में सभी शून्य हो सकता है।

2-तत्व मामले में आप एक और चीज कर सकते हैं जो हमेशा 0 या 1 प्राप्त करने के लिए cmpmask >> 1 के साथ बिट-स्कैन को प्रतिस्थापित करना है। (bsf इनपुट = ऑल-शून्य के साथ अजीब है)।