بروتوكولات اتساق الخابيات

بروتوكولات اتساق خابيات

Cache coherence protocols -

بروتوكولات اتساق الخابيات

محمّد نوّار العوّا

أنواع البروتوكولات

المقاربات الهجينة

يسهم توفر الخابيات caches في البنى المتوازية ذات المعالِجات المتعددة والذاكرة المشتركة في رفع أداء البنى بتقليص الزمن اللازم لأي معالج للنفاذ إلى الذاكرة، وبإنقاص متطلبات عرض الحزمة على مستوى الذاكرة المحلية والتوصيل البيني في تلك البنى. ولكن تسبِّب تخبئة المعلومات محلّياً إلى مشكلة في الاتساق، أي التوثّق من أن جميع المعالجات تتعامل مع القيم ذاتها للمعطيات المخبّأة محلياً؛ لضمان تنفيذ البرنامج تنفيذاً صحيحاً. يمكن حلّ هذه المشكلة في المعالجات عتادياً بتنجيز آليات محدّدة تسمى بروتوكولات اتساق الخابيات cache coherence protocols. يبيّن الشكل (1) مثالاً على بنية متوازية تعاني مشكلة اتساق الخابيات. فللمتحوِّل x قيم مختلفة في هذه الخابيات، وهي قد تكون مختلفة عن القيمة المخزّنة في الذاكرة المشتركة.

الشكل (1) بنية متوازية تعاني عدم اتساق الخابيات.

لما كانت كل ذاكرة خابية تتألف من عدد من الأسطر cache lines، فإن بروتوكولات الاتساق تتفعّل عند كتابة أي سطر منها.

يمكن إذن لأكثر من خابية واحدة في البنية احتواء نسخة من المتحول نفسه في الذاكرة الرئيسية. ومن الضروري التوثّق من أن جميع المعالجات تستخدم نسخة محدّثة من هذه المعطيات. فإذا كان المتحول x متوفراً في الخابيتين Ci وCj، وطلب المعالج Pi تغيير قيمة x، تصبح قيمة المتحوّل x في الخابية Cj غير متسقة. وإذا كانت الخابيات تتيح نمط الكتابة خلفاً write-back - أي تسمح بالكتابة في الخابية فقط من دون الذاكرة الرئيسية- تصبح قيمة المتحول x مختلفة عن القيمة المخزّنة في الذاكرة الرئيسية أيضاً.

يجري تنجيز تقنيات الاتساق في البنى المتوازية على مستوى البرمجيات الراسخة firmware، ويمكن استخدام إحدى التقنيتين:

- البُطلان invalidation: ويُفترض فيها أن النسخة الوحيدة الصالحة لكتلة المعطيات هي النسخة الأخيرة التي جرى تعديلها، وينبغي إذن إبطال صلاحية النسخ الأخرى في بقية الخابيات.

- التحديث update: يجري فيها إرسال أي تحديث لكتلة المعطيات إلى بقية الخابيات التي تحدّث بدورها السطر المقابل لهذه الكتلة.

وفي المثال السابق عند قيام المعالج Pi بالكتابة في المتحول x، وباستخدام تقنية البُطلان؛ تصير النسخة المتوافرة في الخابية Cj غير صالحة. أما باستخدام تقنية التحديث يجري بثّ التعديلات إلى المعالجات كافة، ومن ثمّ تغدو النسخة في الخابية Cj صالحة ومحدَّثة.

تعاني طريقة التحديث حاجتها إلى حركة أعلى على شبكة توصيل المعالجات، ومن ثمّ إلى عرض حزمة أعلى. ولذا تتجه معظم البنى المتوازية إلى اعتماد تقنية البُطلان.

أنواع البروتوكولات

لتنفيذ هذه البروتوكولات يُرفق بكل كتلة معطيات حالة محدّدة، تدلّ على مستوى صلاحيتها. ويمكن التمييز بين نوعين أساسيّين: بروتوكولات التنصّت snooping، وبروتوكولات الدليل directory.

