تبعية البيانات

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

في علوم الحاسوب، يُعرف التبعية البياناتية بأنها حالة يشير فيها بيان البرنامج (التعليمات) إلى بيانات بيان سابق. وفي نظرية المترجمات ، تُسمى التقنية المستخدمة لاكتشاف التبعيات البياناتية بين البيانات (أو التعليمات) بتحليل التبعية .

وصف

بافتراض البيانS1{\displaystyle S_{1}}وS2{\displaystyle S_{2}}،S2{\displaystyle S_{2}}يعتمد علىS1{\displaystyle S_{1}}لو:

[أنا(S1)∩يا(S2)]∪[يا(S1)∩أنا(S2)]∪[يا(S1)∩يا(S2)]≠∅{\displaystyle \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 }

أين:

  • أنا(Sأنا){\displaystyle I(S_{i})}هي مجموعة مواقع الذاكرة التي يقرأهاSأنا{\displaystyle S_{i}}،
  • يا(Sج){\displaystyle O(S_{j})}هي مجموعة مواقع الذاكرة التي يكتبهاSج{\displaystyle S_{j}}، و
  • يوجد مسار تنفيذ ممكن أثناء التشغيل منS1{\displaystyle S_{1}}لS2{\displaystyle S_{2}}.

تُسمى هذه الحالات بحالات برنشتاين، نسبة إلى آرثر ج. برنشتاين. [ 1 ]

توجد ثلاث حالات:

  • مكافحة الإدمان:أنا(S1)∩يا(S2)≠∅{\displaystyle I(S_{1})\cap O(S_{2})\neq \varnothing }،S1→S2{\displaystyle S_{1}\rightarrow S_{2}}وS1{\displaystyle S_{1}}يقرأ شيئًا ما قبلS2{\displaystyle S_{2}}يستبدلها
  • الاعتماد على التدفق (البيانات):يا(S1)∩أنا(S2)≠∅{\displaystyle O(S_{1})\cap I(S_{2})\neq \varnothing }،S1→S2{\displaystyle S_{1}\rightarrow S_{2}}وS1{\displaystyle S_{1}}يكتب قبل أن يقرأ شيء ماS2{\displaystyle S_{2}}
  • الاعتماد على المخرجات:يا(S1)∩يا(S2)≠∅{\displaystyle O(S_{1})\cap O(S_{2})\neq \varnothing }،S1→S2{\displaystyle S_{1}\rightarrow S_{2}}وكلاهما يكتب في نفس موقع الذاكرة.

الأنواع

مخاطر البيانات

تحدث مخاطر البيانات عندما تُعدّل التعليمات التي تعتمد على البيانات البيانات في مراحل مختلفة من مسار المعالجة. قد يؤدي تجاهل مخاطر البيانات المحتملة إلى حدوث تضارب في البيانات (يُسمى أيضًا مخاطر التزامن). هناك ثلاث حالات يمكن أن تحدث فيها مخاطر البيانات:

  1. القراءة بعد الكتابة (RAW)، تبعية حقيقية
  2. الكتابة بعد القراءة (WAR)، وهي تقنية مضادة للاعتمادية
  3. الكتابة بعد الكتابة (WAW)، وهي تبعية إخراج
  4. القراءة تلو القراءة (RAR)، تبعية زائفة

لا تُعتبر عملية القراءة المتكررة (RAR) حالة خطرة.

لنفترض وجود تعليمتين i1 و i2 ، حيث تحدث i1 قبل i2 في ترتيب البرنامج.

القراءة بعد الكتابة (RAW)

( تحاول i2 قراءة المصدر قبل أن تكتب i1 إليه) يُشير خطر قراءة البيانات بعد كتابتها (RAW) إلى حالة تُشير فيها تعليمة إلى نتيجة لم تُحسب أو تُسترجع بعد. قد يحدث هذا لأنه على الرغم من تنفيذ تعليمة ما بعد تعليمة سابقة، إلا أن التعليمة السابقة لم تُعالج إلا جزئيًا عبر خط الأنابيب.

مثال

على سبيل المثال:

i1. R2 <- R5 + R8 i2. R4 <- R2 + R8

