مرجع
آخر الزيارات

تنظيم الكاش في المعالجات التفرعية

1٬766 كلمة•0 مشاهدة•🗒️ منذ 18 يوماً
باختصار: مقدمة تُشكِّل بنية الذاكرة المشتركة Shared memory تصنيفاً أساسياً في أنظمة الحاسب التفرعية والأنظمة متعددة المعالِجات، وتتألف هذه البنية من عدة وحدات معالجة تتشارك معاً الوصول إلى مساحة ذاكرية مشتركة عامة ويتم تحقيق الاتصال والتخاطب ما بين…. تجد هنا «الكتابة المُحدِّثة write-update»، «بروتوكول المُلكية Write-Invalidate & Write-Back» و«بروتوكولات الاستطلاع Snooping Protocols» ضمن 9 أقسام.
المحتويات
  1. الكتابة المُحدِّثة write-update
  2. بروتوكول المُلكية Write-Invalidate & Write-Back
  3. بروتوكولات الاستطلاع Snooping Protocols
  4. الترابط المنطقي من النوع cache-cache
  5. الكتابة المتأخرة write-back
  6. الترابط المنطقي من النوع cache-memory
  7. بروتوكول write-invalidate & write-through
  8. MESI protocol
  9. مقدمة
تنظيم الكاش في المعالجات التفرعية

الكتابة المُحدِّثة write-update

تُستعمل كلتا السياستين بهدف تحقيق تناسق للمعطيات المنتشرة عبر الذواكر المخبئية. إذ تحافظ سياسة write-invalidate على تناسق المعطيات بالقراءة من الذواكر المخبئية المحلية إلى أن تتم عملية كتابة ما، فعندما يقوم أي معالج Q) مثلاً) بتحديث قيمة X الموجودة ضمن ذاكرته المخبئية عبر عملية كتابة فإنه يتم الإشارة إلى هذا التحديث عبر توضيع قيمة (1) منطقي ضمن بت خاص بكل ذاكرة مخبئية يُدعى بت التعديل dirty bit لإعلام جميع المعالِجات الأخرى ببطلان صلاحية جميع النسخ الأخرى لـ X الموجودة في بقية الذواكر المخبئية. ويستطيع المعالج Q الاستمرار بتحديث قيمة X طالما امتلك بت التعديل، بالتالي عندما يريد معالج آخر P قراءة قيمة X يتوجب عليه الانتظار حتى ينتهي المعالج Q من تحديثه عبر تصفير بت التعديل.

إضافةً إلى ذلك، تُحافظ سياسة write-update على تناسق المعطيات بين الذواكر المخبئية عبر نشر أي تحديث يحصل على أي ذاكرة مخبئية مباشرة إلى جميع النُسخ الأخرى الموجودة في بقية الذواكر المخبئية. بالتالي فإنه يتم توضيع القيمة(1) في جميع بتات التعديل خلال كل عملية كتابة، وبعد أن يتم التحديث على الجميع يتم تصفير هذه البتات. ويوضح الجدول(1.2) سياستي write-invalidate و write-update.

بروتوكول المُلكية Write-Invalidate & Write-Back

الجدول(1.5) بروتوكول المُلكية Write-Invalidate & Write-Back

كذلك، ليكن لدينا نظام ذاكرة مشتركة كالموضح في الشكل(1.6). يتألف هذا النظام من ممر ربط ومعالِجين P و Q. سنوضح كيف يتم الحفاظ على الترابط المنطقي للذواكر المخبئية باستخدام بروتوكول write-invalidate & write-through. بفرض قيمة الموقع الذاكري X الموجود ضمن الذاكرة المشتركة العامة هي (5) وأن العمليات التالية تم تطبيقها من قبل المعالجين P و Q بالتسلسل المعطى:

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

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

بروتوكول MESI

مثال 3:

بروتوكولات الاستطلاع Snooping Protocols

ومن ناحية أخرى، سنقوم فيما يلي باستعراض أهم بروتوكولات الاستطلاع المستعملة للحفاظ على الترابط المنطقي للذواكر المخبئية.

وعلى صعيد آخر، تعتمد بروتوكولات الاستطلاع على مراقبة الفعاليات الحاصلة على الممر وبالتالي نقل الأوامر الخاصة بتحقيق الترابط المنطقي بين أجزاء النظام. تتألف الذاكرة المشتركة العامة من كتل (بلوكات) يمتلك كل بلوك حالة متعلقة به تحدد التغيرات الحاصلة على محتوياته الداخلية. تتغير حالة كل بلوك كنتيجة للعمليات read-miss, read-hit, write-miss, write-hit. تعني حالة الفقدان cache-miss إلى عدم وجود البلوك المطلوب في الذاكرة المخبئية أو أنه موجود ولكن قد تم إلغاء تفعيله. تختلف بروتوكولات الاستطلاع عن بعضها فيما إذا كانت تقوم بتحديث أو إبطال تفعيل نُسخ المعطيات الموجودة في الذواكر المخبئية الأخرى عند قيام معالج ما بإجراء عملية كتابة. وهي تختلف كذلك على المكان الذي ستجلب منه المعطيات الجديدة في حال فقدانها من الذاكرة المخبئية.

