डेटा निर्भरता

कंप्यूटर विज्ञान में डेटा निर्भरता एक ऐसी स्थिति है जिसमें एक कार्यक्रम वक्तव्य (निर्देश) पिछले स्टेटमेंट के डेटा को संदर्भित करता है। संकलक सिद्धांत में, कथनों (या निर्देशों) के बीच डेटा निर्भरता की खोज करने के लिए उपयोग की जाने वाली तकनीक को निर्भरता विश्लेषण कहा जाता है।

निर्भरताएँ तीन प्रकार की होती हैं: डेटा, नाम और नियंत्रण।

डेटा निर्भरताएँ

अनुमान कथन $S_{1}$ और $S_{2}$, $S_{2}$ पर निर्भर करता है $S_{1}$ अगर:

$\left[I(S_{1})\cap O(S_{2})\right]\cup \left[O(S_{1})\cap I(S_{2})\right]\cup \left[O(S_{1})\cap O(S_{2})\right]\neq \varnothing$

कहाँ:

• $I(S_{i})$ द्वारा पढ़े गए स्मृति स्थानों का समूह है $S_{i}$,
• $O(S_{j})$ द्वारा लिखित स्मृति स्थानों का समूह है $S_{j}$, और
• से एक व्यवहार्य रन-टाइम निष्पादन पथ है $S_{1}$ को $S_{2}$.

इस स्थिति को बर्नस्टीन स्थिति कहा जाता है, जिसका नाम ए जे बर्नस्टीन ने रखा है।

तीन मामले मौजूद हैं:

• विरोधी निर्भरता: $I(S_{1})\cap O(S_{2})\neq \varnothing$, $S_{1}\rightarrow S_{2}$ और $S_{1}$ पहले कुछ पढ़ता है $S_{2}$ इसे अधिलेखित कर देता है
• प्रवाह (डेटा) निर्भरता: $O(S_{1})\cap I(S_{2})\neq \varnothing$, $S_{1}\rightarrow S_{2}$ और $S_{1}$ कुछ पढ़ने से पहले लिखता है $S_{2}$
• आउटपुट निर्भरता: $O(S_{1})\cap O(S_{2})\neq \varnothing$, $S_{1}\rightarrow S_{2}$ और दोनों एक ही मेमोरी लोकेशन लिखते हैं।

प्रवाह निर्भरता (सच्ची निर्भरता)

प्रवाह निर्भरता, जिसे डेटा निर्भरता या सच्ची निर्भरता या रीड-आफ्टर-राइट (RAW) के रूप में भी जाना जाता है, तब होती है जब कोई निर्देश पिछले निर्देश के परिणाम पर निर्भर करता है।

1. ए = 3
2. बी = ए
3. सी = बी

निर्देश 3 वास्तव में निर्देश 2 पर निर्भर है, क्योंकि C का अंतिम मान निर्देश अद्यतन करने वाले B पर निर्भर करता है। निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, क्योंकि B का अंतिम मान निर्देश अद्यतन करने वाले A पर निर्भर करता है। चूँकि निर्देश 3 वास्तव में निर्भर है निर्देश 2 पर और निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, निर्देश 3 भी वास्तव में निर्देश 1 पर निर्भर है। निर्देश स्तर समानता इसलिए इस उदाहरण में एक विकल्प नहीं है।

विरोधी निर्भरता

एक एंटी-डिपेंडेंसी, जिसे राइट-आफ्टर-रीड (WAR) के रूप में भी जाना जाता है, तब होता है जब किसी निर्देश को एक मान की आवश्यकता होती है जिसे बाद में अपडेट किया जाता है। निम्नलिखित उदाहरण में, निर्देश 2 एंटी-निर्देश 3 पर निर्भर करता है - इन निर्देशों का क्रम बदला नहीं जा सकता है, न ही उन्हें समानांतर में निष्पादित किया जा सकता है (संभवतः निर्देश क्रम बदल रहा है), क्योंकि यह ए के अंतिम मूल्य को प्रभावित करेगा।

1. बी = 3
2. ए = बी + 1
3. बी = 7

उदाहरण :

 एमयूएल आर3,आर1,आर2
 R2,R5,R6 जोड़ें

स्पष्ट है कि इन दोनों निर्देशों के बीच परस्पर-निर्भरता है। सबसे पहले हम R2 पढ़ते हैं फिर दूसरे निर्देश में हम एक नया लिख ​​रहे होते हैं इसके लिए मूल्य.

एंटी-डिपेंडेंसी नाम निर्भरता का एक उदाहरण है। अर्थात्, वेरिएबल्स का नाम बदलने से निर्भरता दूर हो सकती है, जैसा कि अगले उदाहरण में है:

1. बी = 3
एन. बी2 = बी
2. ए = बी2 + 1
3. बी = 7

एक नए निर्देश, निर्देश एन में एक नए चर, बी2 को बी की एक प्रति के रूप में घोषित किया गया है। 2 और 3 के बीच की निर्भरता को हटा दिया गया है, जिसका अर्थ है कि इन निर्देशों को अब समानांतर में निष्पादित किया जा सकता है। हालाँकि, संशोधन ने एक नई निर्भरता पेश की है: निर्देश 2 अब वास्तव में निर्देश एन पर निर्भर है, जो वास्तव में निर्देश 1 पर निर्भर है। प्रवाह निर्भरता के रूप में, इन नई निर्भरताओं को सुरक्षित रूप से हटाना असंभव है।

आउटपुट निर्भरता

आउटपुट निर्भरता, जिसे राइट-आफ्टर-राइट (WAW) के रूप में भी जाना जाता है, तब होती है जब निर्देशों का क्रम किसी वेरिएबल के अंतिम आउटपुट मान को प्रभावित करेगा। नीचे दिए गए उदाहरण में, निर्देश 3 और 1 के बीच एक आउटपुट निर्भरता है - इस उदाहरण में निर्देशों के क्रम को बदलने से ए का अंतिम मान बदल जाएगा, इस प्रकार इन निर्देशों को समानांतर में निष्पादित नहीं किया जा सकता है।

1. बी = 3
2. ए = बी + 1
3. बी = 7

निर्भरता-विरोधी की तरह, आउटपुट निर्भरताएँ नाम निर्भरताएँ हैं। अर्थात्, उन्हें वेरिएबल्स का नाम बदलकर हटाया जा सकता है, जैसा कि उपरोक्त उदाहरण के नीचे दिए गए संशोधन में है:

1. बी2 = 3
2. ए = बी2 + 1
3. बी = 7

डेटा निर्भरता के लिए आमतौर पर इस्तेमाल की जाने वाली नामकरण परंपरा निम्नलिखित है: पढ़ने के बाद लिखने या RAW (प्रवाह निर्भरता), पढ़ने के बाद लिखने या WAR (विरोधी निर्भरता), या लिखने के बाद लिखने या WAW (आउटपुट निर्भरता)।

नियंत्रण निर्भरता

एक निर्देश बी की पूर्ववर्ती निर्देश ए पर नियंत्रण निर्भरता होती है यदि ए का परिणाम यह निर्धारित करता है कि बी को निष्पादित किया जाना चाहिए या नहीं। निम्नलिखित उदाहरण में, निर्देश $S_{2}$ निर्देश पर नियंत्रण निर्भरता है $S_{1}$. हालाँकि, $S_{3}$ पर निर्भर नहीं है $S_{1}$ क्योंकि $S_{3}$ परिणाम की परवाह किए बिना हमेशा क्रियान्वित किया जाता है $S_{1}$.

एस1. अगर (ए == बी)
एस2. ए = ए + बी
एस3. बी = ए + बी

सहज रूप से, दो कथनों ए और बी के बीच नियंत्रण निर्भरता होती है

• बी को संभवतः ए के बाद निष्पादित किया जा सकता है
• ए की फांसी का नतीजा यह तय करेगा कि बी को फांसी दी जाएगी या नहीं।

एक विशिष्ट उदाहरण यह है कि किसी if कथन के स्थिति भाग और उसके सही/गलत निकायों में कथनों के बीच नियंत्रण निर्भरताएँ होती हैं।

