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

مقدمة

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

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

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

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

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

يتم تحقيق الترابط المنطقي بين الذاكرة العامة والذاكرة المخبئية ضمن نظام يتألف من ذاكرة مخبئية وحيدة عبر استخدام إحدى السياستين(*) : الكتابة الآنية write-through الكتابة المتأخرة write-back فعندما تقوم مهمة ما تعمل على المعالج P بطلب معطيات من الموقع الذاكري X الموجود في الذاكرة المشتركة العامة فإن محتويات الموقع X تُنسخ إلى الذاكرة المخبئية ليتم تمريرها إلى المعالج فيما بعد. الآن وعندما يقوم المعالج P بتحديث هذه القيمة الموجودة في ذاكرته المخبئية فإن النسخة الأخرى الموجودة في الذاكرة المشتركة تحتاج للتحديث أيضاً بغية الحفاظ على تناسق للمعطيات بين الذاكرة المخبئية والذاكرة الرئيسية

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

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

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

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

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

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

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

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

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

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

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

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

(1) P reads X; (2) Q reads X; (3) Q updates X; (4) Q reads X;(5) Q updates X; (6) P updates X; (7) Q reads X

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

حالة البلوك الوصف

Valid [VALID]

النسخة متناسقة مع الذاكرة المشتركة العامة

Invalid [INV]

النسخة غير متناسقة مع الذاكرة المشتركة العامة

الحدث الإجراء المُتّخذ

Read-Hit

استخدم النسخة المحلية من الذاكرة المخبئية

Read-Miss

اجلب نسخة من الذاكرة المشتركة العامة. حوّل حالة هذه النسخة إلى Valid

Write-Hit

أنجز عملية الكتابة محليّاً. قم بإذاعة أمر إبطال صلاحية إلى جميع الذواكر المخبئية. قم بتحديث الذاكرة المشتركة العامة

Write-Miss

إجلب نسخة من الذاكرة المشتركة العامة. قم بإذاعة أمر إبطال صلاحية إلى جميع الذواكر المخبئية. قم بتحديث النسخة المحلية وحوّل حالتها إلى Valid.

Block replacement

طالما أن معطيات الذاكرة العامة متناسقة دوماً، فلا حاجة لعملية write-back عندما يتم استبدال البلوك.

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

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

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

(1) P reads X; (2) Q reads X; (3) Q updates X; (4) Q reads X;(5) Q updates X; (6) P updates X; (7) Q reads X.

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

حالة البلوك الوصف

Shared (Read-only) [RO]

المعطيات شرعية valid ويمكن قراءتها بأمان. يمكن لعدة نُسخ أن تمتلك هذه الحالة.

Exclusive (Read-Write) [RW]

يوجد فقط ذاكرة مخبئية واحدة تحوي النسخة الشرعية يمكن القراءة منها والكتابة إليها بأمان. بقية النسخ الموجودة في الذواكر المخبئية الأخرى هي غير شرعية invalid.

Invalid [INV]

النسخة متناسقة مع الذاكرة المشتركة العامة

الحدث الإجراء المُتّخذ

Read-Hit

استخدم النسخة المحلية من الذاكرة المخبئية

Read-Miss
  • في حال عدم وجود نسخة لها الحالة Exclusive (Read-Write) إجلب نسخة من الذاكرة المشتركة العامة. حوّل حالة هذه النسخة إلى Shared (Read-only).
  • في حال وجود نسخة لها الحالة Exclusive (Read-Write) قم بعمل نسخة من الذاكرة المخبئية التي تمتلك هذه الحالة. قم بتحديث الذاكرة العامة والذاكرة المحلية بهذه النسخة. حوّل حالة كلا الذاكرتين المخبأيتين إلى الحالة (Read-only).

Write-Hit
  • إذا كانت حالة النسخة هي Exclusive (Read-Write) أنجز الكتابة محلياً.
  • إذا كانت حالة النسخة هي Shared (Read-only) قم بإذاعة أمر إبطال صلاحية إلى جميع الذواكر المخبئية. حوّل هذه النسخة إلى الحالة Exclusive (Read-Write).

Write-Miss

إجلب نسخة إما من الذاكرة المخبئية التي تمتلك نسخة لها الحالة Exclusive (Read-Write)، أو من الذاكرة العامة نفسها. قم بإذاعة أمر إبطال صلاحية إلى جميع الذواكر المخبئية. حدّث النسخة المحلية وحوّل حالتها إلى Exclusive (Read-Write).

