.NET / C # में SIMD का एक छोटा सा अवलोकन

आपका ध्यान .NET फ्रेमवर्क और .NETCORE में एल्गोरिदम के वैश्वीकरण की क्षमताओं के एक छोटे से अवलोकन के लिए आमंत्रित किया गया है। लेख का उद्देश्य उन लोगों को इन तकनीकों से परिचित कराना है जो उन्हें बिल्कुल नहीं जानते थे और यह बताना चाहते थे कि नेट देशी के लिए "वास्तविक, संकलित" भाषाओं से बहुत पीछे नहीं है।
विकास।

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

थोड़ा सा इतिहास

.NET में, SIMD पहली बार .NET फ्रेमवर्क 4.6 की रिलीज के साथ दिखाई दिया। फिर प्रकार मैट्रिक्स 3 एक्स 2, मैट्रिक्स 4 एक्स 4, प्लेन, क्वाटर्नियन, वेक्टर 2, वेक्टर 3 और वेक्टर 4 को जोड़ा गया, जिसने वेक्टरकृत गणना के निर्माण की अनुमति दी। बाद में, वेक्टर <T> प्रकार को जोड़ा गया, जिसने एल्गोरिदम को वेक्टर करने के अधिक अवसर प्रदान किए। लेकिन कई प्रोग्रामर अभी भी नाखुश थे क्योंकि उपरोक्त प्रकारों ने प्रोग्रामर के विचारों के प्रवाह को सीमित कर दिया और आधुनिक प्रोसेसर के SIMD निर्देशों की पूरी शक्ति का उपयोग करने की अनुमति नहीं दी। पहले से ही हमारे समय में, .NET कोर 3.0 पूर्वावलोकन में, System.Runtime.Intrinsics नाम स्थान दिखाई दिया है, जो निर्देश चुनने में बहुत अधिक स्वतंत्रता प्रदान करता है। गति में सर्वोत्तम परिणाम प्राप्त करने के लिए, आपको RyuJit का उपयोग करने की आवश्यकता है और या तो x64 पर निर्माण करें या 32-बिट को प्राथमिकता दें और AnyCPU पर निर्माण करें। सभी बेंचमार्क जिन्हें मैंने Intel Core i7-6700 प्रोसेसर 3.40GHz (Skylake) के साथ कंप्यूटर पर चलाया था।

सरणी के तत्वों को संक्षेप में लिखें

मैंने क्लासिक समस्या के साथ शुरू करने का फैसला किया, जो अक्सर वेक्टराइजेशन की बात आने पर लिखा जाता है। यह सरणी के तत्वों का योग खोजने का कार्य है। हम इस कार्य के चार कार्यान्वयन लिखेंगे, हम एरे सरणी के तत्वों को संक्षेप में प्रस्तुत करेंगे:

सबसे स्पष्ट है

public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; } 

LINQ का उपयोग करना

 public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i); 

System.Numerics से वैक्टर का उपयोग करना:

 public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; } 

System.Runtime.Intrinsics स्थान से कोड का उपयोग करना:

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; } 

मैंने अपने कंप्यूटर पर इन 4 तरीकों पर एक बेंचमार्क लॉन्च किया और यह परिणाम मिला:

यह देखा जा सकता है कि स्पष्ट समाधान की तुलना में वैक्टर और इंट्रिंसिक्स के समाधान बहुत तेजी से और LINQ के साथ हैं। अब हमें यह पता लगाने की जरूरत है कि इन दो तरीकों में क्या होता है।

अधिक विस्तार से वैक्टर विधि पर विचार करें:

 public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; } 

• int VectorSize = वेक्टर <int> .Count; - यह एक वेक्टर में कितने 4 बाइट नंबर हैं। यदि हार्डवेयर त्वरण का उपयोग किया जाता है, तो यह मान दिखाता है कि एक SIMD रजिस्टर में कितने 4-बाइट नंबर रखे जा सकते हैं। वास्तव में, यह दिखाता है कि इस प्रकार के कितने तत्व आप समानांतर में संचालन कर सकते हैं;
• accVector - एक वेक्टर जिसमें फ़ंक्शन का परिणाम जमा होगा;
  var v = नया वेक्टर <int> (सरणी, i); - डेटा को इंडेक्स से शुरू करते हुए, सरणी से, एक नया वेक्टर वी में लोड किया जाता है। वास्तव में वेक्टरसाइज़ डेटा लोड हो जाएगा।
