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

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

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

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

कथन $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}$ ≠ $S_{1}$ का अनुसरण कार्यक्रम के अंत तक प्रत्येक संभावित पथ में $S_{2}$ द्वारा किया जाएगा और
• $S_{1}$ के बाद आवश्यक रूप से $S_{2}$ नहीं होगा, अथार्त $S_{1}$ से प्रोग्राम के अंत तक एक निष्पादन पथ है जो $S_{2}$ से नहीं जाता है।

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

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

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

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

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

for each X in a bottom-up traversal of the post-dominator tree do:
    PostDominanceFrontier(X) ← ∅
    for each Y ∈ Predecessors(X) do:
        if immediatePostDominator(Y) ≠ X:
            then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
    done
    for each Z ∈ Children(X) do:
        for each Y ∈ PostDominanceFrontier(Z) do:
            if immediatePostDominator(Y) ≠ X:
                then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
        done
    done
done

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

निहितार्थ

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

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