الترابط المنطقي من النوع cache-cache

الكتابة المُبطِلة write-invalidate

وعلى صعيد آخر، يتم معالجة هذا الأمر من أجل الحفاظ على تناسق المعطيات عبر إحدى سياستين:

من جانب آخر، عندما تقوم مهمة ما عاملة على المعالج P (الموجود ضمن نظام متعدد المعالجات) بطلب معطيات موجودة في الموقع الذاكري X من الذاكرة المشتركة العامة فإنه يتم نسخ محتويات هذا الموقع إلى الذاكرة المخبئية الخاصة بالمعالج P ليتم تمريرها إليه. لنفترض الآن أن معالجاً آخر Q استطاع كذلك الوصول إلى الموقع الذاكري X ووضع قيمته في ذاكرته المخبئية الخاصة. ماذا يحدث عندما يريد المعالج Q تحديث قيمة ذاكرته المخبئية وكتابة قيمة جديدة فوق القيمة القديمة X الموجود صورة عنها كذلك في ذاكرة المعالج P المخبئية؟

الكتابة المتأخرة write-back

من جانب آخر، فعندما تقوم مهمة ما تعمل على المعالج P بطلب معطيات من الموقع الذاكري X الموجود في الذاكرة المشتركة العامة فإن محتويات الموقع X تُنسخ إلى الذاكرة المخبئية ليتم تمريرها إلى المعالج فيما بعد. الآن وعندما يقوم المعالج P بتحديث هذه القيمة الموجودة في ذاكرته المخبئية فإن النسخة الأخرى الموجودة في الذاكرة المشتركة تحتاج للتحديث كذلك بغية الحفاظ على تناسق للمعطيات بين الذاكرة المخبئية والذاكرة الرئيسية

ومن جهة أخرى، أما في سياسة write-back فإن الذاكرة الرئيسية سيتم تحديثها فقط عندما يتم استبدال كامل البلوك الموجود في الذاكرة المخبئية. أي تبقَ الكلمة الأصلية في الذاكرة الرئيسية على حالها ولا يُجرى التعديل إلا عندما نحتاج لاستبعاد البلوك الموافق من الذاكرة المخبئية. يتطلب تنفيذ هذه السياسة بت إضافي يُدعى بت التعديل dirty bit مع كلمة أو بلوك في الذاكرة المخبئية، تُضبط قيمة هذا البت على الصفر في البداية، وتسند له القيمة (1) عندما تُكتب معطيات في الكلمة أو البلوك الموافق للإشارة إلى ضرورة نقلها من جديد إلى الذاكرة الرئيسية قبل استبعادها من الذاكرة المخبئية، وتقلل هذه السياسة من عمليات الرجوع إلى الذاكرة، فقد تتغير محتويات موقع ما عدة مرات خلال فترة وجوده في الذاكرة المخبئية، ومايهمنا هو القيمة النهائية ولاداعي لنقل كل القيم الوسيطة التي قد تظهر أثناء الحساب ويوضح الجدول(1.1) سياستي write-through و write-back

وفي السياق ذاته، (*) تم الاعتماد في ترجمة مصطلحي write-back و write-through على كتاب «بنية الحاسب» للمهندس فادي حجار الصادر عن دار شعاع للنشر والعلوم طبعة عام 1999

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

الترابط المنطقي من النوع cache-memory

ومن ناحية أخرى، يتم تحقيق الترابط المنطقي بين الذاكرة العامة والذاكرة المخبئية ضمن نظام يتألف من ذاكرة مخبئية وحيدة عبر استخدام إحدى السياستين(*) :

الكتابة الآنية write-through

بروتوكول write-invalidate & write-through

مثال 2:

ومن ناحية أخرى، عند استخدام هذا البروتوكول تكون الذاكرة المشتركة العامة متناسقة دوماً مع آخر تحديث يطرأ على أي ذاكرة مخبئية. إذ يمكن لعدة معالِجات قراءة نٌسخِها من المعطيات بأمان من الذاكرة المشتركة العامة إلى أن يقوم معالج ما بتحديث نسخته الموجودة في ذاكرته المخبئية المحلية، عندئذِ يتم إبطال جميع النُسخ الموجودة في الذواكر المخبئية الأخرى وتحديث الذاكرة المشتركة العامة للإبقاء على حالة تناسق للمعطيات. يوضح الجدول(1.3) ملخصاً عن هذا البروتوكول والحالات التي يأخذها البلوك الذاكري.

الجدول(1.3) بروتوكول write-invalidate & write-through

وفي هذا السياق، ليكن لدينا نظام ذاكرة مشتركة كالموضح في الشكل(1.6). يتألف هذا النظام من ممر ربط ومعالِجين P و Q. سنوضح كيف يتم الحفاظ على الترابط المنطقي للذواكر المخبئية باستخدام بروتوكول write-invalidate & write-through. بفرض قيمة الموقع الذاكري X الموجود ضمن الذاكرة المشتركة العامة هي (5) وأن العمليات التالية تم تطبيقها من قبل المعالجين P و Q بالتسلسل المعطى:

