विभाजन के सवाल पर

हमें एक छोटा लेकिन बेहद दिलचस्प सामरिक अभ्यास करने का अवसर मिला

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

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

और मुझे दुख था कि एआरएम के लोग मुझसे ज्यादा स्मार्ट हैं, और मैं इंटरनेट पर लंबे समय से देख रहा था कि वे यह कैसे करते हैं। मुझे एआरएम वेबसाइट पर निष्पादन समय के बारे में कोई जानकारी नहीं मिली, एसटीएम 32 पर एक सामग्री में यह संकेत दिया गया था कि विभाजन 2 से 7 घड़ी चक्रों से होता है, जो टिप्पणियों से मेल खाता है, लेकिन यह कैसे किया जाता है, इस बारे में कोई जानकारी नहीं है।

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

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

तो, हम जल्दी से (7 चक्रों से अधिक नहीं) 32-बिट परिणाम प्राप्त करने के लिए दो 32-बिट संख्या को कैसे विभाजित करते हैं।

शुरुआत करने के लिए, हम याद करते हैं कि बाइनरी अंकगणितीय में विभाजन को आम तौर पर किस तरह से किया जाता है
क्लासिक रूप। एल्गोरिथ्म काफी सरल और सीधा है - हम डिवाइडर को लाभांश से घटाते हैं। यदि परिणाम गैर-नकारात्मक है (हम अहस्ताक्षरित संख्याओं को विभाजित करते हैं), तो हम परिणाम के अगले अंक को एक के बराबर बनाते हैं और परिणाम को अगले लाभांश के रूप में मानते हैं, अन्यथा परिणाम का अगला बिट 0. है। अगले उपाय से पहले, हम भाजक को आधा कर देते हैं (या तो इसे दाईं ओर शिफ्ट कर देते हैं, या डिविडेंड को बाईं ओर शिफ्ट करें) और थोड़ा वजन 2 गुना कम करें (इसी तरह की शिफ्ट से)। इस प्रकार, हमें एक घड़ी चक्र में परिणाम का एक सा मिलता है और पूरा ऑपरेशन 32 घड़ी चक्रों में चलेगा। इस प्रक्रिया में अभी भी एक प्रारंभिक बदलाव है, लेकिन यह समग्र रूप से स्थिति के आकलन को प्रभावित नहीं करता है। हम तेजी लाएंगे, लेकिन कैसे?

हम ध्यान दें कि परिणामी एल्गोरिदम एक क्रमिक सन्निकटन के साथ एडीसी के संचालन से दृढ़ता से मिलता जुलता है और याद दिलाता है कि अन्य रूपांतरण विधियां हैं, बहुत तेजी से - समानांतर रूपांतरण। क्या होगा अगर ...

हम विभाजक से न केवल लाभांश, बल्कि लाभांश * 2 और लाभांश * 3 (एक ही समय में, तीन योजक पर) से घटाएंगे, फिर हमें जानकारी के तीन बिट्स (परिणाम के संकेत) मिलेंगे, जो 4 मान लेते हैं, इसलिए आप एक बार में उनसे 2 बिट निकाल सकते हैं परिणाम है। अगला, हम परिणाम के 3.4.5 बिट्स के लिए एक समान दृष्टिकोण को एक्सट्रपलेशन करते हैं।
प्रति चक्र के 5 बिट्स की जानकारी प्राप्त करने के लिए, हमें 31 योजक की आवश्यकता है, जिनमें से प्रत्येक पर लाभांश-भाजक * n ऑपरेशन (1-31) किया जाएगा, परिणाम के संकेत एनकोडर के माध्यम से पारित किए जाते हैं और हम तुरंत परिणाम के 5 बिट प्राप्त करेंगे। फिर हम लाभांश को 5 अंकों के बाईं ओर स्थानांतरित करते हैं और तैयार होने तक दोहराते हैं। तब हमें ऑपरेशन पूरा करने के लिए 32/5 = 6.4 => 7 उपायों की आवश्यकता होती है।

काम के लिए, हमें 31 + x योजक की आवश्यकता है, यह बहुत कुछ प्रतीत होता है, लेकिन हमारे पास पहले से ही है, क्योंकि हमारे पास प्रति चक्र 32 * 32 गुणन ऑपरेशन है, और इसे लागू करने के लिए हम 32 योजक के बिना नहीं कर सकते हैं (ठीक है, मुझे लगता है ...) ), ताकि हमारे पास पहले से ही आवश्यक उपकरण हैं, एकमात्र प्रश्न एक तीव्र बदलाव को साकार करने के लिए नियंत्रण सर्किट और मल्टीप्लेक्सर्स के ढेर का निर्माण करना है, लेकिन यह पूरी तरह से हल करने योग्य है।

तो 7 चरणों में विभाजित करने का कार्य हल किया गया है, यह सवाल बना हुआ है - इस समय को कैसे कम किया जा सकता है, क्योंकि अध्ययन किए गए एमके में यह 7. से कम हो सकता है। एल्गोरिथ्म की तैयारी के चरण में लाभांश (सी) और विभाजक (सी) के सबसे महत्वपूर्ण अंकों की संख्या निर्धारित करने के लिए पूछना समाधान है। यह तुरंत स्पष्ट हो जाएगा कि भागफल के कितने उच्च बिट्स शून्य के बराबर हैं, ताकि हम एल्गोरिथ्म के पहले या कई चरणों को छोड़ सकें। उदाहरण के लिए, यदि सी <3, तो परिणाम तुरंत शून्य है और हम ऑपरेशन पूरा करते हैं, सुनिश्चित करें कि आप उपायों की संख्या के लिए एक सूत्र प्राप्त कर सकते हैं, लेकिन मैं पहले से ही ऊब गया था।

दिलचस्प है, यूडिव ऑपरेशन केवल भागफल देता है, हालांकि शेष स्पष्ट रूप से अंदर कहीं रहता है। सिद्धांत रूप में, इसे दो चरणों में प्राप्त करना मुश्किल नहीं है, जो कि छद्म कोड विभाजक-निजी * डिवाइडर को निष्पादित करके मशीन कोड के अध्ययनित टुकड़े में किया गया था, लेकिन यह किसी भी 2 चरणों के लिए है, रजिस्टर जोड़ी में इसे तुरंत क्यों न दें - मुझे इसका उत्तर नहीं पता है एक सवाल।

सामान्य तौर पर, जीडीपी को पूरा करें, उसे बताएं कि हम एमके में विभाजन जरूर करेंगे अगर यह अभी भी उसके लिए दिलचस्प है।

पुनश्च: वैसे, जब मैं केडीपीवी की तलाश कर रहा था (जैसा कि आपने देखा, मुझे यह नहीं मिला), मैंने एक स्पष्ट गलत शिलालेख के साथ देखा "आपको शून्य से विभाजित नहीं करना चाहिए।" मुझे निश्चितता के साथ कहना चाहिए कि शून्य से विभाजित करना संभव है, विभाजित नहीं किया जा सकता है। लेकिन गंभीरता से, विभिन्न आर्किटेक्चर में वे शून्य से अलग-अलग विभाजित होते हैं, x86 में हमें एक अपवाद मिलता है (यह एक अविस्मरणीय गलती 200 है), कुछ में हमें एक लाभांश या शून्य मिलता है, लेकिन मैंने कभी भी अधिकतम पूर्णांक नहीं देखा है। ARM n / 0 = 0/0 में और यह 0 निकला।