تقوم التعليمات الأولى بحساب قيمة لحفظها في المسجل R2 ، بينما تستخدم التعليمات الثانية هذه القيمة لحساب نتيجة للمسجل R4 . مع ذلك، في سلسلة العمليات ، عند جلب المعاملات للعملية الثانية، لم تُحفظ نتائج العملية الأولى بعد، مما يُسبب تبعية في البيانات.

يحدث اعتماد البيانات مع التعليمات i2 ، لأنها تعتمد على إكمال التعليمات i1 .

اكتب بعد القراءة (WAR)

( يحاول i2 كتابة وجهة قبل أن يقرأها i1 ) يمثل خطر الكتابة بعد القراءة (WAR) مشكلة في التنفيذ المتزامن.

مثال

على سبيل المثال:

i1. R4 <- R1 + R5 i2. R5 <- R1 + R2

في أي حالة يكون فيها احتمال أن ينتهي i2 قبل i1 (أي مع التنفيذ المتزامن)، يجب التأكد من عدم تخزين نتيجة السجل R5 قبل أن تتاح لـ i1 فرصة جلب المعاملات.

اكتب بعد كتابة (WAW)

( يحاول i2 كتابة معامل قبل أن يكتبه i1 ) قد يحدث خطر كتابة البيانات بعد الكتابة (WAW) في بيئة التنفيذ المتزامن .

مثال

على سبيل المثال:

i1. R5 <- R4 + R7 i2. R5 <- R1 + R3

يجب تأخير عملية الكتابة (WB) الخاصة بـ i2 حتى ينتهي i1 من التنفيذ.

التبعية الحقيقية (القراءة بعد الكتابة)

يحدث التبعية الحقيقية، والمعروفة أيضًا بتبعية التدفق أو تبعية البيانات ، عندما تعتمد تعليمة ما على نتيجة تعليمة سابقة. ويؤدي انتهاك التبعية الحقيقية إلى خطر القراءة بعد الكتابة (RAW) .

1. أ = 3 2. ب = أ 3. ج = ب

تعتمد التعليمات 3 اعتمادًا كليًا على التعليمات 2، حيث تعتمد القيمة النهائية لـ C على التعليمات التي تُحدِّث B. وتعتمد التعليمات 2 اعتمادًا كليًا على التعليمات 1، حيث تعتمد القيمة النهائية لـ B على التعليمات التي تُحدِّث A. وبما أن التعليمات 3 تعتمد اعتمادًا كليًا على التعليمات 2، والتعليمات 2 تعتمد اعتمادًا كليًا على التعليمات 1، فإن التعليمات 3 تعتمد أيضًا اعتمادًا كليًا على التعليمات 1. لذا، فإن التوازي على مستوى التعليمات غير ممكن في هذا المثال. [ 2 ]

مقاومة التبعية (الكتابة بعد القراءة)

يحدث التبعية المضادة عندما تتطلب تعليمة ما قيمة يتم تحديثها لاحقًا. ويؤدي انتهاك التبعية المضادة إلى خطر الكتابة بعد القراءة (WAR) .

في المثال التالي، تعتمد التعليمات 2 عكسيًا على التعليمات 3 - لا يمكن تغيير ترتيب هذه التعليمات، ولا يمكن تنفيذها بالتوازي (مما قد يؤدي إلى تغيير ترتيب التعليمات)، لأن هذا سيؤثر على القيمة النهائية لـ A.

1. ب = 3 2. أ = ب + 1 3. ب = 7

مثال:

MUL R3، R1، R2 أضف R2، R5، R6

من الواضح وجود ترابط عكسي بين هاتين التعليمات. في البداية نقرأ قيمة R2، ثم في التعليمات الثانية نكتب قيمة جديدة لها.

يُعدّ التبعية المضادة مثالاً على تبعية الاسم . أي أن إعادة تسمية المتغيرات قد تزيل التبعية، كما في المثال التالي:

1. ب = 3 N. B2 = B 2. أ = ب² + 1 3. ب = 7