علاوةً على ذلك، يوضح الجدول(1.4) محتويات كلِ من الذاكرة المشتركة والذاكرتين المخبأيتين لكل من المعالجين P و Q بعد تنفيذ كل عملية باستخدام البروتوكول السابق بهدف تحقيق الترابط المنطقي. كما يوضح الجدول كذلك حالة البلوك الحاوي على الموقع الذاكري X في كل من الذاكرتين المخبأيتين للمعالجين P و Q.

MESI protocol

ومن ناحية أخرى، Invalid (I): هي الحالة التي لا يكون فيها البلوك موجوداً ضمن الذاكرة المخبئية الحالية أو النسخة موجودة ولكنها غير شرعية.

ومن جهة أخرى، عملية الكتابة إلى ذاكرة مخبئية لها الحالة (S) هي كتابة من نوع write-through (يتم تحديث النسخة الموجودة ضمن الذاكرة المشتركة بشكل مباشر) بينما الكتابة إلى ذاكرة لها الحالة (E) هي كتابة من نوع write-back (أي لا يتم تحديث الذاكرة المشتركة إلى أن يتم استبدال كامل البلوك).

لتوضيح هذا المخطط سنقوم بتطبيق التسلسل التالي من الأحداث:

علاوةً على ذلك، Shared (S): تعني هذه الحالة أن نسخة البلوك موجودة ضمن أكثر من ذاكرة مخبئية وهي متطابقة مع نسخة الذاكرة المشتركة.

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

في هذا الإطار، Exclusive (E): هي حالة متوسطة بين الحالتين (S) و(M) وهي تعني أن هذه الذاكرة المخبئية هي الوحيدة التي تملك نسخة شرعية من البلوك متطابقة مع نسخة الذاكرة المشتركة.

وعلى صعيد آخر، Modified (M): تعني هذه الحالة أن هذه الذاكرة المخبئية هي الوحيدة التي تملك نسخة شرعية (محدّثة) من البلوك، وأن نسخة البلوك الموجودة في الذاكرة المشتركة هي نسخة غير محدّثة.

يوضح الشكل(3.3) مخطط الحالة لهذا البروتوكول:

إضافةً إلى ذلك، يتألف هذا البروتوكول من أربع حالات يمكن لكل بلوك ذاكري أن يأخذها أثناء وجوده ضمن أي ذاكرة مخبئية لأي معالج موجود في النظام. هذه الحالات هي:

مقدمة

علاوةً على ذلك، المشكلة الأولى هي تناقص درجة الأداء performance degradation التي تحدث بصورة أساسية عند محاولة عدة معالِجات الوصول إلى الذاكرة المشتركة العامة معاً بآن واحد، ويمكن استخدام تصميم نموذجي يتألف من ذواكر مخبئية (كاش cache) مرافقة لكل معالج لحل مشكلة التنافس، إلا أن وجود عدة نسخ من المعطيات تنتشر عبر هذه الذواكر المخبئية يقود إلى مشكلة أساسية أخرى هي مشكلة الترابط المنطقي Cache coherency لهذه النُسخ من المعطيات، إذ يمكن القول أن نسخ المعطيات الموجودة في الذواكر المخبئية هي نسخ مترابطة منطقياً إذا امتلكت جميعها نفس القيمة، وفي حال قيام أحد المعالِجات بالكتابة فوق هذه القيمة أو تعديلها من أجل أي نسخة من نسخ المعطيات تلك فإن هذه النسخة ستصبح متناقضة وغير مترابطة منطقياً مع بقية النُسخ لأنها لم تعد تملك نفس القيمة التي تمتلكها تلك النُسخ

في هذا الإطار، يتم الأخذ بعين الاعتبار مشكلتين أساسيتين أثناء تصميم نظام ذاكرة مشتركة:

من جانب آخر، تُشكِّل بنية الذاكرة المشتركة Shared memory تصنيفاً أساسياً في أنظمة الحاسب التفرعية والأنظمة متعددة المعالِجات، وتتألف هذه البنية من عدة وحدات معالجة تتشارك معاً الوصول إلى مساحة ذاكرية مشتركة عامة ويتم تحقيق الاتصال والتخاطب ما بين المهام العاملة على تلك المعالِجات عبر عمليات (القراءة من) و(الكتابة إلى) هذه المساحة الذاكرية المشتركة وكذلك يتم التنسيق وتحقيق التزامن بين جميع وحدات المعالجة باستخدام تلك الذاكرة المشتركة. يتألف النظام الحاسوبي ذو بنية الذاكرة المشتركة من مجموعة من المعالجات المستقلة، مجموعة من وحدات الذاكرة، وشبكة ربط بيني interconnection network. كما يوضح ذلك الشكل(1.1).

الطرائق الأساسية لتحقيق الترابط المنطقي للذواكر المخبئية

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.