डेटा निर्भरता: Difference between revisions

From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में डेटा निर्भरता एक ऐसी स्थिति है जिसमें एक क...")
 
No edit summary
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में डेटा निर्भरता एक ऐसी स्थिति है जिसमें एक [[ कार्यक्रम वक्तव्य ]] (निर्देश) पिछले स्टेटमेंट के डेटा को संदर्भित करता है। [[संकलक सिद्धांत]] में, कथनों (या निर्देशों) के बीच डेटा निर्भरता की खोज करने के लिए उपयोग की जाने वाली तकनीक को [[निर्भरता विश्लेषण]] कहा जाता है।
कंप्यूटर विज्ञान में '''डेटा निर्भरता''' एक ऐसी स्थिति है जिसमें एक प्रोग्राम स्टेटमेंट (निर्देश) पिछले स्टेटमेंट के डेटा को संदर्भित करता है। संकलक सिद्धांत में, कथनों (या निर्देशों) के बीच डेटा निर्भरता की खोज करने के लिए उपयोग की जाने वाली तकनीक को निर्भरता विश्लेषण कहा जाता है।


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


अनुमान कथन <math>S_1</math> और <math>S_2</math>, <math>S_2</math> पर निर्भर करता है <math>S_1</math> अगर:
कथन <math>S_1</math> और <math>S_2</math> मानते हुए,<math>S_2</math> <math>S_1</math> पर निर्भर करता है यदि:


:<math>\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</math>
:<math>\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</math>
कहाँ:
जहाँ:


* <math>I(S_i)</math> द्वारा पढ़े गए स्मृति स्थानों का समूह है {{nobr|1=<math>S_i</math>,}}
* <math>I(S_i)</math> , {{nobr|1=<math>S_i</math>,}} द्वारा पढ़े गए स्मृति स्थानों का समूह है
* <math>O(S_j)</math> द्वारा लिखित स्मृति स्थानों का समूह है {{nobr|1=<math>S_j</math>,}} और
*<math>O(S_j)</math> {{nobr|1=<math>S_j</math>,}}द्वारा लिखित मेमोरी स्थानों का सेट है, और
* से एक व्यवहार्य रन-टाइम निष्पादन पथ है <math>S_1</math> को {{nobr|1=<math>S_2</math>.}}
*<math>S_1</math> को {{nobr|1=<math>S_2</math>.}} तक एक व्यवहार्य रन-टाइम निष्पादन पथ है।


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


तीन मामले मौजूद हैं:
तीन स्थिति उपस्थित हैं:


*विरोधी निर्भरता: <math>I(S_1) \cap O(S_2) \neq \varnothing</math>, <math>S_1 \rightarrow S_2</math> और <math>S_1</math> पहले कुछ पढ़ता है <math>S_2</math> इसे अधिलेखित कर देता है
*निर्भरता-विरोधी:<math>I(S_1) \cap O(S_2) \neq \varnothing</math> <math>S_1 \rightarrow S_2</math> और <math>S_1</math> <math>S_2</math> द्वारा इसे अधिलेखित करने से पहले कुछ पढ़ता है
* प्रवाह (डेटा) निर्भरता: <math>O(S_1) \cap I(S_2) \neq \varnothing</math>, <math>S_1 \rightarrow S_2</math> और <math>S_1</math> कुछ पढ़ने से पहले लिखता है <math>S_2</math>
*प्रवाह (डेटा) निर्भरता: <math>O(S_1) \cap I(S_2) \neq \varnothing</math><math>S_1 \rightarrow S_2</math>और <math>S_1</math> <math>S_2</math> से कुछ पढ़ने से पहले लिखते हैं।
* आउटपुट निर्भरता: <math>O(S_1) \cap O(S_2) \neq \varnothing</math>, <math>S_1 \rightarrow S_2</math> और दोनों एक ही मेमोरी लोकेशन लिखते हैं।
* आउटपुट निर्भरता: <math>O(S_1) \cap O(S_2) \neq \varnothing</math>, <math>S_1 \rightarrow S_2</math> और दोनों एक ही मेमोरी लोकेशन लिखते हैं।


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


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


  1. = 3
  1. A = 3
  2. बी =
  2. B = A
  3. सी = बी
  3. C = B