• accVector = Vector.Add (accVector, v); - दो वैक्टर जोड़े जाते हैं।
  उदाहरण के लिए, ऐरे 8 संख्याओं को संग्रहीत करता है: {0, 1, 2, 3, 4, 5, 6, 7} और वेक्टरसाइज == 4, फिर:
  लूप accVector के पहले पुनरावृत्ति में = {0, 0, 0, 0}, v = {0, 1, 2, 3}, accVector में जोड़ने के बाद यह होगा: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}।
  दूसरी पुनरावृत्ति में, v = {4, 5, 6, 7} और इसके बाद accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}।
• यह केवल किसी न किसी रूप में वेक्टर के सभी तत्वों को प्राप्त करने के लिए बना रहता है, इसके लिए हम इकाइयों से भरे वेक्टर द्वारा स्केलर गुणन लागू कर सकते हैं: int result = Vector.Dot (accVector, वेक्टर <int .One);
  फिर यह पता चला: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28।
• अंत में, यदि आवश्यक हो, तो संख्याएँ जोड़ी जाती हैं जो अंतिम वेक्टर में फिट नहीं होती हैं।

यदि आप आंतरिक पद्धति कोड को देखते हैं:

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; } 

आप देख सकते हैं कि यह कुछ अपवादों के साथ वैक्टर के समान है:

• वेक्टरसाइज निरंतर द्वारा दी जाती है। ऐसा इसलिए है क्योंकि Avx2 निर्देश जो 256 बिट रजिस्टरों पर काम करते हैं, इस पद्धति में स्पष्ट रूप से उपयोग किए जाते हैं। एक वास्तविक एप्लिकेशन में, यह देखने के लिए एक जांच होनी चाहिए कि क्या वर्तमान Avx2 प्रोसेसर निर्देशों का समर्थन करता है और यदि नहीं, तो दूसरा कोड कॉल करें। यह कुछ इस तरह दिखता है:
  

   if (Avx2.IsSupported) { DoThingsForAvx2(); } else if (Avx.IsSupported) { DoThingsForAvx(); } ... else if (Sse2.IsSupported) { DoThingsForSse2(); } ... 

• var accVector = वेक्टर256 <int> .Zero; accVector को शून्य बिट वेक्टर से भरा घोषित किया गया है।
• फिक्स्ड (int * ptr = Array) - एक पॉइंटर का पॉइंटर ptr में दर्ज किया जाता है।
• फिर वैक्टर में समान संचालन: एक वेक्टर में डेटा लोड करना और दो वैक्टर जोड़ना।
• वेक्टर के तत्वों को संक्षेप में प्रस्तुत करने के लिए, निम्नलिखित विधि लागू की गई थी:
  
  • एक सरणी स्टैक पर बनाई गई है: var अस्थायी = स्टैकलोक इंट [वेक्टरसाइज़];
  • वेक्टर को इस सरणी में लोड किया गया है: Avx2.Store (अस्थायी, accVector);
  • एक लूप में ऐरे के तत्व सम्‍मिलित हैं।
• फिर अंतिम वेक्टर में नहीं रखी गई सरणी के तत्वों को जोड़ा जाता है

दो सरणियों की तुलना करें

बाइट्स के दो सरणियों की तुलना करना आवश्यक है। वास्तव में यह वह समस्या है जिसके कारण मैंने .NET में SIMD सीखना शुरू किया। फिर, हम बेंचमार्क के लिए कई तरीके लिखेंगे, हम दो सरणियों की तुलना करेंगे: ArrayA और ArrayB:

सबसे स्पष्ट समाधान:

 public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } 

LINQ के माध्यम से समाधान:

 public bool LINQ() => ArrayA.SequenceEqual(ArrayB); 

MemCmp समारोह के माध्यम से समाधान:

 [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0; 

System.Numerics से वैक्टर का उपयोग करना:

 public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } 

आंतरिक का उपयोग करना:

 public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } } 

मेरे कंप्यूटर पर बेंचमार्क का परिणाम:

इन तरीकों के लिए सभी कोड, मुझे लगता है कि समझ में आता है, आंतरिक में दो लाइनों के अपवाद के साथ:

 var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } 

पहले में, दो वैक्टर की समानता के लिए तुलना की जाती है और परिणाम को इरिक्वाल वेक्टर में संग्रहित किया जाता है, जिसमें सभी बिट्स को एक विशिष्ट स्थान पर एक तत्व में 1 पर सेट किया जाता है यदि va और vb में संबंधित तत्व समान हों। यह पता चला है कि अगर बाइट्स वीए और वीबी से वैक्टर पूरी तरह से बराबर हैं, तो इस तरह से सभी तत्वों में 255 (11111111b) के बराबर होना चाहिए। क्योंकि Avx2.CompareEqual _mm256_cmpeq_epi8 पर एक आवरण है, तब इंटेल साइट पर आप इस ऑपरेशन का छद्म कोड देख सकते हैं:
एक वेक्टर से MoveMask विधि एक 32-बिट संख्या बनाती है। बिट मान वेक्टर के 32 एकल-बाइट तत्वों में से प्रत्येक के उच्च बिट्स हैं। स्यूडोकोड यहाँ पाया जा सकता है ।