A new variable, B2, has been declared as a copy of B in a new instruction, instruction N. The anti-dependency between 2 and 3 has been removed, meaning that these instructions may now be executed in parallel.

لاحظ أنه لا يزال هناك اعتماد على القراءة بعد الكتابة: فالتعليمات 2 تعتمد فعليًا على التعليمات N، والتي بدورها تعتمد فعليًا على التعليمات 1. كان هذا الاعتماد موجودًا في الإصدار الأصلي، حيث كانت التعليمات 2 تعتمد فعليًا على التعليمات 1. لا يمكن إزالة هذا الاعتماد بأمان. [ 2 ]

تبعية الإخراج (الكتابة بعد الكتابة)

يحدث التبعية في المخرجات عندما يؤثر ترتيب التعليمات على القيمة النهائية لمتغير ما. ويؤدي انتهاك هذه التبعية إلى خطر الكتابة المتتالية (WAW) .

في المثال أدناه، هناك تبعية إخراج بين التعليمات 3 و 1 - سيؤدي تغيير ترتيب التعليمات في هذا المثال إلى تغيير القيمة النهائية لـ A، وبالتالي لا يمكن تنفيذ هذه التعليمات بالتوازي.

1. ب = 3 2. أ = ب + 1 3. ب = 7

كما هو الحال مع التبعيات المضادة، فإن تبعيات المخرجات هي تبعيات اسمية . أي أنه يمكن إزالتها من خلال إعادة تسمية المتغيرات، كما في التعديل التالي للمثال أعلاه:

1. B2 = 3 2. أ = ب² + 1 3. ب = 7

تداعيات

تُكتب البرامج التقليدية بافتراض نموذج التنفيذ التسلسلي . وبموجب هذا النموذج، تُنفذ التعليمات واحدة تلو الأخرى، بشكل ذري (أي أنه في أي لحظة معينة، يتم تنفيذ تعليمة واحدة فقط) وبالترتيب الذي يحدده البرنامج.

مع ذلك، قد تعيق التبعيات بين العبارات أو التعليمات التوازي - أي التنفيذ المتوازي لعدة تعليمات، سواءً بواسطة مُترجم مُوازٍ أو بواسطة مُعالج يستغل التوازي على مستوى التعليمات . إن تنفيذ عدة تعليمات بشكل عشوائي دون مراعاة التبعيات ذات الصلة قد يُؤدي إلى خطر الحصول على نتائج خاطئة، أي مخاطر .

الأهمية في مجال الحوسبة

تعتبر تبعيات البيانات ذات صلة في مجالات مختلفة من الحوسبة، لا سيما في تصميم المعالجات ، وبناء المترجمات، والحوسبة المتوازية ، والبرمجة المتزامنة.

تصميم المعالج

بناء المترجم

تُعدّ تبعيات البيانات ذات أهمية للعديد من تحسينات المُصرّف ، على سبيل المثال

  • جدولة التعليمات : يجب على المترجمات جدولة التعليمات بطريقة تراعي تبعيات البيانات. وهذا أمر بالغ الأهمية في تحسين أداء المترجمات التي تعيد ترتيب التعليمات البرمجية لتحسين الأداء.
  • تحويلات الحلقات : عند تحسين الحلقات، تحتاج المترجمات إلى مراعاة تبعيات البيانات لتطبيق تحويلات مثل فك الحلقات أو دمجها أو تبليطها دون تغيير دلالات البرنامج.
  • نقل التعليمات البرمجية : عندما يفكر المترجم في نقل جزء من التعليمات البرمجية، يجب عليه التأكد من عدم انتهاك تبعيات البيانات.

انظر أيضاً

مراجع

  1. ↑ بيرنشتاين، آرثر ج. (1 أكتوبر 1966). "تحليل برامج المعالجة المتوازية". معاملات IEEE في الحواسيب الإلكترونية . EC-15 (5): 757–763 . doi : 10.1109/PGEC.1966.264565 .
  2. 1 2 جون ل. هينيسي ؛ ديفيد أ. باترسون (2003). هندسة الحاسوب: منهج كمي (الطبعة الثالثة) . مورغان كوفمان . ISBN 1-55860-724-2.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )