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

यहाँ .NET Framework और .NET कोर में एल्गोरिथ्म वेक्टराइजेशन क्षमताओं पर एक त्वरित नज़र है। यह लेख उन लोगों के लिए है जो इन तकनीकों के बारे में कुछ नहीं जानते हैं। मैं यह भी दिखाऊंगा कि .NET वास्तव में मूल विकास के लिए "वास्तविक संकलित" भाषाओं से पीछे नहीं है।

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

कुछ इतिहास

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

सार तत्वों को समेटना

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

सबसे स्पष्ट कार्यान्वयन:

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); - सरणी से डेटा को एक नए v वेक्टर में लोड किया जाता है, जो i इंडेक्स से शुरू होता है। डेटा का वेक्टरसाइज़ बिल्कुल लोड किया जाएगा;
• accVector = Vector.Add (accVector, v); - दो वैक्टर सम्‍मिलित हैं।
  उदाहरण के लिए, ऐरे में 8 संख्याएँ हैं: {0, 1, 2, 3, 4, 5, 6, 7} और वेक्टरसेज == 4।
  फिर पहले चक्र के दौरान पुनरावृत्ति उच्चारण = {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 temp = stackalloc int [VectorSize];
  • इस सरणी में एक वेक्टर लोड करें: Avx2.Store (अस्थायी, accVector);
  • चक्र के दौरान योग के तत्व।
• अगला, वे तत्व जो अंतिम वेक्टर में फिट नहीं होते हैं, उन्हें सारांशित किया जाता है।

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

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

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

 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 एकबाइट तत्वों के शीर्ष बिट्स MoveMask परिणाम में बिट्स के मान हैं। स्यूडोकोड यहाँ उपलब्ध है ।

इस प्रकार, यदि va और vb में कुछ बाइट्स मेल नहीं खाते हैं, तो areEqual में संबंधित बाइट्स 0. होगा। इसलिए, इन बाइट्स के शीर्ष बिट्स 0 भी होंगे। इसका मतलब यह है कि Avx2.MoveMask में संबंधित बिट्स 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} होंगे।
• MoveMask विधि 10011100b लौटेगी जिसकी तुलना 11111111b मास्क से की जानी चाहिए। चूंकि ये मास्क समान नहीं हैं, इसलिए 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 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 वेक्टर में एक सरणी के भाग को लोड करें और इस भाग की तुलना मास्क से करें। नतीजतन, सभी बिट्स एसेक्वाल के समान तत्वों में सेट हो जाएंगे। जैसा कि ईक्वल पूर्णांक का एक सरणी है, तो यदि हम एक तत्व के सभी बिट्स सेट करते हैं, तो हम इस तत्व में -1 प्राप्त करेंगे ((इंट) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
• एक्वीक्टर से घटाव वेक्टर वेक्टर हैं। फिर, accVector प्रत्येक पद के लिए सभी v वैक्टरों में आइटम तत्व कितनी बार हुआ इसकी गणना करेगा (शून्य से ऋण एक प्लस है)।

लेख का पूरा कोड GitHub पर है ।

निष्कर्ष

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

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