नियंत्रण निर्भरता की औपचारिक परिभाषा इस प्रकार प्रस्तुत की जा सकती है:

एक बयान $S_{2}$ कहा जाता है कि नियंत्रण किसी अन्य कथन पर निर्भर होता है $S_{1}$ अगर और केवल अगर

• वहां एक रास्ता मौजूद है $P$ से $S_{1}$ को $S_{2}$ ऐसा कि हर बयान $S_{i}$ ≠ $S_{1}$ अंदर $P$ द्वारा पीछा किया जाएगा $S_{2}$ कार्यक्रम के अंत तक प्रत्येक संभावित पथ में और
• $S_{1}$ अनिवार्य रूप से इसका पालन नहीं किया जाएगा $S_{2}$, यानी से एक निष्पादन पथ है $S_{1}$ प्रोग्राम के अंत तक जो नहीं चलता है $S_{2}$.

(पोस्ट-)प्रभुत्व की सहायता से व्यक्त की गई दोनों स्थितियाँ समतुल्य हैं

• $S_{2}$ पद सब पर हावी है $S_{i}$
• $S_{2}$ पोस्ट-डोमिनेट नहीं होता है $S_{1}$

नियंत्रण निर्भरता का निर्माण

नियंत्रण निर्भरताएं अनिवार्य रूप से नियंत्रण-प्रवाह ग्राफ (सीएफजी) के रिवर्स ग्राफ में डोमिनेटर (ग्राफ सिद्धांत) हैं। इस प्रकार, उन्हें बनाने का एक तरीका, सीएफजी के पोस्ट-प्रभुत्व सीमा का निर्माण करना होगा, और फिर नियंत्रण निर्भरता ग्राफ प्राप्त करने के लिए इसे उलट देना होगा।

प्रभुत्व के बाद की सीमा के निर्माण के लिए निम्नलिखित एक छद्म कोड है:

पोस्ट-डोमिनेटर ट्री के बॉटम-अप ट्रैवर्सल में प्रत्येक एक्स के लिए:
    पोस्टडोमिनेंसफ्रंटियर(एक्स) ← ∅
    प्रत्येक Y ∈ पूर्ववर्ती(X) के लिए:
        यदि तत्कालपोस्टडोमिनेटर(वाई) ≠ एक्स:
            फिर पोस्टडोमिनेंसफ्रंटियर(एक्स) ← पोस्टडोमिनेंसफ्रंटियर(एक्स) ∪ {वाई}
    पूर्ण
    प्रत्येक Z ∈ बच्चों(X) के लिए यह करें:
        प्रत्येक Y ∈ PostDominanceFrontier(Z) के लिए करें:
            यदि तत्कालपोस्टडोमिनेटर(वाई) ≠ एक्स:
                फिर पोस्टडोमिनेंसफ्रंटियर(एक्स) ← पोस्टडोमिनेंसफ्रंटियर(एक्स) ∪ {वाई}
        पूर्ण
    पूर्ण
पूर्ण

यहां, चिल्ड्रन (एक्स) सीएफजी में नोड्स का सेट है जो एक्स द्वारा तुरंत पोस्ट-वर्चस्वित होता है, और पूर्ववर्ती (एक्स) सीएफजी में नोड्स का सेट है जो सीधे सीएफजी में एक्स से पहले होता है। ध्यान दें कि नोड X को उसके सभी चिल्ड्रेन के संसाधित होने के बाद ही संसाधित किया जाएगा। एक बार प्रभुत्व के बाद के सीमांत मानचित्र की गणना हो जाने के बाद, इसे उलटने से सीएफजी में नोड्स से लेकर उन नोड्स तक का मानचित्र तैयार हो जाएगा, जिन पर नियंत्रण निर्भरता है।

निहितार्थ

पारंपरिक कार्यक्रम अनुक्रमिक निष्पादन मॉडल को मानकर लिखे जाते हैं। इस मॉडल के तहत, निर्देश एक के बाद एक, परमाणु रूप से निष्पादित होते हैं (यानी, किसी भी समय, केवल एक निर्देश निष्पादित होता है) और प्रोग्राम द्वारा निर्दिष्ट क्रम में।

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