أ- بروتوكولات التنصّت

تعتمد هذه البروتوكولات على مبدأ بثّ broadcasting طلب الاتساق إلى العقد (المعالجات) كافة. ولعلّ المقاربة الأكثر انتشاراً هي التنصّت على المسرى. في هذه الحالة يربط مسرى جميع المعالجات، بحيث تستطيع استلام الرسالة. ويحقق المسرى مبدأ الذرية atomicity؛ فالرسالة تظهر على المسرى في لحظة معينة، وتلتقطها جميع العقد معاً. وتنجِّز متحكمات الخابية - في كل عقدة- آلات منتهية الحالات (FSM) Finite State Machines للحفاظ على اتساق المتحولات فيها. ومن أهم البروتوكولات:

- البروتوكول (MSI) Modified-Shared-Invalid: وهو بروتوكول يعتمد على تقنية البُطلان، ويُستخدم في حالة اتباع الخابيات طريقة الكتابة خلفاً. يستخدم البروتوكول ثلاث حالات مختلفة للتمييز بين الكتل الصالحة للاستخدام، وهي:

• حالة معدَّلة (M) Modified: وتسمى أيضاً حالة متسخة dirty. وهي تشير إلى أن هذه الخابية تحوي نسخة صالحة من كتلة المعطيات، وأن هذه النسخة مختلفة عن قيمتها في الذاكرة الرئيسية.
• حالة مشتركة (S) shared: وتشير إلى أن سطر الخابية المعني مطابق لكتلة المعطيات في الذاكرة الرئيسية، وأنه قد تتوفر مثل هذه النسخة لدى خابيات أخرى في البنية.
• حالة غير صالحة (I) invalid: وتدل على أن سطر الخابية المعني غير صالح للاستخدام.

  يبيّن الشكل 2 مخطط حالات هذا البروتوكول.

  الشكل (2) مخطط حالات البروتوكول MSI.

  يحوي هذا المخطط نوعين من الخطوط: الخطوط المتصلة التي تشير إلى انتقال يحدث بسبب طلب من المعالج المدروس (طلب قراءة أو كتابة)، والخطوط المتقطعة التي تشير إلى انتقال يحدث بسبب طلب من الخابيات الأخرى الواقعة خارج المعالج المدروس. ومثال ذلك إذا طلب معالجٌ الكتابةَ في كتلة غير صالحة (أي بالحالة I)؛ فهذا يؤدي إلى ظهور طلب كتابة على المسرى. يجري عندئذٍ تحميل الكتلة المحدَّثة في الخابية، وتكون حالتها «معدّلة M». أما في بقية الخابيات فتصبح حالة هذه الكتلة «غير صالحة I» لمنع المعالج من استخدامها بعد أن تغيّرت قيمتها في المعالج المدروس.

  ومثال آخر إذا أعلم معالج ما Pj بطلب قراءة كتلة يجري في معالج آخر Pi، وكانت حالتها في خابية المعالج Pj «معدَّلة M»؛ فإنه يسرع بإفراغ قيمتها في الذاكرة الرئيسية، ويعدِّل حالتها لتصبح «مشتركة S»، نظراً لحصول المعالج Pi لاحقاً على نسخة منها عن طريق الذاكرة الرئيسية.

  - البروتوكول Modified -Exclusive -Shared- Invalid  (MESI): يُعرف هذا البروتوكول أيضاً باسم البروتوكول «إيلينويز Illinois» حيث طُوّر للمرة الأولى في تلك الجامعة. وهو بروتوكول واسع الانتشار، يُستخدم عند اتباع الخابيات طريقة الكتابة خلفاً. يستدرك هذا البروتوكول مثالب البروتوكول MSI التي تظهر عند رغبة معالج ما بقراءة أو تعديل عنصر معطيات، والتي تتطلب إجراء انتقالين متتاليين. كما يضيف البروتوكول MESI حالة جديدة، وهي الحالة «الحصرية E»، لتقليص حركة المعطيات على المسرى. يبيّن الشكل (3) مخطط حالات هذا البروتوكول.

  الشكل(3) مخطط الحالات للبروتوكول MESI.

  ومثال ذلك إذا قام المعالج Pi بكتابة كلمة حالتها «حصرية» E في خابيته؛ فيمكن أن تنتقل حالتها إلى الحالة المعدّلة M مباشرةً، من دون أن يولِّد ذلك أي طلب على المسرى. وعند كتابة كتلة في خابية المعالج Pj حالتها مشتركة S يعدِّل المعالج Pi حالتها لديه لتصبح غير صالحة I.

  ومع تطوّر المعالجات وزيادة الحاجة إلى رفع أداء الحواسيب، أصبحت الخابيات المتعددة المستويات multi-level caches شائعة الاستخدام. ويُعدّ اتساق الخابيات في مثل هذه الحالة أكثر تعقيداً لأن التغيّرات التي يقوم بها المعالج في خابية المستوى الأول L1 لن تكون مرئية لمتحكّم الخابيات، كما أن عمليات
  القراءة/الكتابة التي تجري على المسرى لن تكون مرئية مباشرةً لخابيات المستوى الأول L1.

  يمكن حلّ مثل هذه الحالات بتوفير متحكِّم خابيات خاص بكل مستوى، ولكن ذلك يؤدي إلى زيادة تعقيد البنى، ورفع كلفتها. ولذا يُستعاض عن ذلك بحلٍّ يستثمر ميزة الاحتواء inclusion في هذه الخابيات، والتي تنص على ما يلي:

• إذا توفّرت كتلة ذاكرة في المستوى L1، ينبغي أن تتوفر أيضاً في المستوى L2؛ أي إن محتويات الخابية L1 هي مجموعة جزئية من محتويات الخابية L2.
• إذا كانت حالة الكتلة في الخابية L1 معدَّلة؛ ينبغي أن يكون لها الحالة نفسها في الخابية L2، وعندئذٍ يكفي توفر متحكم واحد على المستوى L2.

  يجري الحفاظ على ميزة الاحتواء عند تطبيق سياسة الاستعاضة replacement في الخابية L2؛ فعند الاستعاضة عن كتلة معينة في المستوى L2 يُرسل عنوانها إلى المستوى L1 لإبطال صلاحيتها أو إفراغها. وإذا جرى إبطال صلاحية كتلة في المستوى L2، ينبغي نقل الإبطال إلى المستوى L1 أيضاً. ويمكن تحقيق ذلك بإضافة بت إلى الخابية L2 يسمى بت الاحتواء، للإشارة إلى توفر نسخة من الكتلة في المستوى L1.

  وبالمماثلة عند كتابة قيمة على المستوى L1، ينبغي نقل التعديلات إلى المستوى L2. ويمكن إجراء ذلك باتباع طريقة الكتابة في أثناء التعديل write through في المستوى L1. ويمكن أيضاً توسيع الحالات الممكنة لكتلة المعطيات في المستوى L2 بإضافة حالة جديدة وهي «معدَّلة ولكن قديمة modified but stale». وتُجلَب عندئذٍ الكتلة المحدَّثة من المستوى L1 عند الحاجة إليها في المستوى L2.

  ب- بروتوكولات الدليل

  في النظم المتوازية المعقّدة تُستخدم بنى للتوصيل تسمح بالتصعّدية scalability وبزيادة الأداء بحسب الحاجة إلى ذلك. تعاني بروتوكولات التنصّت ضرورةَ تمكين كل عقدة بالاتصال ببقية العقد لتحقيق هذه البروتوكولات. ولتفادي هذه المشكلة ظهرت بروتوكولات الدليل التي لا تتطلب من العقد التنصّت على المسرى المشترك، بل الاحتفاظ بحالة كتل المعطيات صراحةً في مكان يسمى الدليل directory. وفي هذه الحالة يُخصّص لكل كتلة معطيات سجل record يحوي نسخة من هذه الكتلة، وحالتها في مختلف الخابيات. يسمى هذا السجل بمدخل الدليل entry، (الشكل 4).

  الشكل (4) مثال عن الدليل.

  يمكن تعريف الدليل بأنه بنية معطيات مساعِدة تتعقّب حالة التخبئة لكل سطر خابية (كتلة معطيات) في البنية المتوازية. وتناسب هذه البروتوكولات البنى ذات الذاكرة المشتركة الموزّعة (DSM) Distributed Shared Memory، إذ يسمح توزّع الذاكرة بالحيلولة دون الاختناق عند نقطة واحدة.

  يتطلب الحفاظ على الاتساق- في حالة بروتوكولات الدليل- اتصالات أكثر بين العقد والدليل. وقد يتبع بروتوكول الدليل طريقة البُطلان أو طريقة التحديث، ويمكن أن تُعطى لكل كتلة حالات مشابهة لتلك المعرَّفة في البروتوكول MESI.

  إذا رغب المعالج في قراءة سطر الخابية L فعليه إرسال طلب إلى العقدة التي تحوي دليلاً على ذاك السطر L، تسمى العقدة الموطن home بالنسبة إلى L. تستقبل العقدةُ الموطن الطلبَ وتبحث في الدليل. إذا تبيّن أن هذا السطر غير مخبّأ، أو أنه قابل للقراءة فقط (أي كانت حالته «نظيفة clean»)، تسجِّل العقدة الموطن أن العقدة الطالبة أصبحت «مشارِكة sharer»، وتعيد إليها نسخة من السطر المطلوب L. ولكن إذا تبيّن من الدليل أن ثمة عقدة ثالثة تحوي معطيات معدَّلة في خابيتها، وُسِم السطر بأنه «متسخ dirty»، وتحيل العقدةُ الموطن الطلبَ إلى العقدة «البعيدة remote» لاستحضار القيمة من خابيتها والإجابة. ينبغي في نهاية العملية أن تبلِّغ العقدةُ البعيدة العقدةَ الموطن بحسن إتمام العملية.

  وللحيلولة دون حجز كمية كبيرة من الذاكرة لتخزين معلومات الدليل، يمكن بناء الدليل بطريقة ديناميكية كقائمة مترابطة linked list، بحيث يحوي الدليل بداية القائمة فقط، كما هو مبيّن في الشكل (5).

  الشكل (5) الدليل الموزَّع.

  ويعدّ البروتوكول (SCI) Scalable Coherent Interface مثالاً على تطبيق الدليل الموزّع. ويُعرف هذا البروتوكول أيضاً باسم IEEE-1596-1992، ويهدف إلى التصعّد السلس مع الأعداد الكبيرة من العقد، من دون كلفة تخزين كبيرة في الذاكرة. ويجري ذلك اعتماداً على مبدأ القوائم المترابطة المزدوجة، والموزّعة في عقد البنية. ولعبور القائمة المشتركة ينبغي أولاً اتباع المؤشر في ترويسة الدليل في الشبكة إلى حين بلوغ المعالج المطلوب. وفي كل عقدة ينبغي الاحتفاظ بمؤشر خلفي نحو العقدة السابقة، ومؤشر أحادي نحو العقدة التالية إضافة إلى حالة الخابية.

  يمكن حذف عقد أو إضافتها من كل قائمة، بحسب العملية المطلوبة من المعالج وبحسب حالتها الراهنة. ففي حالة إخفاق الكتابة يجعل الدليل الموطن العقدةَ الطالبة R رأسَ القائمة الجديد، ويعيد حالة الرأس السابق. وترسل العقدة الطالبة R طلب إبطال إلى كل مدخل في القائمة المشتركة. يمثل الشكل (6) حالة تعريف رأس قائمة جديد، وإلغاء العقد الحالية.

  الشكل (6) تعريف رأس قائمة جديد وإلغاء العقد الحالية

  المقاربات الهجينة

  يمكن في بعض الحالات استخدام تراتبية ثنائية المستوى بحيث تكون كل عقدة نظاماً متعدد المعالجات. يتحقق الاتساق بين معالجات العقدة الواحدة بوساطة بروتوكول محدَّد، يسمى البروتوكول الداخلي inner، ويُحافَظ على اتساق العقد باستخدام بروتوكول آخر، يسمى البروتوكول الخارجي outer، وتُستخدم عادةً وحدة ملاءَمة adaptation لتمثيل العقدة في هذا البروتوكول. يمكن مثلاً استخدام بروتوكول الدليل بروتوكولاً خارجياً، وبروتوكول التنصّت بروتوكولاً داخلياً أو العكس، كما هو موضح في الشكل (7).

  الشكل (7) مقاربات هجينة لبروتوكولات اتساق الخابيات

   

  مراجع للاستزادة: - H. Elrewini, M. Abdelbarr, “Advanced Architecture and Parallel processing”, John Wiley, 2005. - O. Khan, M. Lis, Y. Sinangil, S. Devados, “DCC: A Dependable Cache coherence Multicore Architecture”, IEEE Computer Architecture Lectures, Jan. 2011. - M. Marty, “Cache Coherence Techniques for Multicore Processors”, PhD Thesis, University of Wisconsin-Madison, 2008. - D. Tsaliagos, “Design and Implementation of Directory-based Cache Coherence Protocol”, Technical Report, Forth-ICS/TR-418, May 2011.