Block replacement
  • إذا كانت حالة النسخة هي Exclusive (Read-Write) فإنه يجب أن تتم كتابتها إلى الذاكرة العامة في حال تم استبدال البلوك.
  • إذا كانت حالة النسخة هي Invalid أو Shared (Read-only) فلا حاجة لأن تتم كتابتها إلى الذاكرة العامة في حال تم استبدال البلوك.

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

بروتوكول MESI

MESI protocol

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

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

  • Modified (M): تعني هذه الحالة أن هذه الذاكرة المخبئية هي الوحيدة التي تملك نسخة شرعية (محدّثة) من البلوك، وأن نسخة البلوك الموجودة في الذاكرة المشتركة هي نسخة غير محدّثة.
  • Shared (S): تعني هذه الحالة أن نسخة البلوك موجودة ضمن أكثر من ذاكرة مخبئية وهي متطابقة مع نسخة الذاكرة المشتركة.
  • Exclusive (E): هي حالة متوسطة بين الحالتين (S) و(M) وهي تعني أن هذه الذاكرة المخبئية هي الوحيدة التي تملك نسخة شرعية من البلوك متطابقة مع نسخة الذاكرة المشتركة.
  • Invalid (I): هي الحالة التي لا يكون فيها البلوك موجوداً ضمن الذاكرة المخبئية الحالية أو النسخة موجودة ولكنها غير شرعية.

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

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

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

التسلسل الحدث الإجراء المتخذ + حالة البلوك

1

المعالِج CPU0: قراءة a0

يقرأ المعالج CPU0 قيمة a0 من الذاكرة المشتركة – الحالة E

2

المعالِج CPU0: قراءة a0

يقرأ المعالج CPU0 قيمة a0 من الذاكرة المشتركة – الحالة E

3

المعالِج CPU0: كتابة(تحديث) a0

يُحدِّث المعالج CPU0 قيمة a0 في ذاكرته المخبئية فقط – الحالة M

4

المعالِج CPU0: كتابة a0

يُحدِّث المعالج CPU0 قيمة a0 في ذاكرته المخبئية فقط – الحالة M

5

المعالِج CPU1: قراءة a0

يقرأ المعالج CPU1 قيمة a0، تتدخل الذاكرة المخبئية للمعالج CPU0 وتقدم معطياتها لكل من الذاكرة الرئيسية والذاكرة المخبئية للمعالج CPU1 – الحالة S

6

المعالِج CPU1: كتابة a0

يُحدِّث المعالج CPU1 قيمة a0 في ذاكرته المخبئية والذاكرة المشتركة ويقوم بإبطال شرعية قيمة a0 الموجودة في بقية الذواكر المخبئية – الحالة E

7

المعالِج CPU1: كتابة a0

يُحدِّث المعالج CPU1 قيمة a0 في ذاكرته المخبئية فقط – الحالة M

8

المعالِج CPU0: كتابة a0

يقرأ المعالج CPU0 قيمة a0 من ذاكرته المخبئية، تتدخل الذاكرة المخبئية للمعالج CPU1 وتقدم معطياتها لكل من الذاكرة الرئيسية والذاكرة المخبئية للمعالج CPU1 – الحالة S، يقوم المعالج CPU0 بعدها بتحديث قيمة a0 في كل من ذاكرته المخبئية والذاكرة المشتركة ويقوم بإبطال شرعية قيمة a0 الموجودة في بقية الذواكر المخبئية – الحالة E

9

المعالِج CPU0: كتابة a2

يقرأ المعالج CPU0 قيمة a2 من الذاكرة المشتركة – الحالة E ومن ثم يقوم بتحديث هذه القيمة – الحالة M

10

المعالِج CPU0: كتابة a0

يعيد المعالج CPU0 قيمة a2 إلى الذاكرة المشتركة، يقرأ قيمة a2 منها –الحالة E ومن ثم يُحدِّث a0 – الحالة M

المراجع
  • Archibald, J. and Baer, J. 1986. Cache coherence protocols: evaluation using a multiprocessor simulation model. ACM Trans. Comput. Syst. 4, 4 (Sep. 1986), 273-298. DOI= http://doi.acm.org/10.1145/6513.6514
  • Goodman, J. R. 1983. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th Annual international Symposium on Computer Architecture (Stockholm, Sweden, June 13 - 17, 1983). International Conference on Computer Architecture. IEEE Computer Society Press, Los Alamitos, CA, 124-131. URL= http://portal.acm.org/citation.cfm?id=800046.801647
  • Handy, Jim. The Cache Memory Book. Academic Press, Inc., 1998. ISBN 0-12-322980-4
  • كتاب «بنية الحاسب» للمهندس فادي حجار الصادر عن دار شعاع للنشر والعلوم طبعة عام 1999
  • بوابة تقنية المعلومات
  • بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.