ब्रांच (कंप्यूटर साइंस): Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
{{more citations needed|date=June 2009}} | {{more citations needed|date=June 2009}} | ||
{{Machine code}} | {{Machine code}} | ||
एक शाखा एक [[कंप्यूटर प्रोग्राम]] में एक निर्देश है जो एक कंप्यूटर को एक | एक शाखा एक [[कंप्यूटर प्रोग्राम]] में एक निर्देश है जो एक कंप्यूटर को एक भिन्न निर्देश अनुक्रम निष्पादित करना प्रारंभ कर सकता है और इस प्रकार निर्देशों को क्रियान्वित करने के अपने डिफ़ॉल्ट व्यवहार से विचलित हो सकता है।{{efn|At least conceptually; see [[out-of-order execution]].}} ''ब्रांच'' (या ''ब्रांचिंग'', ''ब्रांच्ड'') ब्रांच इंस्ट्रक्शन को निष्पादित करने के परिणामस्वरूप निष्पादन को एक भिन्न निर्देश अनुक्रम में स्विच करने के कार्य को भी संदर्भित कर सकता है। शाखा निर्देशों का उपयोग प्रोग्राम लूप और सशर्त में नियंत्रण प्रवाह को प्रारम्भ करने के लिए किया जाता है (अर्थात, निर्देशों के एक विशेष अनुक्रम को केवल तभी निष्पादित किया जाता है जब कुछ शर्तें पूरी होती हैं)। | ||
एक शाखा निर्देश या तो एक ''बिना शर्त शाखा'' हो सकता है, जिसके परिणामस्वरूप | एक शाखा निर्देश या तो एक ''बिना शर्त शाखा'' हो सकता है, जिसके परिणामस्वरूप सदैव शाखाकरण होता है, या एक ''सशर्त शाखा'' हो सकती है, जो कुछ स्थितियों के आधार पर शाखाकरण का कारण हो भी सकती है और नहीं भी। इसके अतिरिक्त , यह नए निर्देश अनुक्रम (लक्षित पता) के पते को कैसे निर्दिष्ट करता है, इसके आधार पर, एक शाखा निर्देश को सामान्यतः 'प्रत्यक्ष', 'अप्रत्यक्ष' या 'सापेक्ष' के रूप में वर्गीकृत किया जाता है, जिसका अर्थ है कि निर्देश में सम्मलित है लक्ष्य पता, या यह निर्दिष्ट करता है कि लक्ष्य पता कहाँ पाया जाना है (उदाहरण के लिए, एक रजिस्टर या मेमोरी स्थान), या यह वर्तमान और लक्ष्य पते के मध्य अंतर को निर्दिष्ट करता है। | ||
== कार्यान्वयन == | == कार्यान्वयन == | ||
| Line 11: | Line 11: | ||
शाखा निर्देश सीपीयू के [[कार्यक्रम गणक]] (या पीसी) (या इंटेल माइक्रोप्रोसेसरों पर निर्देश सूचक) की सामग्री को बदल सकते हैं। पीसी अगले मशीन निर्देश के स्मृति पते को लाने और निष्पादित करने के लिए बनाए रखता है। इसलिए, एक शाखा, यदि निष्पादित की जाती है, तो प्रोग्रामर द्वारा नियोजित एल्गोरिथम के अनुसार प्रोग्राम लॉजिक को बदलते हुए, सीपीयू को एक नए मेमोरी एड्रेस से कोड निष्पादित करने का कारण बनता है। | शाखा निर्देश सीपीयू के [[कार्यक्रम गणक]] (या पीसी) (या इंटेल माइक्रोप्रोसेसरों पर निर्देश सूचक) की सामग्री को बदल सकते हैं। पीसी अगले मशीन निर्देश के स्मृति पते को लाने और निष्पादित करने के लिए बनाए रखता है। इसलिए, एक शाखा, यदि निष्पादित की जाती है, तो प्रोग्रामर द्वारा नियोजित एल्गोरिथम के अनुसार प्रोग्राम लॉजिक को बदलते हुए, सीपीयू को एक नए मेमोरी एड्रेस से कोड निष्पादित करने का कारण बनता है। | ||
एक प्रकार की मशीन स्तरीय शाखा जंप इंस्ट्रक्शन है। हो सकता है या न हो कि पीसी को कुछ नए, | एक प्रकार की मशीन स्तरीय शाखा जंप इंस्ट्रक्शन है। हो सकता है या न हो कि पीसी को कुछ नए, भिन्न मूल्य के साथ लोड या संशोधित किया जा रहा हो, जो सामान्य रूप से होता (निम्नलिखित, अगले निर्देश को इंगित करने के लिए वर्तमान निर्देश से आगे बढ़ाया जा रहा है)। छलांग में सामान्यतः ''बिना शर्त'' और ''सशर्त'' रूप होते हैं जहां बाद वाले को कुछ शर्तों के आधार पर ''लिया'' या ''नहीं लिया'' (पीसी संशोधित किया गया है या नहीं) लिया जा सकता है। | ||
दूसरी प्रकार की मशीन स्तर शाखा कॉल निर्देश है जिसका उपयोग [[सबरूटीन]]्स को प्रारम्भ करने के लिए किया जाता है। जंप निर्देशों की तरह, कॉल स्थिति कोड के अनुसार पीसी को संशोधित या संशोधित नहीं कर सकते हैं, | दूसरी प्रकार की मशीन स्तर शाखा कॉल निर्देश है जिसका उपयोग [[सबरूटीन]]्स को प्रारम्भ करने के लिए किया जाता है। जंप निर्देशों की तरह, कॉल स्थिति कोड के अनुसार पीसी को संशोधित या संशोधित नहीं कर सकते हैं, चूँकि , अतिरिक्त वापसी पता स्मृति में एक सुरक्षित स्थान में सहेजा जाता है (सामान्यतः स्मृति निवासी डेटा संरचना में जिसे स्टैक कहा जाता है (अमूर्त डेटा प्रकार)#हार्डवेयर स्टैक ). सबरूटीन के पूरा होने पर, यह वापसी पता पीसी पर बहाल हो जाता है, और इसलिए प्रोग्राम निष्पादन कॉल निर्देश के बाद निर्देश के साथ फिर से प्रारंभ होता है। | ||
तीसरी प्रकार की मशीन स्तरीय शाखा वापसी निर्देश है। यह स्टैक से रिटर्न एड्रेस को पॉप करता है और इसे पीसी रजिस्टर में लोड करता है, इस प्रकार कॉलिंग रूटीन पर नियंत्रण लौटाता है। वापसी के निर्देश भी सशर्त रूप से निष्पादित किए जा सकते हैं। यह वर्णन साधारण अभ्यास से संबंधित है; | तीसरी प्रकार की मशीन स्तरीय शाखा वापसी निर्देश है। यह स्टैक से रिटर्न एड्रेस को पॉप करता है और इसे पीसी रजिस्टर में लोड करता है, इस प्रकार कॉलिंग रूटीन पर नियंत्रण लौटाता है। वापसी के निर्देश भी सशर्त रूप से निष्पादित किए जा सकते हैं। यह वर्णन साधारण अभ्यास से संबंधित है; चूँकि , मशीन प्रोग्रामर के निकट स्टैक पर रिटर्न एड्रेस में हेरफेर करने की अधिक शक्तियां होती हैं, और इसलिए किसी भी संख्या में विभिन्न तरीकों से प्रोग्राम निष्पादन को पुनर्निर्देशित करता है। | ||
प्रोसेसर के आधार पर, जंप और कॉल निर्देश पीसी रजिस्टर की सामग्री को विभिन्न तरीकों से बदल सकते हैं। एक निरपेक्ष पता लोड किया जा सकता है, या पीसी की वर्तमान सामग्री में कुछ मूल्य (या विस्थापन) जोड़ा जा सकता है या इसके वर्तमान मूल्य से घटाया जा सकता है, जिससे गंतव्य पता कार्यक्रम में वर्तमान स्थान के सापेक्ष हो जाता है। विस्थापन मूल्य का स्रोत भिन्न हो सकता है, जैसे निर्देश के भीतर एम्बेडेड तत्काल मूल्य, या प्रोसेसर रजिस्टर या मेमोरी स्थान की सामग्री, या किसी स्थान की सामग्री को इंडेक्स वैल्यू में जोड़ा जाता है। | प्रोसेसर के आधार पर, जंप और कॉल निर्देश पीसी रजिस्टर की सामग्री को विभिन्न तरीकों से बदल सकते हैं। एक निरपेक्ष पता लोड किया जा सकता है, या पीसी की वर्तमान सामग्री में कुछ मूल्य (या विस्थापन) जोड़ा जा सकता है या इसके वर्तमान मूल्य से घटाया जा सकता है, जिससे गंतव्य पता कार्यक्रम में वर्तमान स्थान के सापेक्ष हो जाता है। विस्थापन मूल्य का स्रोत भिन्न हो सकता है, जैसे निर्देश के भीतर एम्बेडेड तत्काल मूल्य, या प्रोसेसर रजिस्टर या मेमोरी स्थान की सामग्री, या किसी स्थान की सामग्री को इंडेक्स वैल्यू में जोड़ा जाता है। | ||
[[उच्च स्तरीय प्रोग्रामिंग भाषा]]ओं में कार्यक्रमों का जिक्र करते समय 'शाखा' शब्द का भी उपयोग किया जा सकता है। इन शाखाओं में | [[उच्च स्तरीय प्रोग्रामिंग भाषा]]ओं में कार्यक्रमों का जिक्र करते समय 'शाखा' शब्द का भी उपयोग किया जा सकता है। इन शाखाओं में सामान्यतः विभिन्न रूपों के [[सशर्त (प्रोग्रामिंग)]] का रूप लेते हैं जो निर्देश अनुक्रम को समाहित करते हैं जो शर्तों के संतुष्ट होने पर निष्पादित होंगे। बिना शर्त शाखा निर्देश जैसे [[GOTO]] का उपयोग बिना शर्त के एक भिन्न निर्देश अनुक्रम में जाने के लिए किया जाता है। यदि एल्गोरिथ्म को एक सशर्त शाखा की आवश्यकता होती है, तो GOTO (या GOSUB सबरूटीन कॉल) एक सशर्त (कंप्यूटर प्रोग्रामिंग)#If–then(–else)|IF-THEN कथन से पहले होता है जो शर्तों को निर्दिष्ट करता है। सभी उच्च स्तरीय भाषाएं एल्गोरिदम का समर्थन करती हैं जो नियंत्रण प्रवाह # लूप्स के रूप में कोड का पुन: उपयोग कर सकती हैं, एक नियंत्रण संरचना जो निर्देशों के अनुक्रम को दोहराती है जब तक कि कुछ शर्त संतुष्ट न हो जाए जिससे लूप समाप्त हो जाए। लूप शाखा निर्देश के रूप में भी योग्य हैं। मशीन स्तर पर, लूप्स को सामान्य सशर्त छलांग के रूप में प्रारम्भ किया जाता है जो निष्पादन को दोहराए जाने वाले कोड पर पुनर्निर्देशित करता है। | ||
फ़्लैग रजिस्टर वाले [[CPU]] में, पहले वाला निर्देश फ़्लैग रजिस्टर में एक शर्त सेट करता है। पहले का निर्देश अंकगणित तर्क इकाई | अंकगणित या तर्क निर्देश हो सकता है। यह | फ़्लैग रजिस्टर वाले [[CPU]] में, पहले वाला निर्देश फ़्लैग रजिस्टर में एक शर्त सेट करता है। पहले का निर्देश अंकगणित तर्क इकाई | अंकगणित या तर्क निर्देश हो सकता है। यह अधिकांशतः शाखा के करीब होता है, चूँकि आवश्यक नहीं कि शाखा से पहले 'तुरंत' निर्देश हो। संग्रहीत स्थिति का उपयोग तब एक शाखा में किया जाता है जैसे कि 'जंप इफ ओवरफ्लो-फ्लैग सेट'। यह अस्थायी जानकारी अधिकांशतः फ़्लैग रजिस्टर में संग्रहीत होती है, किन्तुयह कहीं और भी स्थित हो सकती है। एक झंडा रेगीधीमी, सरल कंप्यूटरों में स्टर डिज़ाइन सरल है। तेज कंप्यूटरों में एक [[झंडा रजिस्टर]] गति पर अड़चन डाल सकता है, क्योंकि निर्देश जो अन्यथा समानांतर (कई निष्पादन इकाइयों में) काम कर सकते हैं, उन्हें फ्लैग बिट्स को एक विशेष क्रम में सेट करने की आवश्यकता होती है। | ||
ऐसी मशीनें भी हैं (या विशेष निर्देश) जहां कूद निर्देश द्वारा ही स्थिति की जांच की जा सकती है, जैसे ''शाखा <लेबल> यदि रजिस्टर एक्स नकारात्मक''। सरल कंप्यूटर डिजाइनों में, तुलना शाखाएं अधिक अंकगणित निष्पादित करती हैं और फ्लैग रजिस्टर शाखाओं की तुलना में अधिक शक्ति का उपयोग कर सकती हैं। तेज़ कंप्यूटर डिज़ाइन में तुलना शाखाएँ फ़्लैग रजिस्टर शाखाओं की तुलना में तेज़ी से चल सकती हैं, क्योंकि तुलना शाखाएँ गणना के रूप में समान CPU तंत्र का उपयोग करके अधिक समानता के साथ रजिस्टरों तक पहुँच सकती हैं। | ऐसी मशीनें भी हैं (या विशेष निर्देश) जहां कूद निर्देश द्वारा ही स्थिति की जांच की जा सकती है, जैसे ''शाखा <लेबल> यदि रजिस्टर एक्स नकारात्मक''। सरल कंप्यूटर डिजाइनों में, तुलना शाखाएं अधिक अंकगणित निष्पादित करती हैं और फ्लैग रजिस्टर शाखाओं की तुलना में अधिक शक्ति का उपयोग कर सकती हैं। तेज़ कंप्यूटर डिज़ाइन में तुलना शाखाएँ फ़्लैग रजिस्टर शाखाओं की तुलना में तेज़ी से चल सकती हैं, क्योंकि तुलना शाखाएँ गणना के रूप में समान CPU तंत्र का उपयोग करके अधिक समानता के साथ रजिस्टरों तक पहुँच सकती हैं। | ||
कुछ | कुछ प्रारंभिक और सरल सीपीयू आर्किटेक्चर, जो अभी भी माइक्रोकंट्रोलर्स में पाए जाते हैं, एक सशर्त कूद को प्रारम्भ नहीं कर सकते हैं, जबकि केवल एक सशर्त अगले निर्देश ऑपरेशन को छोड़ देते हैं। एक सशर्त कूद या कॉल इस प्रकार एक बिना शर्त कूद या कॉल निर्देश की सशर्त छोड़ने के रूप में कार्यान्वित की जाती है। | ||
=== उदाहरण === | === उदाहरण === | ||
[[कंप्यूटर आर्किटेक्चर]] के आधार पर, जंप इंस्ट्रक्शन के लिए [[सभा की भाषा]] [[स्मृति सहायक]] | [[कंप्यूटर आर्किटेक्चर]] के आधार पर, जंप इंस्ट्रक्शन के लिए [[सभा की भाषा]] [[स्मृति सहायक]] सामान्यतः शब्द जंप या शब्द शाखा का कुछ छोटा रूप होता है, अधिकांशतः अन्य सूचनात्मक अक्षरों (या एक अतिरिक्त पैरामीटर) के साथ स्थिति का प्रतिनिधित्व करता है। कभी-कभी अन्य विवरण भी सम्मलित होते हैं, जैसे कि छलांग की सीमा (ऑफ़सेट आकार) या एक विशेष एड्रेसिंग मोड जिसका उपयोग वास्तविक प्रभावी ऑफ़सेट का पता लगाने के लिए किया जाना चाहिए। | ||
यह तालिका मशीन स्तर की शाखा या कई प्रसिद्ध आर्किटेक्चर में पाए जाने वाले जंप निर्देशों को सूचीबद्ध करती है: | यह तालिका मशीन स्तर की शाखा या कई प्रसिद्ध आर्किटेक्चर में पाए जाने वाले जंप निर्देशों को सूचीबद्ध करती है: | ||
| Line 112: | Line 112: | ||
|} | |} | ||
<sup>*</sup> x86, PDP-11, VAX, और कुछ अन्य, कैरी-फ्लैग को सिग्नल बॉरो पर सेट करते हैं और कैरी-फ्लैग को नो बॉरो सिग्नल के लिए क्लियर करते हैं। एआरएम, [[6502]], पीआईसी, और कुछ अन्य, घटिया संचालन के लिए विपरीत कार्य करते हैं। कुछ निर्देशों के लिए कैरी फ़्लैग का यह उलटा कार्य किसके द्वारा चिह्नित किया गया है (<sup>*</sup>), | <sup>*</sup> x86, PDP-11, VAX, और कुछ अन्य, कैरी-फ्लैग को सिग्नल बॉरो पर सेट करते हैं और कैरी-फ्लैग को नो बॉरो सिग्नल के लिए क्लियर करते हैं। एआरएम, [[6502]], पीआईसी, और कुछ अन्य, घटिया संचालन के लिए विपरीत कार्य करते हैं। कुछ निर्देशों के लिए कैरी फ़्लैग का यह उलटा कार्य किसके द्वारा चिह्नित किया गया है (<sup>*</sup>), अर्थात , उधार =<u>नहीं</u> तालिका के कुछ हिस्सों में ले जाएं, किन्तुयदि अन्यथा नोट नहीं किया गया है, तो उधार लें≡कैरी। चूँकि , ऐडिटिव ऑपरेशंस को जारी रखने के लिए अधिकांश आर्किटेक्चर द्वारा उसी तरह से हैंडल किया जाता है। | ||
== शाखा निर्देशों के साथ प्रदर्शन समस्याएं == | == शाखा निर्देशों के साथ प्रदर्शन समस्याएं == | ||
उच्च प्रदर्शन प्राप्त करने के लिए, आधुनिक प्रोसेसर [[निर्देश पाइपलाइन]] हैं। उनमें कई भाग होते हैं जो प्रत्येक आंशिक रूप से एक निर्देश को संसाधित करते हैं, अपने परिणामों को पाइपलाइन में अगले चरण में फीड करते हैं, और कार्यक्रम में अगले निर्देश पर काम करना | उच्च प्रदर्शन प्राप्त करने के लिए, आधुनिक प्रोसेसर [[निर्देश पाइपलाइन]] हैं। उनमें कई भाग होते हैं जो प्रत्येक आंशिक रूप से एक निर्देश को संसाधित करते हैं, अपने परिणामों को पाइपलाइन में अगले चरण में फीड करते हैं, और कार्यक्रम में अगले निर्देश पर काम करना प्रारंभ करते हैं। यह डिज़ाइन एक विशेष अपरिवर्तनीय अनुक्रम में निर्देशों को निष्पादित करने की अपेक्षा करता है। सशर्त शाखा निर्देश इस क्रम को जानना असंभव बनाते हैं। तो सशर्त शाखाएं स्टालों का कारण बन सकती हैं जिसमें कार्यक्रम के एक भिन्न हिस्से पर पाइपलाइन को पुनरारंभ करना पड़ता है। | ||
== शाखाओं से स्टालों को कम करके प्रदर्शन में सुधार == | == शाखाओं से स्टालों को कम करके प्रदर्शन में सुधार == | ||
| Line 121: | Line 121: | ||
=== शाखा भविष्यवाणी संकेत === | === शाखा भविष्यवाणी संकेत === | ||
ऐतिहासिक रूप से, शाखा भविष्यवाणी ने आँकड़े लिए, और परिणाम का उपयोग कोड को अनुकूलित करने के लिए किया। एक प्रोग्रामर प्रोग्राम के परीक्षण संस्करण को संकलित करेगा, और इसे परीक्षण डेटा के साथ चलाएगा। परीक्षण कोड ने गिना कि शाखाओं को वास्तव में कैसे लिया गया था। जारी किए गए कोड की शाखाओं को अनुकूलित करने के लिए परीक्षण कोड के आंकड़े तब संकलक द्वारा उपयोग किए गए थे। अनुकूलन यह व्यवस्था करेगा कि सबसे तेज़ शाखा दिशा (लिया या नहीं) | ऐतिहासिक रूप से, शाखा भविष्यवाणी ने आँकड़े लिए, और परिणाम का उपयोग कोड को अनुकूलित करने के लिए किया। एक प्रोग्रामर प्रोग्राम के परीक्षण संस्करण को संकलित करेगा, और इसे परीक्षण डेटा के साथ चलाएगा। परीक्षण कोड ने गिना कि शाखाओं को वास्तव में कैसे लिया गया था। जारी किए गए कोड की शाखाओं को अनुकूलित करने के लिए परीक्षण कोड के आंकड़े तब संकलक द्वारा उपयोग किए गए थे। अनुकूलन यह व्यवस्था करेगा कि सबसे तेज़ शाखा दिशा (लिया या नहीं) सदैव सबसे अधिक बार लिया जाने वाला नियंत्रण प्रवाह पथ होगा। इसकी अनुमति देने के लिए, सीपीयू को पूर्वानुमेय शाखा समय के साथ (या कम से कम) डिज़ाइन किया जाना चाहिए। कुछ सीपीयू में निर्देश सेट होते हैं (जैसे कि पावर आईएसए) जो शाखा संकेत के साथ डिजाइन किए गए थे जिससे कि एक कंपाइलर सीपीयू को बता सके कि प्रत्येक शाखा को कैसे लिया जाए। | ||
सॉफ़्टवेयर शाखा भविष्यवाणी के साथ समस्या यह है कि इसके लिए एक जटिल सॉफ़्टवेयर विकास प्रक्रिया की आवश्यकता होती है। | सॉफ़्टवेयर शाखा भविष्यवाणी के साथ समस्या यह है कि इसके लिए एक जटिल सॉफ़्टवेयर विकास प्रक्रिया की आवश्यकता होती है। | ||
=== हार्डवेयर [[शाखा भविष्यवक्ता]] === | === हार्डवेयर [[शाखा भविष्यवक्ता|शाखा भविष्यसमया]] === | ||
किसी भी सॉफ़्टवेयर को चलाने के लिए, हार्डवेयर शाखा | किसी भी सॉफ़्टवेयर को चलाने के लिए, हार्डवेयर शाखा भविष्यसमयाओं ने आँकड़ों को इलेक्ट्रॉनिक्स में स्थानांतरित कर दिया। शाखा भविष्यसमया एक प्रोसेसर के भाग होते हैं जो एक सशर्त शाखा के परिणाम का अनुमान लगाते हैं। फिर प्रोसेसर का तर्क अपेक्षित निर्देश प्रवाह को निष्पादित करने के लिए शुरुआत से अनुमान लगाता है। एक साधारण हार्डवेयर शाखा भविष्यवाणी योजना का एक उदाहरण यह मान लेना है कि सभी पिछड़ी शाखाएं (अर्थात एक छोटे प्रोग्राम काउंटर के लिए) ली जाती हैं (क्योंकि वे एक लूप का हिस्सा हैं), और सभी आगे की शाखाएं (एक बड़े प्रोग्राम काउंटर के लिए) नहीं ली जाती हैं (क्योंकि वे एक पाश छोड़ते हैं)। विभिन्न प्रकार के परीक्षण कार्यक्रमों पर अनुकरण में उन्हें चलाकर बेहतर शाखा भविष्यसमयाओं को विकसित और सांख्यिकीय रूप से मान्य किया जाता है। अच्छे भविष्यसमया सामान्यतः किसी शाखा के पिछले निष्पादन के परिणामों की गणना करते हैं। बेहतर शाखा भविष्यवाणी इलेक्ट्रॉनिक्स में निवेश करके तेज़, अधिक महंगे कंप्यूटर तब तेज़ी से चल सकते हैं। हार्डवेयर शाखा भविष्यवाणी के साथ एक सीपीयू में, शाखा संकेत संकलक की संभवतः बेहतर शाखा भविष्यवाणी को हार्डवेयर की अधिक सरलीकृत शाखा भविष्यवाणी को ओवरराइड करने देते हैं। | ||
=== शाखा-मुक्त कोड === | === शाखा-मुक्त कोड === | ||
कुछ तर्क शाखाओं के बिना या कम शाखाओं के साथ लिखे जा सकते हैं। शाखाओं के | कुछ तर्क शाखाओं के बिना या कम शाखाओं के साथ लिखे जा सकते हैं। शाखाओं के अतिरिक्त बिटवाइज़ संचालन, [[सशर्त चाल]] या अन्य भविष्यवाणी (कंप्यूटर आर्किटेक्चर) का उपयोग करना अधिकांशतः संभव होता है।<ref>{{cite book |first=Donald |last=Knuth |author-link=Donald Knuth |title=[[The Art of Computer Programming]] |volume=4, Pre-fascicle 1A |edition=Revision 6 |year=2008 |pages=48–49}}</ref><ref>{{cite web |title=Avoiding Branches |url=https://www.chessprogramming.org/Avoiding_Branches |website=Chessprogramming wiki}}</ref> वास्तव में, [[समय पर हमला]] के कारण क्रिप्टोग्राफी के लिए ब्रांच-फ्री कोड बहुत आवश्यक है।<ref>{{cite web |title=Constant-Time Crypto |url=https://www.bearssl.org/constanttime.html |website=BearSSL}}</ref> | ||
=== [[विलंब स्लॉट]] === | === [[विलंब स्लॉट]] === | ||
एक अन्य तकनीक विलंब स्लॉट है। इस दृष्टिकोण में, शाखा के बाद एक निर्देश | एक अन्य तकनीक विलंब स्लॉट है। इस दृष्टिकोण में, शाखा के बाद एक निर्देश सदैव निष्पादित होता है। इसलिए, कंप्यूटर इस निर्देश का उपयोग उपयोगी कार्य करने के लिए कर सकता है चाहे उसकी पाइपलाइन रुके या नहीं। यह दृष्टिकोण [[जोखिम]] कंप्यूटरों में ऐतिहासिक रूप से लोकप्रिय था। संगत सीपीयू के एक परिवार में, यह मल्टीसाइकल सीपीयू (बिना पाइपलाइन के), लंबे समय तक अपेक्षित पाइपलाइनों के साथ तेज सीपीयू, और सुपरस्केलर सीपीयू (जो निर्देशों को क्रम से बाहर कर सकता है) को जटिल बनाता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 23:01, 3 March 2023
 | This article needs additional citations for verification. (June 2009) (Learn how and when to remove this template message) |
| Machine code |
|---|
| General concepts |
| Instructions |
एक शाखा एक कंप्यूटर प्रोग्राम में एक निर्देश है जो एक कंप्यूटर को एक भिन्न निर्देश अनुक्रम निष्पादित करना प्रारंभ कर सकता है और इस प्रकार निर्देशों को क्रियान्वित करने के अपने डिफ़ॉल्ट व्यवहार से विचलित हो सकता है।[lower-alpha 1] ब्रांच (या ब्रांचिंग, ब्रांच्ड) ब्रांच इंस्ट्रक्शन को निष्पादित करने के परिणामस्वरूप निष्पादन को एक भिन्न निर्देश अनुक्रम में स्विच करने के कार्य को भी संदर्भित कर सकता है। शाखा निर्देशों का उपयोग प्रोग्राम लूप और सशर्त में नियंत्रण प्रवाह को प्रारम्भ करने के लिए किया जाता है (अर्थात, निर्देशों के एक विशेष अनुक्रम को केवल तभी निष्पादित किया जाता है जब कुछ शर्तें पूरी होती हैं)।
एक शाखा निर्देश या तो एक बिना शर्त शाखा हो सकता है, जिसके परिणामस्वरूप सदैव शाखाकरण होता है, या एक सशर्त शाखा हो सकती है, जो कुछ स्थितियों के आधार पर शाखाकरण का कारण हो भी सकती है और नहीं भी। इसके अतिरिक्त , यह नए निर्देश अनुक्रम (लक्षित पता) के पते को कैसे निर्दिष्ट करता है, इसके आधार पर, एक शाखा निर्देश को सामान्यतः 'प्रत्यक्ष', 'अप्रत्यक्ष' या 'सापेक्ष' के रूप में वर्गीकृत किया जाता है, जिसका अर्थ है कि निर्देश में सम्मलित है लक्ष्य पता, या यह निर्दिष्ट करता है कि लक्ष्य पता कहाँ पाया जाना है (उदाहरण के लिए, एक रजिस्टर या मेमोरी स्थान), या यह वर्तमान और लक्ष्य पते के मध्य अंतर को निर्दिष्ट करता है।
कार्यान्वयन
शाखा निर्देश सीपीयू के कार्यक्रम गणक (या पीसी) (या इंटेल माइक्रोप्रोसेसरों पर निर्देश सूचक) की सामग्री को बदल सकते हैं। पीसी अगले मशीन निर्देश के स्मृति पते को लाने और निष्पादित करने के लिए बनाए रखता है। इसलिए, एक शाखा, यदि निष्पादित की जाती है, तो प्रोग्रामर द्वारा नियोजित एल्गोरिथम के अनुसार प्रोग्राम लॉजिक को बदलते हुए, सीपीयू को एक नए मेमोरी एड्रेस से कोड निष्पादित करने का कारण बनता है।
एक प्रकार की मशीन स्तरीय शाखा जंप इंस्ट्रक्शन है। हो सकता है या न हो कि पीसी को कुछ नए, भिन्न मूल्य के साथ लोड या संशोधित किया जा रहा हो, जो सामान्य रूप से होता (निम्नलिखित, अगले निर्देश को इंगित करने के लिए वर्तमान निर्देश से आगे बढ़ाया जा रहा है)। छलांग में सामान्यतः बिना शर्त और सशर्त रूप होते हैं जहां बाद वाले को कुछ शर्तों के आधार पर लिया या नहीं लिया (पीसी संशोधित किया गया है या नहीं) लिया जा सकता है।
दूसरी प्रकार की मशीन स्तर शाखा कॉल निर्देश है जिसका उपयोग सबरूटीन्स को प्रारम्भ करने के लिए किया जाता है। जंप निर्देशों की तरह, कॉल स्थिति कोड के अनुसार पीसी को संशोधित या संशोधित नहीं कर सकते हैं, चूँकि , अतिरिक्त वापसी पता स्मृति में एक सुरक्षित स्थान में सहेजा जाता है (सामान्यतः स्मृति निवासी डेटा संरचना में जिसे स्टैक कहा जाता है (अमूर्त डेटा प्रकार)#हार्डवेयर स्टैक ). सबरूटीन के पूरा होने पर, यह वापसी पता पीसी पर बहाल हो जाता है, और इसलिए प्रोग्राम निष्पादन कॉल निर्देश के बाद निर्देश के साथ फिर से प्रारंभ होता है।
तीसरी प्रकार की मशीन स्तरीय शाखा वापसी निर्देश है। यह स्टैक से रिटर्न एड्रेस को पॉप करता है और इसे पीसी रजिस्टर में लोड करता है, इस प्रकार कॉलिंग रूटीन पर नियंत्रण लौटाता है। वापसी के निर्देश भी सशर्त रूप से निष्पादित किए जा सकते हैं। यह वर्णन साधारण अभ्यास से संबंधित है; चूँकि , मशीन प्रोग्रामर के निकट स्टैक पर रिटर्न एड्रेस में हेरफेर करने की अधिक शक्तियां होती हैं, और इसलिए किसी भी संख्या में विभिन्न तरीकों से प्रोग्राम निष्पादन को पुनर्निर्देशित करता है।
प्रोसेसर के आधार पर, जंप और कॉल निर्देश पीसी रजिस्टर की सामग्री को विभिन्न तरीकों से बदल सकते हैं। एक निरपेक्ष पता लोड किया जा सकता है, या पीसी की वर्तमान सामग्री में कुछ मूल्य (या विस्थापन) जोड़ा जा सकता है या इसके वर्तमान मूल्य से घटाया जा सकता है, जिससे गंतव्य पता कार्यक्रम में वर्तमान स्थान के सापेक्ष हो जाता है। विस्थापन मूल्य का स्रोत भिन्न हो सकता है, जैसे निर्देश के भीतर एम्बेडेड तत्काल मूल्य, या प्रोसेसर रजिस्टर या मेमोरी स्थान की सामग्री, या किसी स्थान की सामग्री को इंडेक्स वैल्यू में जोड़ा जाता है।
उच्च स्तरीय प्रोग्रामिंग भाषाओं में कार्यक्रमों का जिक्र करते समय 'शाखा' शब्द का भी उपयोग किया जा सकता है। इन शाखाओं में सामान्यतः विभिन्न रूपों के सशर्त (प्रोग्रामिंग) का रूप लेते हैं जो निर्देश अनुक्रम को समाहित करते हैं जो शर्तों के संतुष्ट होने पर निष्पादित होंगे। बिना शर्त शाखा निर्देश जैसे GOTO का उपयोग बिना शर्त के एक भिन्न निर्देश अनुक्रम में जाने के लिए किया जाता है। यदि एल्गोरिथ्म को एक सशर्त शाखा की आवश्यकता होती है, तो GOTO (या GOSUB सबरूटीन कॉल) एक सशर्त (कंप्यूटर प्रोग्रामिंग)#If–then(–else)|IF-THEN कथन से पहले होता है जो शर्तों को निर्दिष्ट करता है। सभी उच्च स्तरीय भाषाएं एल्गोरिदम का समर्थन करती हैं जो नियंत्रण प्रवाह # लूप्स के रूप में कोड का पुन: उपयोग कर सकती हैं, एक नियंत्रण संरचना जो निर्देशों के अनुक्रम को दोहराती है जब तक कि कुछ शर्त संतुष्ट न हो जाए जिससे लूप समाप्त हो जाए। लूप शाखा निर्देश के रूप में भी योग्य हैं। मशीन स्तर पर, लूप्स को सामान्य सशर्त छलांग के रूप में प्रारम्भ किया जाता है जो निष्पादन को दोहराए जाने वाले कोड पर पुनर्निर्देशित करता है।
फ़्लैग रजिस्टर वाले CPU में, पहले वाला निर्देश फ़्लैग रजिस्टर में एक शर्त सेट करता है। पहले का निर्देश अंकगणित तर्क इकाई | अंकगणित या तर्क निर्देश हो सकता है। यह अधिकांशतः शाखा के करीब होता है, चूँकि आवश्यक नहीं कि शाखा से पहले 'तुरंत' निर्देश हो। संग्रहीत स्थिति का उपयोग तब एक शाखा में किया जाता है जैसे कि 'जंप इफ ओवरफ्लो-फ्लैग सेट'। यह अस्थायी जानकारी अधिकांशतः फ़्लैग रजिस्टर में संग्रहीत होती है, किन्तुयह कहीं और भी स्थित हो सकती है। एक झंडा रेगीधीमी, सरल कंप्यूटरों में स्टर डिज़ाइन सरल है। तेज कंप्यूटरों में एक झंडा रजिस्टर गति पर अड़चन डाल सकता है, क्योंकि निर्देश जो अन्यथा समानांतर (कई निष्पादन इकाइयों में) काम कर सकते हैं, उन्हें फ्लैग बिट्स को एक विशेष क्रम में सेट करने की आवश्यकता होती है।
ऐसी मशीनें भी हैं (या विशेष निर्देश) जहां कूद निर्देश द्वारा ही स्थिति की जांच की जा सकती है, जैसे शाखा <लेबल> यदि रजिस्टर एक्स नकारात्मक। सरल कंप्यूटर डिजाइनों में, तुलना शाखाएं अधिक अंकगणित निष्पादित करती हैं और फ्लैग रजिस्टर शाखाओं की तुलना में अधिक शक्ति का उपयोग कर सकती हैं। तेज़ कंप्यूटर डिज़ाइन में तुलना शाखाएँ फ़्लैग रजिस्टर शाखाओं की तुलना में तेज़ी से चल सकती हैं, क्योंकि तुलना शाखाएँ गणना के रूप में समान CPU तंत्र का उपयोग करके अधिक समानता के साथ रजिस्टरों तक पहुँच सकती हैं।
कुछ प्रारंभिक और सरल सीपीयू आर्किटेक्चर, जो अभी भी माइक्रोकंट्रोलर्स में पाए जाते हैं, एक सशर्त कूद को प्रारम्भ नहीं कर सकते हैं, जबकि केवल एक सशर्त अगले निर्देश ऑपरेशन को छोड़ देते हैं। एक सशर्त कूद या कॉल इस प्रकार एक बिना शर्त कूद या कॉल निर्देश की सशर्त छोड़ने के रूप में कार्यान्वित की जाती है।
उदाहरण
कंप्यूटर आर्किटेक्चर के आधार पर, जंप इंस्ट्रक्शन के लिए सभा की भाषा स्मृति सहायक सामान्यतः शब्द जंप या शब्द शाखा का कुछ छोटा रूप होता है, अधिकांशतः अन्य सूचनात्मक अक्षरों (या एक अतिरिक्त पैरामीटर) के साथ स्थिति का प्रतिनिधित्व करता है। कभी-कभी अन्य विवरण भी सम्मलित होते हैं, जैसे कि छलांग की सीमा (ऑफ़सेट आकार) या एक विशेष एड्रेसिंग मोड जिसका उपयोग वास्तविक प्रभावी ऑफ़सेट का पता लगाने के लिए किया जाना चाहिए।
यह तालिका मशीन स्तर की शाखा या कई प्रसिद्ध आर्किटेक्चर में पाए जाने वाले जंप निर्देशों को सूचीबद्ध करती है:
| condition or result | x86 | PDP-11, VAX | ARM (partly 6502) | equation |
|---|---|---|---|---|
| zero (implies equal for sub/cmp) | JZ; JNZ | BEQ; BNE | BEQ; BNE | zero; not zero |
| negative (N), sign (S), or minus (M) | JS; JNS | BMI; BPL | BMI; BPL | negative; not negative |
| arithmetic overflow (flag called O or V) | JO; JNO | BVS; BVC | BVS; BVC | overflow; not overflow |
| carry (from add, cmp, shift, etc.) | JC; JNC | BCS; BCC | BCS; BCC | carry; not carry |
| unsigned below (lower) | JB | BLO | BLO * | borrow |
| unsigned below or equal (lower or same) | JBE | BLOS | BLS * | borrow or zero |
| unsigned above or equal (higher or same) | JAE | BHIS | BHS * | not borrow |
| unsigned above (higher) | JA | BHI | BHI * | not borrow and not zero |
| signed less than | JL | BLT | BLT | sign≠overflow |
| signed less or equal | JLE | BLE | BLE | (sign≠overflow) or zero |
| signed greater or equal | JGE | BGE | BGE | sign=overflow |
| signed greater than | JG | BGT | BGT | (sign=overflow) and not zero |
* x86, PDP-11, VAX, और कुछ अन्य, कैरी-फ्लैग को सिग्नल बॉरो पर सेट करते हैं और कैरी-फ्लैग को नो बॉरो सिग्नल के लिए क्लियर करते हैं। एआरएम, 6502, पीआईसी, और कुछ अन्य, घटिया संचालन के लिए विपरीत कार्य करते हैं। कुछ निर्देशों के लिए कैरी फ़्लैग का यह उलटा कार्य किसके द्वारा चिह्नित किया गया है (*), अर्थात , उधार =नहीं तालिका के कुछ हिस्सों में ले जाएं, किन्तुयदि अन्यथा नोट नहीं किया गया है, तो उधार लें≡कैरी। चूँकि , ऐडिटिव ऑपरेशंस को जारी रखने के लिए अधिकांश आर्किटेक्चर द्वारा उसी तरह से हैंडल किया जाता है।
शाखा निर्देशों के साथ प्रदर्शन समस्याएं
उच्च प्रदर्शन प्राप्त करने के लिए, आधुनिक प्रोसेसर निर्देश पाइपलाइन हैं। उनमें कई भाग होते हैं जो प्रत्येक आंशिक रूप से एक निर्देश को संसाधित करते हैं, अपने परिणामों को पाइपलाइन में अगले चरण में फीड करते हैं, और कार्यक्रम में अगले निर्देश पर काम करना प्रारंभ करते हैं। यह डिज़ाइन एक विशेष अपरिवर्तनीय अनुक्रम में निर्देशों को निष्पादित करने की अपेक्षा करता है। सशर्त शाखा निर्देश इस क्रम को जानना असंभव बनाते हैं। तो सशर्त शाखाएं स्टालों का कारण बन सकती हैं जिसमें कार्यक्रम के एक भिन्न हिस्से पर पाइपलाइन को पुनरारंभ करना पड़ता है।
शाखाओं से स्टालों को कम करके प्रदर्शन में सुधार
सशर्त शाखाओं से स्टालों को कम करके कई तकनीकें गति में सुधार करती हैं।
शाखा भविष्यवाणी संकेत
ऐतिहासिक रूप से, शाखा भविष्यवाणी ने आँकड़े लिए, और परिणाम का उपयोग कोड को अनुकूलित करने के लिए किया। एक प्रोग्रामर प्रोग्राम के परीक्षण संस्करण को संकलित करेगा, और इसे परीक्षण डेटा के साथ चलाएगा। परीक्षण कोड ने गिना कि शाखाओं को वास्तव में कैसे लिया गया था। जारी किए गए कोड की शाखाओं को अनुकूलित करने के लिए परीक्षण कोड के आंकड़े तब संकलक द्वारा उपयोग किए गए थे। अनुकूलन यह व्यवस्था करेगा कि सबसे तेज़ शाखा दिशा (लिया या नहीं) सदैव सबसे अधिक बार लिया जाने वाला नियंत्रण प्रवाह पथ होगा। इसकी अनुमति देने के लिए, सीपीयू को पूर्वानुमेय शाखा समय के साथ (या कम से कम) डिज़ाइन किया जाना चाहिए। कुछ सीपीयू में निर्देश सेट होते हैं (जैसे कि पावर आईएसए) जो शाखा संकेत के साथ डिजाइन किए गए थे जिससे कि एक कंपाइलर सीपीयू को बता सके कि प्रत्येक शाखा को कैसे लिया जाए।
सॉफ़्टवेयर शाखा भविष्यवाणी के साथ समस्या यह है कि इसके लिए एक जटिल सॉफ़्टवेयर विकास प्रक्रिया की आवश्यकता होती है।
हार्डवेयर शाखा भविष्यसमया
किसी भी सॉफ़्टवेयर को चलाने के लिए, हार्डवेयर शाखा भविष्यसमयाओं ने आँकड़ों को इलेक्ट्रॉनिक्स में स्थानांतरित कर दिया। शाखा भविष्यसमया एक प्रोसेसर के भाग होते हैं जो एक सशर्त शाखा के परिणाम का अनुमान लगाते हैं। फिर प्रोसेसर का तर्क अपेक्षित निर्देश प्रवाह को निष्पादित करने के लिए शुरुआत से अनुमान लगाता है। एक साधारण हार्डवेयर शाखा भविष्यवाणी योजना का एक उदाहरण यह मान लेना है कि सभी पिछड़ी शाखाएं (अर्थात एक छोटे प्रोग्राम काउंटर के लिए) ली जाती हैं (क्योंकि वे एक लूप का हिस्सा हैं), और सभी आगे की शाखाएं (एक बड़े प्रोग्राम काउंटर के लिए) नहीं ली जाती हैं (क्योंकि वे एक पाश छोड़ते हैं)। विभिन्न प्रकार के परीक्षण कार्यक्रमों पर अनुकरण में उन्हें चलाकर बेहतर शाखा भविष्यसमयाओं को विकसित और सांख्यिकीय रूप से मान्य किया जाता है। अच्छे भविष्यसमया सामान्यतः किसी शाखा के पिछले निष्पादन के परिणामों की गणना करते हैं। बेहतर शाखा भविष्यवाणी इलेक्ट्रॉनिक्स में निवेश करके तेज़, अधिक महंगे कंप्यूटर तब तेज़ी से चल सकते हैं। हार्डवेयर शाखा भविष्यवाणी के साथ एक सीपीयू में, शाखा संकेत संकलक की संभवतः बेहतर शाखा भविष्यवाणी को हार्डवेयर की अधिक सरलीकृत शाखा भविष्यवाणी को ओवरराइड करने देते हैं।
शाखा-मुक्त कोड
कुछ तर्क शाखाओं के बिना या कम शाखाओं के साथ लिखे जा सकते हैं। शाखाओं के अतिरिक्त बिटवाइज़ संचालन, सशर्त चाल या अन्य भविष्यवाणी (कंप्यूटर आर्किटेक्चर) का उपयोग करना अधिकांशतः संभव होता है।[1][2] वास्तव में, समय पर हमला के कारण क्रिप्टोग्राफी के लिए ब्रांच-फ्री कोड बहुत आवश्यक है।[3]
विलंब स्लॉट
एक अन्य तकनीक विलंब स्लॉट है। इस दृष्टिकोण में, शाखा के बाद एक निर्देश सदैव निष्पादित होता है। इसलिए, कंप्यूटर इस निर्देश का उपयोग उपयोगी कार्य करने के लिए कर सकता है चाहे उसकी पाइपलाइन रुके या नहीं। यह दृष्टिकोण जोखिम कंप्यूटरों में ऐतिहासिक रूप से लोकप्रिय था। संगत सीपीयू के एक परिवार में, यह मल्टीसाइकल सीपीयू (बिना पाइपलाइन के), लंबे समय तक अपेक्षित पाइपलाइनों के साथ तेज सीपीयू, और सुपरस्केलर सीपीयू (जो निर्देशों को क्रम से बाहर कर सकता है) को जटिल बनाता है।
यह भी देखें
- शाखा विलंब स्लॉट
- शाखा भविष्यवाणी
- शाखा तालिका
- सशर्त (प्रोग्रामिंग)
- बहाव को काबू करें
- अप्रत्यक्ष शाखा
- कार्यक्रम गणक
- सबरूटीन
- स्पेगेटी कोड
टिप्पणियाँ
- ↑ At least conceptually; see out-of-order execution.
संदर्भ
- ↑ Knuth, Donald (2008). The Art of Computer Programming. Vol. 4, Pre-fascicle 1A (Revision 6 ed.). pp. 48–49.
- ↑ "Avoiding Branches". Chessprogramming wiki.
- ↑ "Constant-Time Crypto". BearSSL.
बाहरी संबंध
- Free IA-32 and x86-64 documentation, provided by Intel
- The PDP-11 FAQ
- The ARM instruction set