निर्देश 3 वास्तव में निर्देश 2 पर निर्भर है, क्योंकि C का अंतिम मान निर्देश अद्यतन करने वाले B पर निर्भर करता है। निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, क्योंकि B का अंतिम मान निर्देश अद्यतन करने वाले A पर निर्भर करता है। चूँकि निर्देश 3 वास्तव में निर्भर है निर्देश 2 पर और निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, निर्देश 3 भी वास्तव में निर्देश 1 पर निर्भर है। [[निर्देश स्तर समानता]] इसलिए इस उदाहरण में एक विकल्प नहीं है।
निर्देश 3 वास्तव में निर्देश 2 पर निर्भर है, क्योंकि C का अंतिम मान निर्देश अपडेट करने वाले B पर निर्भर करता है। निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, क्योंकि B का अंतिम मान निर्देश अपडेट करने वाले A पर निर्भर करता है। चूँकि निर्देश 3 वास्तव में निर्भर है निर्देश 2 पर और निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, निर्देश 3 भी वास्तव में निर्देश 1 पर निर्भर है। [[निर्देश स्तर समानता|इंस्ट्रक्शन  लेवल परललिस्म]] इसलिए इस उदाहरण में एक विकल्प नहीं है।<ref name="architecture">{{cite book | author=[[John L. Hennessy]]; [[David A. Patterson (scientist)|David A. Patterson]] | title=Computer Architecture: a quantitative approach (3rd ed.) | publisher=[[Morgan Kaufmann]] | year=2003 | isbn=1-55860-724-2}}</ref>
<ref name="architecture">{{cite book | author=[[John L. Hennessy]]; [[David A. Patterson (scientist)|David A. Patterson]] | title=Computer Architecture: a quantitative approach (3rd ed.) | publisher=[[Morgan Kaufmann]] | year=2003 | isbn=1-55860-724-2}}</ref>




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


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


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


उदाहरण :
उदाहरण :
   एमयूएल आर3,आर1,आर2
   MUL R3,R1,R2
   R2,R5,R6 जोड़ें
   ADD R2,R5,R6


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


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


  1. बी = 3
  1. B = 3
  एन. बी2 = बी
  N. B2 = B
  2. = बी2 + 1
  2. A = B2 + 1
  3. बी = 7
  3. B = 7


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




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


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


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


निर्भरता-विरोधी की तरह, आउटपुट निर्भरताएँ नाम निर्भरताएँ हैं। अर्थात्, उन्हें वेरिएबल्स का नाम बदलकर हटाया जा सकता है, जैसा कि उपरोक्त उदाहरण के नीचे दिए गए संशोधन में है:
एंटी डिपेंड़ेंसी की तरह, आउटपुट डिपेंड़ेंसी नाम निर्भरताएँ हैं। अर्थात्, उन्हें वेरिएबल्स का नाम बदलकर हटाया जा सकता है, जैसा कि उपरोक्त उदाहरण के नीचे दिए गए संशोधन में है:
 
1. बी2 = 3
2. ए = बी2 + 1
3. बी = 7
 
डेटा निर्भरता के लिए आमतौर पर इस्तेमाल की जाने वाली नामकरण परंपरा निम्नलिखित है: पढ़ने के बाद लिखने या RAW (प्रवाह निर्भरता), पढ़ने के बाद लिखने या WAR (विरोधी निर्भरता), या लिखने के बाद लिखने या WAW (आउटपुट निर्भरता)।
<ref name="architecture"/>


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


