आधुनिक प्रोसेसर में अजीब पॉपकॉइन अनुदेश का उपयोग कैसे किया जाता है

यह मेरी प्रस्तुति का छद्म डिकोडिंग है !! Con 2019

आज उपयोग में आने वाले अधिकांश प्रोसेसर आर्किटेक्चर के पास popcount नामक निर्देश हैं, जो 'जनसंख्या गणना' के लिए छोटा है। वह निम्नलिखित करती है: मशीन शब्द में सेट बिट्स की संख्या को गिनाती है। उदाहरण के लिए (आइए सरलता के लिए 8-बिट शब्द लें), popcount(00100110) 3 है, और popcount(01100000) 2 है।

यह आपको मेरी तरह बहुत आश्चर्यचकित कर सकता है, लेकिन यह सब वह करता है! बहुत उपयोगी नहीं लगता है, है ना?

मैंने सोचा कि यह कुछ हाइपरस्पेशिअलाइज्ड उपयोग के मामलों के लिए हाल ही में जोड़ा गया था, लेकिन यह वास्तव में 1961 के बाद से प्रोसेसर आर्किटेक्चर में मौजूद है:

• 1961: आईबीएम स्ट्रेच
  
• 1964: सीडीसी 6000
  
• 1975: क्रे -1
  
• 2005: स्पार्क
  
• 2005: एआरएम नीयन
  
• 2007: एएमडी के 10
  
• 2008: इंटेल नेहेल्म

तो क्या चल रहा है?

एनएसए निर्देश

popcount "NSA निर्देश" के रूप में भी जाना जाता है, और comp.arch पर एक बहुत ही दिलचस्प सूत्र क्रिप्टोग्राफी में इसके उपयोग पर चर्चा करता है। अफवाह यह है कि यह मूल रूप से एनएसए के अनुरोध पर सीपीयू अनुदेश सेट में जोड़ा गया था। जैसा कि इस संग्रहीत मेल थ्रेड में बताया गया है:

यह एक तेज़ ट्रक सीडीसी कारों में से एक को "अच्छे ग्राहक" में भेजने के लिए लगभग एक परंपरा थी - एक अज्ञात ट्रक का आगमन हुआ और फिर कभी नहीं सुना गया।

एक महान किंवदंती, लेकिन उन्होंने इसका उपयोग क्यों किया?

सामग्री का एक माप हैमिंग का वजन है , जो एक स्ट्रिंग में गैर-शून्य वर्णों की संख्या है। एक बाइनरी स्ट्रिंग के लिए, यह popcount !

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

1. संदेश को लाइनों में विभाजित करें
   
2. स्ट्रिंग में प्रत्येक अद्वितीय वर्ण के लिए थोड़ा सेट करें
   
3. विभिन्न वर्णों की संख्या की गणना करने के लिए popcount का उपयोग करें
   
4. आगे क्रिप्टैनालिसिस के लिए हैश के रूप में काउंटर का उपयोग करें

उत्सुकता से, popcount 1970 के दशक और 2000 के मध्य के बीच के निर्देश सेट से गायब हो गया है, इसलिए रिटर्न को क्रिप्टोग्राफिक अनुप्रयोगों के अलावा कुछ और समझा जाना चाहिए। इसके लिए और क्या उपयोग किया जा सकता है?

बग ठीक करना

हैमिंग वजन की अवधारणा हैमिंग दूरी से संबंधित है, जो एक ही लंबाई की दो लाइनों के बीच विभिन्न पदों की संख्या है। दो बाइनरी स्ट्रिंग्स x और y , यह XOR के बाद सिर्फ popcount । उदाहरण के लिए:

  00100110
 01100000 ^
 --------
 01000110

 पॉपकाउंट (01000110) = 3 

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

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

बाइनरी कनवल्शनल न्यूरल नेटवर्क

और अब कुछ पूरी तरह से अलग है: द्विआधारी दृढ़ तंत्रिका नेटवर्क! लेकिन पहले, यह क्या है?

• बाइनरी का अर्थ है कि हम केवल 32-बिट फ्लोटिंग पॉइंट वैल्यू के विपरीत, +1 के मानों (1 के रूप में एन्कोडेड) और -1 (एन्कोडेड 0 के रूप में) का उपयोग करते हैं।
  
• क्या कनवल्शन का मतलब मैट्रिक्स गुणा है?
  
• तंत्रिका नेटवर्क जानवरों के दिमाग से प्रेरित प्रणाली हैं (यहां मैं थोड़ा तैर रहा हूं)।

इस प्रकार, हमें बाइनरी मैट्रिस का गुणा करना चाहिए। लेकिन बाइनरी मैट्रिसेस के बारे में क्या खास है?

32-बिट मूल्यों द्वारा पारंपरिक मैट्रिक्स गुणा शक्तिशाली सीपीयू और जीपीयू के साथ डेस्कटॉप कंप्यूटरों के लिए अच्छी तरह से अनुकूल है, लेकिन अधिक से अधिक बार हम छोटे और सरल उपकरणों जैसे स्मार्टफोन, राउटर, स्मार्ट घड़ियों आदि पर उपयोगी काम करना चाहते हैं, हम इनका विघटन कर सकते हैं। बाइनरी मैट्रिस की परतों के लिए और अधिक जटिल मैट्रीस, और उनके साथ काम करना और उन्हें संग्रहीत करना इतना आसान है कि हम परतों की संख्या में वृद्धि के बावजूद भी लाभ उठाते हैं।

