ब्रांच (कंप्यूटर साइंस)
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] शाखा (ब्रांचिंग या ब्रांच्ड) भी अधिनियम का उल्लेख कर सकता है। शाखा निर्देश निष्पादित करने के परिणामस्वरूप निष्पादन को भिन्न निर्देश अनुक्रम में स्विच करना। शाखा निर्देशों का उपयोग प्रोग्राम लूप और प्रतिबंध में नियंत्रण प्रवाह को प्रारम्भ करने के लिए किया जाता है (अर्थात, निर्देशों के विशेष अनुक्रम को केवल तभी निष्पादित किया जाता है जब कुछ नियम पूर्ण होते है)।
शाखा निर्देश या तो बिना नियमानुसार शाखा हो सकता है, जिसके परिणामस्वरूप सदैव शाखाकरण होता है, या नियमानुसार शाखा हो सकती है, जो कुछ स्थितियों के आधार पर शाखाओं में विखंडित हो सकती है या नहीं भी हो सकती है। इसके अतिरिक्त, यह इस बात पर निर्भर करता है कि यह नए निर्देश अनुक्रम ("लक्ष्य" ज्ञात) के ज्ञात को कैसे निर्दिष्ट करता है, इसके आधार पर, शाखा निर्देश को सामान्यतः 'प्रत्यक्ष', 'अप्रत्यक्ष' या 'सापेक्ष' के रूप में वर्गीकृत किया जाता है, जिसका अर्थ है कि निर्देश में लक्ष्य ज्ञात होता है, (उदाहरण के लिए, रजिस्टर या मेमोरी स्थान), या वर्तमान और लक्ष्य ज्ञातों के मध्य अंतर को निर्दिष्ट करता है।
कार्यान्वयन
शाखा निर्देश सीपीयू के कार्यक्रम गणक (या पीसी) (या इंटेल माइक्रोप्रोसेसरों पर निर्देश सूचक) की सामग्री को परिवर्तित कर सकते हैं। पीसी अगले मशीन निर्देश के स्मृति ज्ञात करने और निष्पादित करने के लिए बनाए रखता है। इसलिए, शाखा यदि निष्पादित की जाती है, तो प्रोग्रामर द्वारा नियोजित एल्गोरिथम के अनुसार प्रोग्राम लॉजिक को परिवर्तित करते हुए, सीपीयू को नए मेमोरी एड्रेस से कोड निष्पादित करने का कारण बनता है।
विशेष प्रकार की मशीन स्तरीय शाखा जंप इंस्ट्रक्शन है। सामान्य रूप से पीसी में कुछ नए, भिन्न मूल्य के साथ लोड या संशोधित किया जाता है (निम्नलिखित, अगले निर्देश को प्रदर्शित करने के लिए वर्तमान निर्देश से आगे बढ़ाया जा रहा है)। सामान्यतः बिना नियमानुसार के रूप होते हैं जहां कुछ नियमानुसार के आधार के पश्चात लिया जा सकता है या नहीं लिया जा सकता है (पीसी संशोधित है या नहीं)।
द्वितीय प्रकार की मशीन स्तर शाखा कॉल निर्देश है जिसका उपयोग सबरूटीन को प्रारम्भ करने के लिए किया जाता है। जंप निर्देशों के जैसे, कॉल स्थिति कोड के अनुसार पीसी को संशोधित नहीं कर सकते हैं, चूँकि, अतिरिक्त वापसी एड्रेस स्मृति में सुरक्षित स्थान में सरल किया जाता है (सामान्यतः स्मृति निवासी डेटा संरचना में जिसे स्टैक कहा जाता हैI) सबरूटीन के पूर्ण होने पर, यह वापसी ज्ञात पीसी पर पूर्ववत् हो जाता है, और इसलिए प्रोग्राम निष्पादन कॉल निर्देश के पश्चात निर्देश के साथ फिर से प्रारंभ होता है।
तृतीय प्रकार की मशीन स्तरीय शाखा वापसी निर्देश है। यह स्टैक से रिटर्न एड्रेस को पॉप करता है और इसे पीसी रजिस्टर में लोड करता है, इस प्रकार कॉलिंग रूटीन पर नियंत्रण आता है। वापसी के निर्देश भी नियमानुसार रूप से निष्पादित किए जा सकते हैं। यह वर्णन साधारण अभ्यास से संबंधित है; चूँकि, मशीन प्रोग्रामर के निकट स्टैक पर रिटर्न एड्रेस में आदान-प्रदान करने की अधिक शक्तियां होती हैं, और इसलिए किसी भी संख्या में विभिन्न विधियों से प्रोग्राम निष्पादन को पुनर्निर्देशित करता है।
प्रोसेसर के आधार पर, जंप और कॉल निर्देश पीसी रजिस्टर की सामग्री को विभिन्न विधियों से परिवर्तित कर सकते हैं। निरपेक्ष एड्रेस लोड किया जा सकता है, या पीसी की वर्तमान सामग्री में कुछ मूल्य (या विस्थापन) जोड़ा जा सकता है या इसके वर्तमान मूल्य से घटाया जा सकता है, जिससे गंतव्य एड्रेस कार्यक्रम में वर्तमान स्थान के सापेक्ष हो जाता है। विस्थापन मूल्य का स्रोत भिन्न हो सकता है, जैसे निर्देश के भीतर एम्बेडेड अविलम्ब मूल्य, या प्रोसेसर रजिस्टर या मेमोरी स्थान की सामग्री, या किसी स्थान की सामग्री को इंडेक्स मान में जोड़ा जाता है।
उच्च स्तरीय प्रोग्रामिंग भाषाओं में कार्यक्रमों का वर्णन करते समय 'शाखा' शब्द का भी उपयोग किया जा सकता है। इन शाखाओं में सामान्यतः विभिन्न रूप नियमानुसार का रूप लेते हैं जो निर्देश अनुक्रम को समाहित करते हैं जो नियम के संतुष्ट होने पर निष्पादित होंगे। बिना नियम शाखा निर्देश जैसे गोटो का उपयोग बिना नियम के भिन्न निर्देश अनुक्रम में जाने के लिए किया जाता है। यदि एल्गोरिथ्म को नियमानुसार शाखा की आवश्यकता होती है, तो गोटो (या गोसुब सबरूटीन कॉल) इफ-देन (IF-THEN) कथन द्वारा नियमानुसार को निर्दिष्ट करने से पूर्व होता है। सभी उच्च स्तरीय भाषाएं एल्गोरिदम का समर्थन करती हैं जो नियंत्रण प्रवाह लूप्स के रूप में कोड का पुन: उपयोग कर सकती हैं, नियंत्रण संरचना जो निर्देशों के अनुक्रम को दोहराती है जब तक कि कुछ नियम संतुष्ट न हो जाए जिससे लूप समाप्त हो जाए। लूप शाखा निर्देश के रूप में भी योग्य हैं। मशीन स्तर पर, लूप्स को सामान्य नियमानुसार के रूप में प्रारम्भ किया जाता है जो निष्पादन को दोहराए जाने वाले कोड पर पुनर्निर्देशित करता है।
फ़्लैग रजिस्टर वाले सीपीयू में, प्रथम वाला निर्देश फ़्लैग रजिस्टर के अनुसार सेट करता है। प्रथम का निर्देश अंकगणित या तर्क निर्देश हो सकता है। यह अधिकांशतः शाखा के निकटतम होता है, चूँकि आवश्यक नहीं कि निर्देश शाखा से ठीक पहले हो। संग्रहीत स्थिति का उपयोग तब शाखा में किया जाता है जैसे कि 'जंप इफ ओवरफ्लो-फ्लैग सेट' किया जाता है। यह अस्थायी जानकारी अधिकांशतः फ़्लैग रजिस्टर में संग्रहीत होती है, किन्तु यह कहीं और भी स्थित हो सकती है। धीमी, सरल कंप्यूटरों में फ्लैग रजिस्टर डिज़ाइन सरल है। तीव्र कंप्यूटरों में फ्लैग रजिस्टर गति पर बाधा उत्पन्न कर सकता है, क्योंकि निर्देश जो अन्यथा समानांतर (कई निष्पादन इकाइयों में) कार्य कर सकते हैं, उन्हें फ्लैग बिट्स को विशेष क्रम में सेट करने की आवश्यकता होती है।
ऐसी मशीनें (या विशेष निर्देश) भी हैं जहां जंप निर्देश द्वारा ही स्थिति का परीक्षण किया जा सकता है, जैसे branch <label> यदि एक्स नकारात्मक पंजीकृत है। सरल कंप्यूटर डिजाइनों में, तुलना शाखाएं अधिक अंकगणित निष्पादित करती हैं और फ्लैग रजिस्टर शाखाओं की तुलना में अधिक शक्ति का उपयोग कर सकती हैं। तीव्र कंप्यूटर डिज़ाइन में तुलना शाखाएँ फ़्लैग रजिस्टर शाखाओं की तुलना में तीव्रता से चल सकती हैं, क्योंकि तुलना शाखाएँ गणना के रूप में समान सीपीयू तंत्र का उपयोग करके अधिक समानता के साथ रजिस्टरों तक पहुँच सकती हैं।
कुछ प्रारंभिक और सरल सीपीयू आर्किटेक्चर, जो अभी भी माइक्रोकंट्रोलर्स में पाए जाते हैं, नियमानुसार जंप को प्रारम्भ नहीं कर सकते हैं, जबकि केवल नियमानुसार अगले निर्देश ऑपरेशन को त्याग देते हैं। नियमानुसार जंप या कॉल इस प्रकार बिना नियम जंप या कॉल निर्देश के नियमानुसार त्याग के रूप में कार्यान्वित की जाती है।
उदाहरण
कंप्यूटर आर्किटेक्चर के आधार पर, जंप इंस्ट्रक्शन के लिए सभा की भाषा स्मृति सहायक सामान्यतः शब्द जंप या शब्द शाखा का कुछ छोटा रूप होता है, अधिकांशतः अन्य सूचनात्मक अक्षरों (या अतिरिक्त पैरामीटर) के साथ स्थिति का प्रतिनिधित्व करता है। कभी-कभी अन्य विवरण भी सम्मलित होते हैं, जैसे कि छलांग की सीमा (ऑफ़सेट आकार) या विशेष एड्रेसिंग मोड जिसका उपयोग वास्तविक प्रभावी ऑफ़सेट का पता लगाने के लिए किया जाना चाहिए।
यह तालिका मशीन स्तर की शाखा या कई प्रसिद्ध आर्किटेक्चर में पाए जाने वाले जंप निर्देशों को सूचीबद्ध करती है:
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