इस प्रकार, यदि va और vb में कुछ बाइट्स मेल नहीं खाते हैं, तो समान्य में बाइट्स 0 होंगे, इसलिए इन बाइट्स के सबसे महत्वपूर्ण बिट्स भी 0 होंगे, जिसका अर्थ है कि Avx2 .Mask प्रतिक्रिया में संबंधित बिट्स भी 0 और तुलनात्मक होंगे। बराबरी के साथ काम नहीं करेगा।

चलो एक छोटे से उदाहरण का विश्लेषण करते हैं, यह मानते हुए कि वेक्टर की लंबाई 8 बाइट्स है (यह लिखना कम था):

• चलो va = {100, 10, 20, 30, 100, 40, 50, 100}, और vb = {100, 20, 10, 30, 100, 40, 80, 90};
• फिर ईक्वल {255, 0, 0, 255, 255, 255, 0, 0} के बराबर होगा;
• मूवमस्क विधि 10011100 बी लौटेगी, जिसे मास्क 11111111 बी के साथ तुलना करने की आवश्यकता होगी, क्योंकि चूंकि ये मुखौटे असमान हैं, इसलिए यह पता चला है कि वैक्टर va और vb समान नहीं हैं।

गणना करें कि संग्रह में एक तत्व कितनी बार होता है

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

सबसे स्पष्ट:

 public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; } 

LINQ का उपयोग कर:

 public int LINQ() => Array.Count(i => i == Item); 

System.Numerics.Vectors से वैक्टर का उपयोग करना:

 public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; } 

आंतरिक का उपयोग करना:

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; //var mask = Avx2.SetAllVector256(Item); //var mask = Avx2.SetVector256(Item, Item, Item, Item, Item, Item, Item, Item); var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; } 

मेरे कंप्यूटर पर बेंचमार्क का परिणाम:

वैक्टर और इंट्रिनिक्स विधियां पूरी तरह से तर्क में समान हैं, अंतर केवल विशिष्ट संचालन के कार्यान्वयन में हैं। समग्र रूप में विचार है:

• एक मुखौटा वेक्टर बनाया जाता है जिसमें आवश्यक संख्या प्रत्येक तत्व में संग्रहीत होती है;
• सरणी का हिस्सा वेक्टर v में लोड किया जाता है और मास्क के साथ तुलना की जाती है, फिर सभी बिट्स को समान तत्वों में सेट किया जाएगा। areEqual ints से एक वेक्टर है, तो यदि आप एक तत्व के सभी बिट्स सेट करते हैं, तो हमें इस तत्व में -1 मिलता है ((int) (1111_1111_1111_1111_1111_1111_1111_1111b == -1);
• वेक्टर areEqual को accVector से घटाया जाता है और फिर accVector को इस बात का योग होगा कि प्रत्येक वैक्टर v में कितनी बार आइटम तत्व हुआ है प्रत्येक स्थिति के लिए (माइनस मिनट एक प्लस देता है)।

लेख के सभी कोड GitHub पर देखे जा सकते हैं

निष्कर्ष

मैंने केवल संभावनाओं के एक बहुत छोटे हिस्से की जांच की जो .NET कम्प्यूटिंग कम्प्यूटिंग के लिए प्रदान करता है। X86 के तहत .NETCORE में उपलब्ध आंतरिक की पूर्ण और अद्यतित सूची के लिए, आप स्रोत कोड का उल्लेख कर सकते हैं। यह सुविधाजनक है कि प्रत्येक आंतरिक के सारांश में C # फ़ाइलों में C की दुनिया का अपना नाम है, जो इस आंतरिक के उद्देश्य और मौजूदा C ++ / C एल्गोरिदम के अनुवाद की समझ को आसान बनाता है। System.Numerics.Vector प्रलेखन msdn पर उपलब्ध है।

मेरी राय में, .NET का C ++ से अधिक लाभ है, क्योंकि जेआईटी संकलन क्लाइंट मशीन पर पहले से ही होता है, फिर कंपाइलर एक विशिष्ट क्लाइंट प्रोसेसर के लिए कोड का अनुकूलन कर सकता है, अधिकतम प्रदर्शन प्रदान करता है। उसी समय, तेज कोड लिखने के लिए एक प्रोग्रामर एक भाषा और प्रौद्योगिकी के ढांचे के भीतर रह सकता है।

UPD (09/15/2019):