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

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

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

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

कथन $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}$. तक एक व्यवहार्य रन-टाइम निष्पादन पथ है।

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

तीन स्थिति उपस्थित हैं:

• निर्भरता-विरोधी:$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}$ और दोनों एक ही मेमोरी लोकेशन लिखते हैं।

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

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

1. A = 3
2. B = A
3. C = B

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

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

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

1. B = 3
2. A = B + 1
3. B = 7

उदाहरण :

 MUL R3,R1,R2
 ADD R2,R5,R6

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

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

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

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

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

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

1. B = 3
2. A = B + 1
3. B = 7

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

1. B2 = 3
2. A = B2 + 1
3. B = 7

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

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

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

S1.         if (a == b)
S2.             a = a + b
S3.         b = a + b

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

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

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

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

एक कथन $S_{2}$ को दूसरे कथन $S_{1}$ पर नियंत्रण निर्भर कहा जाता है।

• $S_{1}$ को $S_{2}$ तक एक पथ P उपस्थित है, जिससे कि P के अंदर प्रत्येक कथन $S_{i}$ ≠