डेटा डिपेंड़ेंसी के लिए समान्यत: उपयोग की जाने वाली नामकरण परंपरा निम्नलिखित है: पढ़ने के बाद लिखने या आरएडब्ल्यू (प्रवाह निर्भरता), पढ़ने के बाद लिखने या डब्ल्यूएआर (एंटी डिपेंड़ेंसी), या लिखने के बाद लिखने या डब्ल्यूएडब्ल्यू (आउटपुट निर्भरता)।<ref name="architecture"/>
==नियंत्रण निर्भरता==
==नियंत्रण निर्भरता==
एक निर्देश बी की पूर्ववर्ती निर्देश पर नियंत्रण निर्भरता होती है यदि का परिणाम यह निर्धारित करता है कि बी को निष्पादित किया जाना चाहिए या नहीं। निम्नलिखित उदाहरण में, निर्देश <math>S_2</math> निर्देश पर नियंत्रण निर्भरता है <math>S_1</math>. हालाँकि, <math>S_3</math> पर निर्भर नहीं है <math>S_1</math> क्योंकि <math>S_3</math> परिणाम की परवाह किए बिना हमेशा क्रियान्वित किया जाता है <math>S_1</math>.
एक निर्देश B की पूर्ववर्ती निर्देश A पर नियंत्रण निर्भरता होती है यदि A का परिणाम यह निर्धारित करता है कि B को निष्पादित किया जाना चाहिए या नहीं। निम्नलिखित उदाहरण में, निर्देश <math>S_2</math> की निर्देश <math>S_1</math> पर नियंत्रण निर्भरता है। चूँकि , <math>S_3</math> <math>S_1</math> पर निर्भर नहीं है क्योंकि <math>S_3</math> को सदैव  <math>S_1</math> के परिणाम की परवाह किए बिना निष्पादित किया जाता है।


  एस1. अगर (== बी)
  S1.         if (a == b)
  एस2. = + बी
  S2.             a = a + b
  एस3. बी = + बी
  S3.         b = a + b


सहज रूप से, दो कथनों और बी के बीच नियंत्रण निर्भरता होती है
सहज रूप से, दो कथनों A और B के बीच नियंत्रण निर्भरता होती है
* बी को संभवतः के बाद निष्पादित किया जा सकता है
* B को संभवतः A के बाद निष्पादित किया जा सकता है
*की फांसी का नतीजा यह तय करेगा कि बी को फांसी दी जाएगी या नहीं।
*A की निष्पादन का परिणाम यह तय करेगा कि B को निष्पादन दी जाएगी या नहीं।


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


एक बयान <math>S_2</math> कहा जाता है कि नियंत्रण किसी अन्य कथन पर निर्भर होता है <math>S_1</math> [[अगर और केवल अगर]]
एक कथन <math>S_2</math> को दूसरे कथन <math>S_1</math> पर नियंत्रण निर्भर कहा जाता है।
*वहां एक रास्ता मौजूद है <math>P</math> से <math>S_1</math> को <math>S_2</math> ऐसा कि हर बयान <math>S_i</math> ≠ <math>S_1</math> अंदर <math>P</math> द्वारा पीछा किया जाएगा <math>S_2</math> कार्यक्रम के अंत तक प्रत्येक संभावित पथ में और
*<math>S_1</math> को <math>S_2</math> तक एक पथ P उपस्थित है, जिससे कि P के अंदर प्रत्येक कथन <math>S_i                                                                                                                                                                  
* <math>S_1</math> अनिवार्य रूप से इसका पालन नहीं किया जाएगा <math>S_2</math>, यानी से एक निष्पादन पथ है <math>S_1</math> प्रोग्राम के अंत तक जो नहीं चलता है <math>S_2</math>.
                                                                                                                                                                                                           
                                                          </math> ≠ <math>S_1</math> का अनुसरण कार्यक्रम के अंत तक प्रत्येक संभावित पथ में <math>S_2</math> द्वारा किया जाएगा और
*<math>S_1</math> के बाद आवश्यक रूप से <math>S_2</math> नहीं होगा, अथार्त <math>S_1</math> से प्रोग्राम के अंत तक एक निष्पादन पथ है जो <math>S_2</math> से नहीं जाता है।