यह वह popcount है popcount खेलने में आता है। इसका उपयोग दो द्विआधारी मैट्रिक्स के स्केलर उत्पाद की गणना करने के लिए किया जाता है:

  a = xnor (x, y)
 बी = पॉपकाउंट (ए)
 सी = लेन (ए)
 डॉट (x, y) = 2 × b - c 

अधिक जानकारी के लिए यहां और यहां देखें।

शतरंज की प्रोग्रामिंग

कई शतरंज कार्यक्रम एक बिटबोर्ड प्रतिनिधित्व में डेटा संग्रहीत करते हैं, जो आसानी से 64-बिट शब्द में फिट बैठता है। Population Count ऑपरेशन का उपयोग इस दृश्य के साथ सार्थक संचालन के लिए किया गया था, जैसे किसी आंकड़े की गतिशीलता की गणना करना।

उँगलियों का फड़कना

यह popcount दूरी से भी संबंधित है: अणु किसी तरह से हैश किए जाते हैं और तुलना ( popcount का उपयोग popcount ) यह निर्धारित करने के लिए कि वे समान कैसे हैं। अधिक जानकारी के लिए यहां देखें।

हैश ऐरे मैप्ड ट्राइ (HAMT)

यह वह जगह है जहाँ मैंने पहली बार popcount बारे में सीखा! एचएएमटी एक डेटा संरचना है ( पहली बार फिल बैगवेल द्वारा बनाई गई ) जो प्रत्येक ट्राइ नोड पर एक सरणी में बहुत बड़ी संख्या में मान (आमतौर पर 32 या 64) स्टोर कर सकती है। हालांकि, 32 या 64 तत्व सरणी के लिए मेमोरी आवंटित करना हर बार अविश्वसनीय रूप से बेकार हो सकता है, खासकर अगर सरणी में वास्तव में केवल कुछ तत्व होते हैं। समाधान एक बिटमास्क जोड़ने के लिए है जिसमें सेट बिट्स की संख्या सरणी में तत्वों की संख्या से मेल खाती है, जो सरणी को बढ़ने और आवश्यकतानुसार अनुबंध करने की अनुमति देता है। किसी दिए गए तत्व के लिए सूचकांक गणना प्रभावी रूप से popcount का उपयोग करके की जा सकती है। HAMT संरचनाओं को लागू करने के बारे में मेरे ब्लॉग पोस्ट में , आप इस बारे में अधिक जान सकते हैं कि वे कैसे काम करते हैं।

संकुचित डेटा संरचनाएँ

यह अनुसंधान का एक रोमांचक नया क्षेत्र है जो उपयोगी काम करने के लिए बिना अनपैक किए कम से कम जगह में डेटा को स्टोर करने के तरीके पर ध्यान केंद्रित करता है। तरीकों में से एक बिट्स (बिट वैक्टर) के सरणियों के संदर्भ में सोचना है जो दो कार्यों में अनुरोध किया जा सकता है:

• rank(i) बिट वेक्टर में i-th इंडेक्स तक दिए गए बिट्स की संख्या को गिनता है
  
• select(i) उस इंडेक्स को खोजता है जिस पर i-th बिट सेट है

बड़ी बिट वैक्टर पर इन ऑपरेशनों को कुशल बनाने के लिए, आपको एक इंडेक्स बनाने और popcount जुड़े दोनों मामलों में इसका प्रभावी ढंग से उपयोग करने की popcount । यहां RRR इंडेक्स का अच्छा अवलोकन है। और, जहां तक ​​मैं बता सकता हूं, सबसे उन्नत आधुनिक दृष्टिकोण का वर्णन अंतरिक्ष-कुशल, उच्च-प्रदर्शन रैंक और असम्बद्ध बिट अनुक्रमों पर चयनित संरचनाओं में किया गया है ।

संकलक अनुकूलन

popcount इतना व्यापक हो गया है कि GCC और popcount दोनों इसका पता लगाने में सक्षम हैं और इसे एक अंतर्निहित निर्देश के साथ बदल सकते हैं। इस क्लैपी की कल्पना करें: "ओह, मैं देखता हूं कि आप popcount को लागू करने की कोशिश कर रहे हैं, मुझे बाहर जाने दो और इसे आपके लिए ठीक कर popcount !" इसी LLVM कोड यहाँ है । डैनियल लेमायर इसे आधुनिक संकलक के अद्भुत दिमाग के उदाहरण के रूप में उद्धृत करता है।

निष्कर्ष

अपने इतिहास की शुरुआत में रहस्य में डूबा हुआ, popcount निर्देश का उपयोग हर जगह किया जाना popcount , हालांकि यह थोड़ा असामान्य सीपीयू निर्देश रहा। मुझे यह पसंद है कि जिस तरह से यह कंप्यूटर विज्ञान के विभिन्न क्षेत्रों को जोड़ता है, और मुझे आश्चर्य है कि ऐसे अन्य अजीब निर्देश मौजूद हैं। यदि आपका अपना पसंदीदा है, तो मैं उसके बारे में सुनना चाहूंगा!