التصنيف : كهرباء وحاسوب

النوع : كهرباء وحاسوب

المجلد: المجلد الرابع

رقم الصفحة ضمن المجلد : 0

آخر أخبار الهيئة :

البحوث الأكثر قراءة

اصدارات الموسوعة العربية

أسماء الباحثين

هل تعلم ؟؟

• - هل تعلم أن الأبلق نوع من الفنون الهندسية التي ارتبطت بالعمارة الإسلامية في بلاد الشام ومصر خاصة، حيث يحرص المعمار على بناء مداميكه وخاصة في الواجهات

• - هل تعلم أن الإبل تستطيع البقاء على قيد الحياة حتى لو فقدت 40% من ماء جسمها ويعود ذلك لقدرتها على تغيير درجة حرارة جسمها تبعاً لتغير درجة حرارة الجو،

• - هل تعلم أن أبقراط كتب في الطب أربعة مؤلفات هي: الحكم، الأدلة، تنظيم التغذية، ورسالته في جروح الرأس. ويعود له الفضل بأنه حرر الطب من الدين والفلسفة.

• - هل تعلم أن المرجان إفراز حيواني يتكون في البحر ويتركب من مادة كربونات الكلسيوم، وهو أحمر أو شديد الحمرة وهو أجود أنواعه، ويمتاز بكبر الحجم ويسمى الش

• هل تعلم أن الأبسيد كلمة فرنسية اللفظ تم اعتمادها مصطلحاً أثرياً يستخدم في العمارة عموماً وفي العمارة الدينية الخاصة بالكنائس خصوصاً، وفي الإنكليزية أب

• - هل تعلم أن أبجر Abgar اسم معروف جيداً يعود إلى عدد من الملوك الذين حكموا مدينة إديسا (الرها) من أبجر الأول وحتى التاسع، وهم ينتسبون إلى أسرة أوسروين

• - هل تعلم أن الأبجدية الكنعانية تتألف من /22/ علامة كتابية sign تكتب منفصلة غير متصلة، وتعتمد المبدأ الأكوروفوني، حيث تقتصر القيمة الصوتية للعلامة الك

شراء النسخة الورقية