(पोस्ट-)प्रभुत्व की सहायता से व्यक्त की गई दोनों स्थितियाँ समतुल्य हैं
(पोस्ट-)प्रभुत्व की सहायता से व्यक्त की गई दोनों स्थितियाँ समतुल्य हैं
* <math>S_2</math> पद सब पर हावी है <math>S_i</math>
*<math>S_2</math> सभी <math>S_i</math> पर पोस्ट-डोमिनेट करता है।
* <math>S_2</math> पोस्ट-डोमिनेट नहीं होता है <math>S_1</math>
* <math>S_2</math> <math>S_1</math> पोस्ट-डोमिनेट नहीं होता है




=== नियंत्रण निर्भरता का निर्माण ===
=== नियंत्रण निर्भरता का निर्माण ===
नियंत्रण निर्भरताएं अनिवार्य रूप से [[नियंत्रण-प्रवाह ग्राफ]] (सीएफजी) के रिवर्स ग्राफ में [[डोमिनेटर (ग्राफ सिद्धांत)]] हैं।<ref>{{Cite journal|title = स्टेटिक सिंगल असाइनमेंट फॉर्म की गणना करने की एक कुशल विधि|publisher = ACM|journal = Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|date = 1989-01-01|location = New York, NY, USA|isbn = 0897912942|pages = 25–35|series = POPL '89|doi = 10.1145/75277.75280|first1 = R.|last1 = Cytron|first2 = J.|last2 = Ferrante|first3 = B. K.|last3 = Rosen|first4 = M. N.|last4 = Wegman|first5 = F. K.|last5 = Zadeck| s2cid=8301431 }}</ref> इस प्रकार, उन्हें बनाने का एक तरीका, सीएफजी के पोस्ट-प्रभुत्व सीमा का निर्माण करना होगा, और फिर नियंत्रण निर्भरता ग्राफ प्राप्त करने के लिए इसे उलट देना होगा।
नियंत्रण निर्भरताएं अनिवार्य रूप से [[नियंत्रण-प्रवाह ग्राफ|कंट्रोल-फ्लो ग्राफ]] (सीएफजी) के रिवर्स ग्राफ में [[डोमिनेटर (ग्राफ सिद्धांत)]] हैं।<ref>{{Cite journal|title = स्टेटिक सिंगल असाइनमेंट फॉर्म की गणना करने की एक कुशल विधि|publisher = ACM|journal = Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|date = 1989-01-01|location = New York, NY, USA|isbn = 0897912942|pages = 25–35|series = POPL '89|doi = 10.1145/75277.75280|first1 = R.|last1 = Cytron|first2 = J.|last2 = Ferrante|first3 = B. K.|last3 = Rosen|first4 = M. N.|last4 = Wegman|first5 = F. K.|last5 = Zadeck| s2cid=8301431 }}</ref> इस प्रकार, उन्हें बनाने का एक विधि, सीएफजी के पोस्ट-प्रभुत्व सीमा का निर्माण करना होगा, और फिर नियंत्रण निर्भरता ग्राफ प्राप्त करने के लिए इसे विपरीत कर देना होगा।


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


  पोस्ट-डोमिनेटर ट्री के बॉटम-अप ट्रैवर्सल में प्रत्येक एक्स के लिए:
  for each X in a bottom-up traversal of the post-dominator tree do:
     पोस्टडोमिनेंसफ्रंटियर(एक्स) ← ∅
     PostDominanceFrontier(X) ← ∅
     प्रत्येक Y ∈ पूर्ववर्ती(X) के लिए:
     for each Y ∈ Predecessors(X) do:
         यदि तत्कालपोस्टडोमिनेटर(वाई) ≠ एक्स:
         if immediatePostDominator(Y) ≠ X:
             फिर पोस्टडोमिनेंसफ्रंटियर(एक्स) ← पोस्टडोमिनेंसफ्रंटियर(एक्स) ∪ {वाई}
             then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
     पूर्ण
     done
     प्रत्येक Z ∈ बच्चों(X) के लिए यह करें:
     for each Z ∈ Children(X) do:
         प्रत्येक Y ∈ PostDominanceFrontier(Z) के लिए करें:
         for each Y ∈ PostDominanceFrontier(Z) do:
             यदि तत्कालपोस्टडोमिनेटर(वाई) ≠ एक्स:
             if immediatePostDominator(Y) ≠ X:
                 फिर पोस्टडोमिनेंसफ्रंटियर(एक्स) ← पोस्टडोमिनेंसफ्रंटियर(एक्स) ∪ {वाई}
                 then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
         पूर्ण
         done
     पूर्ण
     done
  पूर्ण
  done


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


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


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


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
[[Category: संकलनकर्ता]] [[Category: समानांतर एल्गोरिदम का विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category:CS1 maint]]
[[Category:Created On 09/07/2023]]
[[Category:Created On 09/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:संकलनकर्ता]]
[[Category:समानांतर एल्गोरिदम का विश्लेषण]]

Latest revision as of 16:45, 4 September 2023

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

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

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

कथन और मानते हुए, पर निर्भर करता है यदि:

जहाँ:

  • , , द्वारा पढ़े गए स्मृति स्थानों का समूह है
  • ,द्वारा लिखित मेमोरी स्थानों का सेट है, और
  • को . तक एक व्यवहार्य रन-टाइम निष्पादन पथ है।

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

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

  • निर्भरता-विरोधी: और द्वारा इसे अधिलेखित करने से पहले कुछ पढ़ता है
  • प्रवाह (डेटा) निर्भरता: और से कुछ पढ़ने से पहले लिखते हैं।
  • आउटपुट निर्भरता: , और दोनों एक ही मेमोरी लोकेशन लिखते हैं।

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

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

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

निर्देश 3 वास्तव में निर्देश 2 पर निर्भर है, क्योंकि C का अंतिम मान निर्देश अपडेट करने वाले B पर निर्भर करता है। निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, क्योंकि B का अंतिम मान निर्देश अपडेट करने वाले A पर निर्भर करता है। चूँकि निर्देश 3 वास्तव में निर्भर है निर्देश 2 पर और निर्देश 2 वास्तव में निर्देश 1 पर निर्भर है, निर्देश 3 भी वास्तव में निर्देश 1 पर निर्भर है। इंस्ट्रक्शन लेवल परललिस्म इसलिए इस उदाहरण में एक विकल्प नहीं है।[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 पर निर्भर है। प्रवाह निर्भरता के रूप में, इन नई निर्भरताओं को सुरक्षित रूप से हटाना असंभव है।[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

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

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

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

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

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

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

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

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

एक कथन को दूसरे कथन पर नियंत्रण निर्भर कहा जाता है।

  • को तक एक पथ P उपस्थित है, जिससे कि P के अंदर प्रत्येक कथन का अनुसरण कार्यक्रम के अंत तक प्रत्येक संभावित पथ में द्वारा किया जाएगा और
  • के बाद आवश्यक रूप से नहीं होगा, अथार्त से प्रोग्राम के अंत तक एक निष्पादन पथ है जो से नहीं जाता है।

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

  • सभी पर पोस्ट-डोमिनेट करता है।
  • पोस्ट-डोमिनेट नहीं होता है


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

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

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

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 को उसके सभी चिल्ड्रेन के संसाधित होने के बाद ही संसाधित किया जाएगा। एक बार प्रभुत्व के बाद के सीमांत मानचित्र की गणना हो जाने के बाद, इसे विपरीत से सीएफजी में नोड्स से लेकर उन नोड्स तक का मानचित्र तैयार हो जाएगा, जिन पर नियंत्रण निर्भरता है।

निहितार्थ

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

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

संदर्भ

  1. 1.0 1.1 1.2 John L. Hennessy; David A. Patterson (2003). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann. ISBN 1-55860-724-2.{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. Cytron, R.; Ferrante, J.; Rosen, B. K.; Wegman, M. N.; Zadeck, F. K. (1989-01-01). "स्टेटिक सिंगल असाइनमेंट फॉर्म की गणना करने की एक कुशल विधि". Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL '89. New York, NY, USA: ACM: 25–35. doi:10.1145/75277.75280. ISBN 0897912942. S2CID 8301431.