11. التخزين وهرم الذاكرة

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

فمثلًا، فكّر في الصيغتين التاليتين لدالة تحسب متوسط قيم مصفوفة رياضية بحجم N×N كما يظهر في الجدول 1. ومع أن النسختين تصلان إلى مواقع الذاكرة نفسها عددًا متساويًا من المرات (N2)، فإن الشيفرة على اليسار تنفَّذ في الأنظمة الحقيقية أسرع بنحو خمس مرات من الشيفرة على اليمين. وينشأ الفرق من الأنماط التي تصل بها كل نسخة إلى مواقع الذاكرة تلك. ونحلل هذا المثال قرب نهاية هذا الفصل باستخدام أداة تنميط الذاكرة Cachegrind.

الجدول 1. نسختان من دالة تصل إلى كل عنصر في مصفوفة رياضية بحجم NxN. وتختلفان فقط في طريقة الفهرسة في الذاكرة داخل المصفوفة الرياضية.

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

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

وكما نستكشف التخزين الحاسوبي الحديث، يبرز نمط شائع: الأجهزة ذات السعات الأعلى تقدم أداءً أدنى. وبعبارة أخرى، تستخدم الأنظمة أجهزة سريعة وأجهزة تخزّن قدرًا كبيرًا من البيانات، لكن لا يوجد جهاز واحد يجمع الأمرين. وتُعرف هذه المقايضة بين الأداء والسعة بـ هرم الذاكرة (memory hierarchy)، ويعرض الشكل 1 هذا الهرم بصريًا.

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

الشكل 1. تسلسل الذاكرة الهرمي

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

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

ومع أن هذا الفصل يركّز أساسًا على انتقال البيانات بين السجلات وذاكرات المعالج المؤقتة والذاكرة الرئيسية، فإن القسم التالي يوصّف أجهزة التخزين الشائعة عبر هرم الذاكرة. وسنفحص الأقراص ودورها في الصورة الأكبر لإدارة الذاكرة لاحقًا، في مناقشة الفصل 13 لـ الذاكرة الافتراضية.

يصنّف مصممو الأنظمة الأجهزة في هرم الذاكرة بحسب طريقة وصول البرامج إلى بياناتها. ويمكن للبرنامج الوصول إلى أجهزة التخزين الأساسي (primary storage) مباشرةً على المعالج. أي أن تعليمات التجميع في المعالج ترمّز الموقع الدقيق للبيانات التي ينبغي أن تسترجعها التعليمات. ومن أمثلة التخزين الأساسي سجلات المعالج والذاكرة الرئيسية (RAM)، التي تشير إليها تعليمات التجميع مباشرة (مثلًا، في تجميع IA32 بالصيغتين %reg و(%reg) على الترتيب).

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

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

وثمة معايير مهمة أخرى لتصنيف أجهزة الذاكرة تنشأ من خصائص أدائها وسعتها. وأكثر ثلاثة مقاييس إثارة للاهتمام هي:

• السعة (capacity): مقدار البيانات التي يستطيع الجهاز تخزينها. وتُقاس السعة عادةً بالبايتات.
• زمن الوصول (latency): مقدار الوقت الذي يستغرقه الجهاز للاستجابة بالبيانات بعد تلقّي أمر تنفيذ عملية استرجاع بيانات. ويُقاس زمن الوصول عادةً بأجزاء من الثانية (مثل أجزاء الألف من الثانية أو النانوثانية) أو بدورات المعالج.
• معدل النقل (transfer rate): مقدار البيانات التي يمكن نقلها بين الجهاز والذاكرة الرئيسية خلال فترة زمنية ما. ويُعرف معدل النقل أيضًا بـ الإنتاجية (throughput) ويُقاس عادةً بالبايتات في الثانية.

ويكشف استكشاف تنوع الأجهزة في حاسوب حديث عن تفاوت هائل في أداء الأجهزة على هذه المقاييس الثلاثة كلها. وينشأ تفاوت الأداء أساسًا من عاملين: المسافة والاختلافات في التقنيات المستخدمة لتنفيذ الأجهزة.

تسهم المسافة لأن أي بيانات يريد البرنامج استخدامها يجب في نهاية الأمر أن تكون متاحة للمكوّنات الحسابية في المعالج، أي وحدة الحساب والمنطق، للمعالجة. ويضع مصممو المعالجات السجلات قريبة من وحدة الحساب والمنطق لتقليل الوقت اللازم لانتشار الإشارة بينهما. لذلك، مع أن السجلات لا تستطيع تخزين إلا بضع بايتات وعددها ليس كبيرًا، فإن القيم المخزَّنة فيها متاحة لوحدة الحساب والمنطق شبه فورًا! وفي المقابل، تنقل أجهزة التخزين الثانوي مثل الأقراص البيانات إلى الذاكرة عبر أجهزة تحكم متنوعة تتصل بأسلاك أطول. وتؤدي المسافة الإضافية والمعالجة الوسيطة إلى إبطاء التخزين الثانوي بدرجة كبيرة.

«النانوثواني» لدى Grace Hopper

كانت رائدة الحوسبة والأدميرال في البحرية الأمريكية Grace Hopper توزع في كثير من الأحيان على الحاضرين في محاضراتها قطعًا من السلك بطول 11.8 بوصة. وتمثّل هذه القطع أقصى مسافة تقطعها إشارة كهربائية في نانوثانية واحدة، وكانت تُسمى «نانوثواني Grace Hopper». وقد استخدمتها لوصف قيود زمن الوصول في الاتصال بالأقمار الاصطناعية، ولبيان لماذا يجب أن تكون أجهزة الحوسبة صغيرة كي تكون سريعة. والتسجيلات التي تقدّم فيها Grace Hopper نانوثوانيها متاحة على YouTube.

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

ويفحص ما تبقى من هذا القسم تفاصيل أجهزة التخزين الأساسي والثانوي ويحلل خصائص أدائها.

11.2.1. التخزين الأساسي

تتألف أجهزة التخزين الأساسي من ذاكرة الوصول العشوائي (RAM)، أي أن الوقت اللازم للوصول إلى البيانات لا يتأثر بموقع البيانات في الجهاز. وبعبارة أخرى، لا تحتاج RAM إلى القلق بشأن أمور مثل تحريك أجزاء إلى الموضع الصحيح أو إرجاع بكرات الشريط. وهناك نوعان شائعان من RAM، هما ذاكرة الوصول العشوائي الساكنة (SRAM) وذاكرة الوصول العشوائي الديناميكية (DRAM)، وكلتاهما تؤدي دورًا مهمًا في الحواسيب الحديثة. ويوصّف الجدول 1 مقاييس أداء أجهزة التخزين الأساسي الشائعة وأنواع RAM التي تستخدمها.

الجهاز	السعة	زمن الوصول التقريبي	نوع RAM
السجل	4 - 8 بايتات	< 1 نانوثانية	SRAM
ذاكرة المعالج المؤقتة	1 - 32 ميغابايت	5 نانوثانية	SRAM
الذاكرة الرئيسية	4 - 64 غيغابايت	100 نانوثانية	DRAM

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

وتخزّن DRAM البيانات باستخدام مكوّنات كهربائية تُسمى المكثفات تحمل شحنة كهربائية. وسُمّيت «ديناميكية» لأن نظام DRAM يجب أن يجدّد شحنة مكثفاته بوتيرة متكررة للحفاظ على القيمة المخزَّنة. وتستخدم الأنظمة الحديثة DRAM لتنفيذ الذاكرة الرئيسية على وحدات تتصل بالمعالج عبر وصلة عالية السرعة تُسمى ناقل الذاكرة (memory bus).

ويوضح الشكل 1 مواضع أجهزة التخزين الأساسي نسبةً إلى ناقل الذاكرة. ولاسترجاع قيمة من الذاكرة، يضع المعالج عنوان البيانات التي يريد استرجاعها على ناقل الذاكرة ويشير إلى أنه ينبغي لوحدات الذاكرة تنفيذ قراءة. وبعد تأخير قصير، ترسل وحدة الذاكرة القيمة المخزَّنة عند العنوان المطلوب عبر الناقل إلى المعالج.

الشكل 1. معمارية التخزين الأساسي وناقل الذاكرة

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

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

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

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

ملاحظة

إذا كانت أحجام الذاكرات المؤقتة والذاكرة الرئيسية على نظامك تثير فضولك، فإن الأمر lscpu يطبع معلومات عن المعالج (بما في ذلك سعات ذاكراته المؤقتة). ويظهر تشغيل free -m سعة الذاكرة الرئيسية للنظام بالميغابايتات.

11.2.2. التخزين الثانوي

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

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

الشكل 2. صور أمثلة لـ (أ) بطاقة مثقبة، و(ب) بكرة شريط مغناطيسي، و(ج) أحجام مختلفة من أقراص المرنة. الصور من ويكيبيديا.

والوسائط القابلة للإزالة مثل الأقراص المرنة والأقراص الضوئية شكل شائع آخر من التخزين الثانوي. وتحتوي الأقراص المرنة مغزلًا من وسائط التسجيل المغناطيسية يدور فوق رأس قرص يقرأ محتوياته ويكتب فيها. ويعرض الشكل 2 صورًا لبطاقة مثقّبة ومحرك شريط وقرص مرن. وتخزّن الأقراص الضوئية مثل CD وDVD وBlu-ray المعلومات عبر نقرات صغيرة على القرص. ويقرأ المشغّل القرص بتسليط ليزر عليه، ويؤدي وجود النقرات أو غيابها إلى انعكاس الحزمة (أو عدمه)، فيُرمَّز الصفر والواحد.

التخزين الثانوي الحديث

الجهاز	السعة	زمن الوصول	معدل النقل
قرص فلاش	0.5 - 2 تيرابايت	0.1 - 1 ميليثانية	200 - 3,000 ميغابايت / ثانية
قرص صلب تقليدي	0.5 - 10 تيرابايت	5 - 10 ميليثانية	100 - 200 ميغابايت / ثانية
خادم شبكة بعيد	يتفاوت كثيرًا	20 - 200 ميليثانية	يتفاوت كثيرًا

يوصّف الجدول 2 أجهزة التخزين الثانوي المتاحة عادةً لمحطات العمل اليوم. ويعرض الشكل 3 كيف يمر المسار من التخزين الثانوي إلى الذاكرة الرئيسية عمومًا عبر عدة أجهزة تحكم وسيطة. فمثلًا، يتصل قرص صلب نموذجي بمتحكم Serial ATA، الذي يتصل بمتحكم الإدخال/الإخراج في النظام، الذي يتصل بدوره بناقل الذاكرة. وتجعل هذه الأجهزة الوسيطة الأقراص أسهل استخدامًا بتجريد تفاصيل اتصال القرص عن نظام التشغيل والمبرمج. غير أنها تدخل أيضًا تأخيرات في النقل عند تدفق البيانات عبر الأجهزة الإضافية.

الشكل 3. معمارية التخزين الثانوي وناقل الإدخال/الإخراج

وأكثر جهازي تخزين ثانوي شيوعًا اليوم هما محركات الأقراص الصلبة (HDD) ومحركات الأقراص ذات الحالة الصلبة (SSD) القائمة على الفلاش. ويتألف القرص الصلب من عدد قليل من الأقراص المسطحة الدائرية المصنوعة من مادة تتيح التسجيل المغناطيسي. وتدور الأقراص بسرعة، عادةً بسرعات تتراوح بين 5,000 و15,000 دورة في الدقيقة. وأثناء دوران الأقراص، يتحرك ذراع ميكانيكي صغير في طرفه رأس قرص عبر القرص لقراءة البيانات أو كتابتها على مسارات متحدة المركز (مناطق من القرص تقع عند القطر نفسه).

ويوضح الشكل 4 المكوّنات الرئيسية لـقرص صلب. وقبل الوصول إلى البيانات، يجب أن يحاذي القرص رأس القرص مع المسار الذي يحتوي البيانات المطلوبة. وتتطلب المحاذاة بسط الذراع أو سحبها حتى يستقر الرأس فوق المسار. ويُسمى تحريك ذراع القرص البحث (seeking)، ولأنه يتطلب حركة ميكانيكية، فإن البحث يدخل تأخيرًا صغيرًا يُعرف بـ زمن البحث (seek time) في الوصول إلى البيانات (بضعة أجزاء من الألف من الثانية). وعندما يكون الذراع في الموضع الصحيح، يجب أن ينتظر القرص دوران القرص حتى يصبح رأس القرص فوق الموقع الذي يخزّن البيانات المطلوبة مباشرةً. ويُدخل ذلك تأخيرًا قصيرًا آخر (بضعة أجزاء أخرى من الألف من الثانية) يُعرف بـ زمن الوصول الدوراني (rotational latency). وبالتالي، بسبب خصائصها الميكانيكية، تُظهر الأقراص الصلبة أزمنة وصول أعلى بكثير من أجهزة التخزين الأساسي الموصوفة سابقًا.

الشكل 4. المكوّنات الرئيسية لقرص صلب

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

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

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

وتستغل الأنظمة أساسًا شكلين من المحلية:

1. المحلية الزمنية (temporal locality): تميل البرامج إلى الوصول إلى البيانات نفسها مرارًا مع مرور الوقت. أي أنه إذا استخدم برنامج متغيرًا مؤخرًا، فمن المرجح أن يستخدمه مرة أخرى قريبًا.
2. المحلية المكانية (spatial locality): تميل البرامج إلى الوصول إلى بيانات قريبة من بيانات سبق الوصول إليها. و«القريب» هنا يشير إلى عنوان البيانات في الذاكرة. فمثلًا، إذا وصل برنامج إلى بيانات عند العنوانين N وN+4، فمن المرجح أن يصل إلى N+8 قريبًا.

11.3.1. أمثلة على المحلية في الشيفرة

لحسن الحظ، تُظهر أنماط البرمجة الشائعة كلا شكلي المحلية بتكرار كبير. خذ الدالة التالية مثلًا:

/* Sum up the elements in an integer array of length len. */
int sum_array(int *array, int len) {
    int i;
    int sum = 0;

    for (i = 0; i < len; i++) {
        sum += array[i];
    }

    return sum;
}

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

ويستفيد الوصول إلى محتويات المصفوفة أيضًا من المحلية المكانية. فمع أن البرنامج يصل إلى كل عنصر من عناصر المصفوفة مرة واحدة فقط، يحمّل نظام حديث أكثر من int واحد في المرة من الذاكرة إلى ذاكرة المعالج المؤقتة. أي أن الوصول إلى فهرس المصفوفة الأول يملأ الذاكرة المؤقتة ليس بالعدد الصحيح الأول فحسب، بل بالأعداد الصحيحة القليلة التالية له أيضًا. ويعتمد عدد الأعداد الصحيحة الإضافية التي تنتقل إلى الذاكرة المؤقتة تحديدًا على حجم الكتلة (block size) في الذاكرة المؤقتة، أي مقدار البيانات المنقولة إلى الذاكرة المؤقتة دفعة واحدة.

فمثلًا، مع حجم كتلة 16 بايتًا، ينسخ النظام أربعة أعداد صحيحة من الذاكرة إلى الذاكرة المؤقتة في المرة. وبذلك يتحمل الوصول إلى العدد الصحيح الأول الكلفة المرتفعة نسبيًا للوصول إلى الذاكرة الرئيسية، بينما تُلبّى عمليات الوصول إلى الأعداد الثلاثة التالية من الذاكرة المؤقتة، حتى لو لم يصل البرنامج إليها من قبل أبدًا.

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

الجدول 1. نسختان من دالة تصل إلى كل عنصر في مصفوفة رياضية بحجم NxN. وتختلفان فقط في الفهرسة في الذاكرة داخل المصفوفة الرياضية، لكن النسخة 1 (يسارًا) تنفَّذ أسرع بنحو خمس مرات.

في كلتا النسختين، تُظهر متغيرات الحلقة (i وj) ومتغير المجموع التراكمي (total) محلية زمنية جيدة لأن الحلقتين تستخدمانها مرارًا في كل تكرار. ولذلك، عند تنفيذ هذه الشيفرة، سيخزّن النظام تلك المتغيرات في مواقع تخزين سريعة على المعالج لتقديم أداء جيد.

لكن بسبب تنظيم ترتيب الصفوف أولًا (row-major order) للمصفوفة الرياضية في الذاكرة، تنفَّذ النسخة الأولى من الشيفرة (يسارًا) أسرع بنحو خمس مرات من النسخة الثانية (يمينًا). وينشأ التفاوت من الفرق في المحلية المكانية — فالنسخة الأولى تصل إلى قيم المصفوفة الرياضية تتابعيًا في الذاكرة (أي بترتيب عناوين الذاكرة المتعاقبة). وبذلك تستفيد من نظام يحمّل كتلًا كبيرة من الذاكرة إلى الذاكرة المؤقتة، لأنها تدفع كلفة الذهاب إلى الذاكرة مرة واحدة فقط لكل كتلة قيم.

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

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

11.3.2. من المحلية إلى الذاكرات المؤقتة

للمساعدة في توضيح كيف يتيح مفهوما المحلية الزمنية والمكانية تصميم الذاكرات المؤقتة، سنتبنى سيناريو مثالًا بأشياء مألوفة من العالم الواقعي: الكتب. لنفترض أن Fiona تؤدي كل واجباتها على مكتب في غرفتها الجامعية، وأن للمكتب مساحة صغيرة لا تتسع إلا لثلاثة كتب. وتحتفظ خارج غرفتها برف كتب فيه مساحة أكبر بكثير من المكتب. وأخيرًا، تملك كليتها عبر الحرم الجامعي مكتبة فيها تنوع هائل من الكتب. وقد يبدو «هرم تخزين الكتب» في هذا المثال شبيهًا بـالشكل 1. وبالنظر إلى هذا السيناريو، سنستكشف كيف تساعد المحلية في توجيه اختيار موقع التخزين الذي ينبغي أن تستخدمه Fiona لتخزين كتبها.

الشكل 1. تسلسل تخزين كتب افتراضي

11.3.3. المحلية الزمنية

تشير المحلية الزمنية إلى أنه إذا كان هناك كتاب تستخدمه Fiona بتكرار، فينبغي أن تبقيه قريبًا من مكتبها قدر الإمكان. وإذا احتاجت أحيانًا نقله إلى الرف لتفريغ مساحة عمل مؤقتة، فالكلفة ليست عالية، لكن سيكون من السخف إعادة كتاب إلى المكتبة إذا كانت ستحتاجه مرة أخرى في اليوم التالي. والعكس صحيح أيضًا: إذا كان هناك كتاب يشغل مساحة قيّمة على مكتبها أو رفها ولم تستخدمه منذ مدة طويلة، فيبدو الكتاب مرشحًا جيدًا لإعادته إلى المكتبة.

فأي الكتب إذن ينبغي أن تنقل Fiona إلى مساحة مكتبها الثمينة؟ في هذا المثال، سينظر الطلاب الحقيقيون على الأرجح في واجباتهم القادمة ويختارون الكتب التي يتوقعون أن تكون الأكثر فائدة. وبعبارة أخرى، لاتخاذ أفضل قرار تخزين، سيحتاجون مثاليًا إلى معلومات عن الاستخدام المستقبلي.

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

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

• عندما تحتاج Fiona إلى استخدام كتاب، تسترجعه من مكانه الحالي وتنقله إلى مكتبها.
• إذا كان المكتب ممتلئًا بالفعل، تنقل الكتاب الذي استخدمته قبل أطول مدة (أي الكتاب الذي ظل على المكتب دون استخدام لأطول فترة) إلى رفها.
• وإذا كان الرف ممتلئًا، تعيد الكتاب الأقل استخدامًا مؤخرًا على الرف إلى المكتبة لتفريغ مساحة.

ومع أن هذا المخطط قد لا يكون مثاليًا، فإن بساطته تجعله جاذبًا. فكل ما يتطلبه هو القدرة على نقل الكتب بين مواقع التخزين وقليل من المعلومات الوصفية عن ترتيب استخدام الكتب سابقًا. وفضلًا عن ذلك، يحقق هذا المخطط هدفَي المحلية الزمنية الأوليين جيدًا:

1. من المرجح أن تبقى الكتب المستخدمة بكثرة على المكتب أو الرف، ما يمنع الرحلات غير الضرورية إلى المكتبة.
2. تصبح الكتب قليلة الاستخدام في النهاية الكتاب الأقل استخدامًا مؤخرًا، وعندها يصبح من المنطقي إعادتها إلى المكتبة.

وتطبيق هذه الاستراتيجية على أجهزة التخزين الأساسي يبدو مشابهًا بشكل ملحوظ لمثال الكتب: عند تحميل البيانات في سجلات المعالج من الذاكرة الرئيسية، وفّر لها مساحة في ذاكرة المعالج المؤقتة. وإذا كانت الذاكرة المؤقتة ممتلئة بالفعل، وفّر مساحة فيها بـإخلاء (evicting) البيانات الأقل استخدامًا مؤخرًا إلى الذاكرة الرئيسية. وفي قسم التخزين المؤقت التالي، سنستكشف تفاصيل كيفية بناء هذه الآليات في أنظمة التخزين المؤقت الحديثة.

11.3.4. المحلية المكانية

تشير المحلية المكانية إلى أنه عند القيام برحلة إلى المكتبة، ينبغي لـ Fiona استرجاع أكثر من كتاب واحد لتقليل احتمال الرحلات المستقبلية إلى المكتبة. وتحديدًا، ينبغي أن تسترجع كتبًا إضافية «قريبة» من الكتاب الذي تحتاجه، لأن الكتب القريبة تبدو مرشحة جيدة لكتب قد تتحول خلاف ذلك إلى زيارات إضافية للمكتبة.

لنفترض أنها تأخذ مقررًا في الأدب عن مسرحيات Shakespeare التاريخية. وإذا كُلّفت في الأسبوع الأول من المقرر بقراءة Henry VI, Part I، فعندما تجد نفسها في المكتبة لاسترجاعه، من المرجح أن تجد الجزأين الثاني والثالث قريبين على الأرفف. وحتى لو لم تكن تعرف بعد ما إذا كان المقرر سيكلّفها الجزأين الآخرين، فليس من غير المعقول أن تفكر أنها قد تحتاجهما. أي أن احتمال الحاجة إليهما أعلى بكثير من كتاب عشوائي في المكتبة، تحديدًا لأنهما قريبان من الكتاب الذي تحتاجه فعلًا.

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

وفي القسم التالي، سنوصّف خصائص الذاكرة المؤقتة ونصف آليات تتيح للعتاد جعل تحديد المحلية واستغلالها يحدثان تلقائيًا.

وبعد أن وصّفنا أجهزة التخزين وتعرّفنا على النمطين المهمين من المحلية الزمنية والمكانية، صرنا جاهزين لاستكشاف كيفية تصميم ذاكرات المعالج المؤقتة وتنفيذها. والذاكرة المؤقتة (cache) جهاز تخزين صغير وسريع على المعالج يحتفظ بمجموعات جزئية محدودة من الذاكرة الرئيسية. وتواجه الذاكرات المؤقتة عدة أسئلة تصميمية مهمة:

• أي المجموعات الجزئية من ذاكرة البرنامج ينبغي أن تحتفظ بها الذاكرة المؤقتة؟
• متى ينبغي أن تنسخ الذاكرة المؤقتة مجموعة جزئية من بيانات البرنامج من الذاكرة الرئيسية إليها أو العكس؟
• كيف يستطيع النظام تحديد ما إذا كانت بيانات البرنامج موجودة في الذاكرة المؤقتة؟

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

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

وعند تحميل البيانات في الذاكرة المؤقتة بعد إخفاق، يجد المعالج غالبًا أن الذاكرة المؤقتة لا تملك مساحة حرة كافية. وفي هذه الحالات، يجب أن تُخلي الذاكرة المؤقتة أولًا بعض البيانات المقيمة لتفريغ مساحة للبيانات الجديدة التي تحمّلها. ولأن الذاكرة المؤقتة تخزّن مجموعات جزئية من البيانات المنسوخة من الذاكرة الرئيسية، فإن إخلاء بيانات مخزَّنة مؤقتًا عُدِّلت يتطلب من الذاكرة المؤقتة تحديث محتويات الذاكرة الرئيسية قبل إخلاء البيانات من الذاكرة المؤقتة.

ولتقديم كل الوظائف المذكورة أعلاه، يستخدم مصممو الذاكرات المؤقتة أحد ثلاثة تصاميم. ويبدأ هذا القسم بفحص الذاكرات المؤقتة المُخطَّطة مباشرة (direct-mapped caches) التي هي أقل تعقيدًا من التصاميم الأخرى.

11.4.1. الذاكرات المؤقتة المُخطَّطة مباشرة

تقسم الذاكرة المؤقتة المُخطَّطة مباشرة مساحة تخزينها إلى وحدات تُسمى أسطر الذاكرة المؤقتة (cache lines). وبحسب حجم الذاكرة المؤقتة، قد تحتفظ بعشرات أو مئات أو حتى آلاف من أسطر الذاكرة المؤقتة. وفي الذاكرة المؤقتة المُخطَّطة مباشرة، يكون كل سطر مستقلًا عن جميع الأسطر الأخرى ويحتوي نوعين مهمين من المعلومات: كتلة بيانات الذاكرة المؤقتة وبيانات وصفية.

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

وعندما يحاول برنامج الوصول إلى عنوان ذاكرة، يجب أن تعرف الذاكرة المؤقتة أين تبحث لتجد البيانات المقابلة، وأن تتحقق مما إذا كانت البيانات المطلوبة متاحة في موقع الذاكرة المؤقتة ذلك، وإذا كانت كذلك، أن تسترجع جزءًا من كتلة الذاكرة المؤقتة المخزَّنة إلى التطبيق الطالب. وتستعرض الخطوات التالية تفاصيل هذه العملية لإيجاد البيانات في الذاكرة المؤقتة واسترجاعها.

تحديد موقع البيانات المخزَّنة مؤقتًا

يجب أن تكون الذاكرة المؤقتة قادرة على تحديد ما إذا كانت المجموعة الجزئية من الذاكرة المقابلة لعنوان مطلوب مقيمة حاليًا فيها بسرعة. وللإجابة عن هذا السؤال، يجب أن تحدد الذاكرة المؤقتة أولًا سطر أو أسطر الذاكرة المؤقتة التي ستفحصها. وفي الذاكرة المؤقتة المُخطَّطة مباشرة، يقابل كل عنوان في الذاكرة سطر ذاكرة مؤقتة واحد بالضبط. وهذا القيد يفسّر اسم مُخطَّطة مباشرة — فهي تخطّط كل عنوان ذاكرة مباشرة إلى سطر ذاكرة مؤقتة واحد.

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

الشكل 1. مثال على تخطيط عناوين الذاكرة إلى سطور الذاكرة المؤقتة في ذاكرة مؤقتة معنونة مباشرة بأربعة سطور وكتل ذاكرة مؤقتة من 32 بايتاً

لاحظ أنه مع أن كل منطقة من الذاكرة تخطّط إلى سطر ذاكرة مؤقتة واحد فقط، فكثير من مجالات الذاكرة تخطّط إلى السطر نفسه. وتتنافس جميع مناطق الذاكرة التي تخطّط إلى السطر نفسه (أي الأجزاء ذات اللون نفسه في الشكل 1) على المساحة في سطر الذاكرة المؤقتة نفسه، فلا يمكن أن تقيم في الذاكرة المؤقتة في الوقت نفسه إلا منطقة واحدة من كل لون.

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

الشكل 2. الجزء الفهرسي الأوسط من عنوان الذاكرة يحدّد سطر ذاكرة مؤقتة.

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

تحديد محتويات الذاكرة المؤقتة

بعد ذلك، وبعد تحديد سطر الذاكرة المؤقتة المناسب، يجب أن تحدد الذاكرة المؤقتة ما إذا كان ذلك السطر يحمل العنوان المطلوب. ولأن عدة مجالات ذاكرة تخطّط إلى سطر الذاكرة المؤقتة نفسه، تفحص الذاكرة المؤقتة البيانات الوصفية للسطر للإجابة عن سؤالين مهمين: هل يحمل سطر الذاكرة المؤقتة هذا مجموعة جزئية صالحة من الذاكرة؟ وإذا كان كذلك، فأي المجموعات الجزئية الكثيرة التي تخطّط إلى هذا السطر يحمل حاليًا؟

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

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

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

الشكل 3. بعد استخدام بتّات الفهرسة في عنوان الذاكرة المطلوب لتحديد سطر الذاكرة المؤقتة المناسب، تتحقق الذاكرة المؤقتة بشكل متزامن من بتّة صالحيّة السطر وتقارن وسمه بوسم العنوان المطلوب. وإذا كان السطر صالحاً بوسم مطابق، نجح البحث بوصفه إصابة.

استرجاع البيانات المخزَّنة مؤقتًا

وأخيرًا، بعد استخدام عنوان الذاكرة المطلوب في البرنامج لإيجاد سطر الذاكرة المؤقتة المناسب، والتحقق من أن السطر يحمل مجموعة جزئية صالحة من الذاكرة تحتوي ذلك العنوان، ترسل الذاكرة المؤقتة البيانات المطلوبة إلى مكوّنات المعالج التي تحتاجها. ولأن حجم كتلة بيانات سطر الذاكرة المؤقتة (مثلًا 64 بايتًا) أكبر عادةً بكثير من مقدار البيانات التي تطلبها البرامج (مثلًا 4 بايتات)، تستخدم الذاكرات المؤقتة البتات الدنيا من العنوان المطلوب كـإزاحة (offset) داخل كتلة البيانات المخزَّنة مؤقتًا. ويوضح الشكل 4 كيف يحدد جزء الإزاحة من العنوان أي بايتات من كتلة الذاكرة المؤقتة يتوقع البرنامج استرجاعها.

الشكل 4. بالنسبة إلى كتلة بيانات ذاكرة مؤقتة، يحدّد الجزء الإزاحي من العنوان البايتات التي يريد البرنامج استرجاعها.

تقسيم عنوان الذاكرة

تحدد أبعاد الذاكرة المؤقتة عدد البتات التي تُفسَّر كأجزاء الإزاحة والفهرس والوسم في عنوان الذاكرة. وبالتكافؤ، يوحي عدد البتات في كل جزء من العنوان بما يجب أن تكون عليه أبعاد الذاكرة المؤقتة. وعند تحديد البتات التي تنتمي إلى كل جزء من العنوان، يفيد النظر إلى العنوان من اليمين إلى اليسار (أي من البت الأقل دلالة إلى الأكثر دلالة).

الجزء الأيمن من العنوان هو الإزاحة، ويعتمد طوله على بُعد حجم الكتلة في الذاكرة المؤقتة. ويجب أن يحتوي جزء الإزاحة من العنوان بتات كافية للإشارة إلى كل بايت ممكن داخل كتلة بيانات الذاكرة المؤقتة. فمثلًا، لنفترض أن الذاكرة المؤقتة تخزّن كتل بيانات بحجم 32 بايتًا. ولأن البرنامج قد يأتي طالبًا أيًا من هذه البايتات الـ32، تحتاج الذاكرة المؤقتة إلى بتات إزاحة كافية لوصف أي المواضع الـ32 الممكنة قد يريدها البرنامج بدقة. وفي هذه الحالة، ستحتاج إلى خمس بتات للإزاحة لأن خمس بتات لازمة لتمثيل 32 قيمة فريدة (log232 = 5). وفي الاتجاه المعاكس، على الذاكرة المؤقتة التي تستخدم أربع بتات للإزاحة أن تخزّن كتل بيانات بحجم 16 بايتًا (24 = 16).

ويبدأ جزء الفهرس من العنوان مباشرةً على يسار الإزاحة. ولتحديد عدد بتات الفهرس، فكّر في عدد الأسطر في الذاكرة المؤقتة، بما أن الفهرس يحتاج بتات كافية لتحديد كل سطر تحديدًا فريدًا. وبمنطق مشابه لمنطق الإزاحة، تحتاج ذاكرة مؤقتة فيها 1,024 سطرًا إلى 10 بتات للفهرس (log2 1,024 = 10). وبالمثل، على ذاكرة مؤقتة تستخدم 12 بتًا للفهرس أن تحتوي 4,096 سطرًا (212 = 4,096).

الشكل 5. يحدّد الجزء الفهرسي من العنوان سطر ذاكرة مؤقتة بشكل فريد، ويحدّد الجزء الإزاحي موقعاً في كتلة بيانات السطر بشكل فريد.

وتشكّل بتات العنوان المتبقية الوسم. ولأن الوسم يجب أن يحدد بشكل فريد المجموعة الجزئية من الذاكرة الموجودة داخل سطر الذاكرة المؤقتة، يجب أن يستخدم الوسم كل بتات العنوان المتبقية غير المطالب بها. فمثلًا، إذا استخدمت آلة عناوين باثنين وثلاثين بتًا، فإن ذاكرة مؤقتة بخمس بتات إزاحة و10 بتات فهرس تستخدم البتات الـ17 المتبقية من العنوان (32 - 15 = 17) لتمثيل الوسم.

أمثلة قراءة في ذاكرة مُخطَّطة مباشرة

فكّر في معالج بالخصائص التالية:

• عناوين ذاكرة بطول 16 بتًا
• ذاكرة مؤقتة مُخطَّطة مباشرة فيها 128 سطرًا
• كتل بيانات ذاكرة مؤقتة بحجم 32 بايتًا.

تبدأ الذاكرة المؤقتة فارغة (جميع الأسطر غير صالحة)، كما يظهر في الشكل 6.

الشكل 6. ذاكرة مؤقتة معنونة مباشرة فارغة كمثال

لنفترض أن برنامجًا يعمل على هذا المعالج يصل إلى مواقع الذاكرة التالية:

1. قراءة من العنوان 1010000001100100
2. قراءة من العنوان 1010000001100111
3. قراءة من العنوان 1001000000100000
4. قراءة من العنوان 1111000001100101

لتجميع التسلسل كله، اتبع هذه الخطوات عند تتبع سلوك الذاكرة المؤقتة:

1. قسّم العنوان المطلوب إلى ثلاثة أجزاء، من اليمين (البتات الدنيا) إلى اليسار (البتات العليا): إزاحة داخل كتلة بيانات الذاكرة المؤقتة، وفهرس إلى سطر الذاكرة المؤقتة المناسب، ووسم لتحديد أي مجموعة جزئية من الذاكرة يخزّنها السطر.
2. ابحث في الذاكرة المؤقتة باستخدام الجزء الأوسط من العنوان المطلوب لإيجاد سطر الذاكرة المؤقتة الذي يخطّط إليه العنوان.
3. افحص بت الصلاحية لسطر الذاكرة المؤقتة. وعندما يكون غير صالح، لا يستطيع البرنامج استخدام محتويات السطر (إخفاق في الذاكرة المؤقتة)، أيًا كان الوسم.
4. افحص وسم سطر الذاكرة المؤقتة. وإذا طابق وسم العنوان وسم سطر الذاكرة المؤقتة وكان السطر صالحًا، فإن كتلة بيانات السطر تحمل البيانات التي يبحث عنها البرنامج (إصابة في الذاكرة المؤقتة). وإلا، يجب أن تحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية عند الفهرس المحدد (إخفاق في الذاكرة المؤقتة).
5. عند الإصابة، استخدم بتات الإزاحة الدنيا من العنوان لاستخراج البيانات المطلوبة في البرنامج من الكتلة المخزَّنة. (غير معروض في المثال.)

تقسيم العنوان

ابدأ بتحديد كيفية تقسيم عناوين الذاكرة إلى أجزاء الإزاحة والفهرس والوسم. وانظر إلى أجزاء العنوان من البتات الدنيا إلى العليا (من اليمين إلى اليسار):

• الإزاحة: حجم كتلة 32 بايتًا يعني أن البتات الخمس اليمنى من العنوان (log2 32 = 5) تشكّل جزء الإزاحة. وبخمس بتات، تستطيع الإزاحة تحديد أي من البايتات الـ32 في الكتلة تحديدًا فريدًا.
• الفهرس: ذاكرة مؤقتة فيها 128 سطرًا تعني أن البتات السبعة التالية من العنوان (log2 128 = 7) تشكّل جزء الفهرس. وبسبع بتات، يستطيع الفهرس تحديد كل سطر ذاكرة مؤقتة تحديدًا فريدًا.
• الوسم: يتألف الوسم من أي بتات عنوان متبقية لا تنتمي إلى الإزاحة أو الفهرس. وهنا، تبقى للعنوان أربع بتات تشكّل الوسم (16 - (5 + 7) = 4).

الشكل 7. قراءة من العنوان 1010000001100100. الفهرس 0000011 (السطر 3) غير صالح، لذا يخفق الطلب وتحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية.

الشكل 8. قراءة من العنوان 1010000001100111. الفهرس 0000011 (السطر 3) صالح والوسم (1010) يطابق، لذا يصيب الطلب. تُخرِج الذاكرة المؤقتة البيانات بدءاً من البايت 7 (الإزاحة 0b00111) في كتلة بيانات.

الشكل 9. قراءة من العنوان 1001000000100000. الفهرس 0000001 (السطر 1) غير صالح، لذا يخفق الطلب وتحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية.

الشكل 10. قراءة من العنوان 1111000001100101. الفهرس 0000011 (السطر 3) صالح لكن الوسم لا يطابق، لذا يخفق الطلب وتحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية.

الكتابة إلى بيانات مخزَّنة مؤقتًا

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

1. في ذاكرة مؤقتة بالكتابة المباشرة (write-through cache)، تعدّل عملية كتابة الذاكرة القيمة في الذاكرة المؤقتة وتحدّث محتويات الذاكرة الرئيسية في الوقت نفسه. أي أن عملية الكتابة تزامن دائمًا محتويات الذاكرة المؤقتة والذاكرة الرئيسية فورًا.
2. وفي ذاكرة مؤقتة بالكتابة المرتجعة (write-back cache)، تعدّل عملية كتابة الذاكرة القيمة المخزَّنة في كتلة بيانات الذاكرة المؤقتة، لكنها لا تحدّث الذاكرة الرئيسية. وبالتالي، بعد تحديث بيانات الذاكرة المؤقتة، تختلف محتويات ذاكرة الكتابة المرتجعة عن البيانات المقابلة لها في الذاكرة الرئيسية.

ولتحديد كتل الذاكرة المؤقتة التي تختلف محتوياتها عن نظيراتها في الذاكرة الرئيسية، يخزّن كل سطر في ذاكرة الكتابة المرتجعة بتًا إضافيًا من البيانات الوصفية يُعرف بـ بت القذارة (dirty bit). وعند إخلاء كتلة البيانات من سطر قذر، يجب أولًا كتابة بيانات كتلة الذاكرة المؤقتة عودةً إلى الذاكرة الرئيسية لمزامنة محتوياتهما. ويعرض الشكل 11 ذاكرة مؤقتة مُخطَّطة مباشرة تتضمن بت قذارة لوسم الأسطر التي يجب كتابتها إلى الذاكرة عند الإخلاء.

الشكل 11. ذاكرة مؤقتة موسّعة ببتّة قذارة

وكما هي العادة، يكشف الفرق بين التصميمين عن مقايضة. فالذاكرات المؤقتة بالكتابة المباشرة أقل تعقيدًا من ذاكرات الكتابة المرتجعة، وتتفادى تخزين بيانات وصفية إضافية على شكل بت قذارة لكل سطر. وفي المقابل، تقلل ذاكرات الكتابة المرتجعة كلفة الكتابات المتكررة إلى الموقع نفسه في الذاكرة.

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

أمثلة كتابة في ذاكرة مُخطَّطة مباشرة (الكتابة المرتجعة)

تتصرف الكتابات إلى الذاكرة المؤقتة مثل القراءات، إلا أنها تضبط أيضًا بت القذارة لسطر الذاكرة المؤقتة المعدَّل. وعند إخلاء سطر قذر، يجب أن تكتب الذاكرة المؤقتة كتلة البيانات المعدَّلة إلى الذاكرة قبل التخلص منها.

لنفترض أن السيناريو الموصوف أعلاه يستمر بعمليتي وصول إضافيتين إلى الذاكرة:

1. كتابة إلى العنوان: 1111000001100000
2. كتابة إلى العنوان: 1010000001100100

الشكل 12. كتابة إلى العنوان 1111000001100000. الفهرس 0000011 (السطر 3) صالح والوسم (1111) يطابق، لذا يصيب الطلب. وبما أن هذا الوصول كتابة، تضبط الذاكرة المؤقتة بتّة قذارة السطر على 1.

الشكل 13. كتابة إلى العنوان 1010000001100100. الفهرس 0000011 (السطر 3) صالح لكن الوسم لا يطابق، لذا يخفق الطلب. وبما أن السطر الهدف صالح وقذار في آن واحد، يجب على الذاكرة المؤقتة حفظ كتلة البيانات الحالية في الذاكرة الرئيسية قبل تحميل الجديدة. وهذا الوصول كتابة، لذا تضبط الذاكرة المؤقتة بتّة قذارة السطر المحمّل حديثاً على 1.

في عمليتي الوصول الرابعة والسادسة في المثال، تُخلي الذاكرة المؤقتة بيانات لأن منطقتين من الذاكرة تتنافسان على سطر الذاكرة المؤقتة نفسه. وبعد ذلك، سنستكشف تصميمًا آخر للذاكرة المؤقتة يهدف إلى تقليل هذا النوع من التنافس.

11.4.2. إخفاقات الذاكرة المؤقتة والتصاميم الترابطية

يهدف مصممو الذاكرات المؤقتة إلى تعظيم معدل الإصابة فيها لضمان أن أكبر عدد ممكن من طلبات الذاكرة يمكنه تجنّب الذهاب إلى الذاكرة الرئيسية. ومع أن المحلية تبعث الأمل في تحقيق معدل إصابة جيد، لا يمكن للذاكرات المؤقتة الحقيقية أن تتوقع الإصابة في كل وصول لأسباب متنوعة:

• الإخفاقات الإجبارية أو إخفاقات البداية الباردة (compulsory/cold-start misses): إذا لم يصل برنامج إلى موقع ذاكرة (أو أي موقع قريب منه) أبدًا، فليس لديه أمل كبير في إيجاد بيانات ذلك الموقع في الذاكرة المؤقتة. ولذلك كثيرًا ما لا تستطيع البرامج تجنّب إخفاقات الذاكرة المؤقتة عند الوصول الأول إلى عناوين ذاكرة جديدة.
• إخفاقات السعة (capacity misses): تخزّن الذاكرة المؤقتة مجموعة جزئية من الذاكرة الرئيسية، ومثاليًا تخزّن بالضبط المجموعة الجزئية من الذاكرة التي يستخدمها البرنامج فعليًا. لكن إذا كان البرنامج يستخدم فعليًا ذاكرة تزيد على ما يتسع له الذاكرة المؤقتة، فلا يمكنه أن يجد كل البيانات التي يريدها فيها، ما يؤدي إلى إخفاقات.
• إخفاقات التعارض (conflict misses): لتقليل تعقيد إيجاد البيانات، تحدّ بعض تصاميم الذاكرات المؤقتة من المواضع التي يمكن أن تقيم فيها البيانات، وقد تؤدي هذه القيود إلى إخفاقات. فمثلًا، حتى لو لم تكن الذاكرة المؤقتة المُخطَّطة مباشرة ممتلئة بنسبة 100%، فقد ينتهي المطاف بالبرنامج إلى تخطيط عنواني متغيرين مستخدمين بكثرة إلى موقع الذاكرة المؤقتة نفسه. وفي هذه الحالات، يُخلي كل وصول إلى أحد المتغيرين الآخر من الذاكرة المؤقتة لأنهما يتنافسان على السطر نفسه.

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

وبديل الذاكرة المؤقتة المُخطَّطة مباشرة ذاكرة ترابطية. فالتصميم الترابطي يمنح الذاكرة المؤقتة مرونة الاختيار بين أكثر من موقع لتخزين منطقة من الذاكرة. وحدسيًا، يقلل وجود خيارات تخزين أكثر من احتمال التعارضات، لكنه يزيد التعقيد أيضًا لأن مواقع أكثر يجب فحصها في كل وصول.

وتتيح الذاكرة المؤقتة الترابطية الكاملة (fully associative) لأي منطقة ذاكرة أن تحتل أي موقع ذاكرة مؤقتة. وتقدم الذاكرات الترابطية الكاملة أكبر قدر من المرونة، لكنها تملك أيضًا أعلى تعقيد في البحث والإخلاء لأن كل موقع يجب النظر فيه في الوقت نفسه في أي عملية. ومع أن الذاكرات الترابطية الكاملة قيّمة في بعض التطبيقات الصغيرة المتخصصة (مثل TLB)، فإن تعقيدها العالي يجعلها غير مناسبة عمومًا لذاكرة معالج عامة الغرض.

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

11.4.3. ذاكرات ترابط المجموعات المؤقتة

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

وفي ذاكرة ترابط المجموعات، يخطّط جزء الفهرس من عنوان الذاكرة العنوان إلى مجموعة واحدة من أسطر الذاكرة المؤقتة. وعند إجراء بحث عن عنوان، تفحص الذاكرة المؤقتة كل سطر في المجموعة في الوقت نفسه. ويوضح الشكل 14 فحصي الوسم وبت الصلاحية في ذاكرة مؤقتة ترابط المجموعات من مسلكين.

وإذا احتوى أي من أسطر المجموعة الصالحة وسمًا يطابق جزء الوسم من العنوان، فإن السطر المطابق يُكمل البحث. وعندما يضيّق البحث النطاق إلى سطر ذاكرة مؤقتة واحد فقط، يتقدم كما في الذاكرة المُخطَّطة مباشرة: تستخدم الذاكرة المؤقتة إزاحة العنوان لإرسال البايتات المطلوبة من كتلة الذاكرة المؤقتة في السطر إلى المكوّنات الحسابية في المعالج.

الشكل 14. التحقق من بتّة الصالحيّة ومطابقة الوسم في ذاكرة مؤقتة مجموعة اتجاهية ثنائية

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

وللمساعدة في حل مشكلة الاختيار هذه، تلجأ الذاكرات المؤقتة إلى فكرة المحلية. وتحديدًا، تشير المحلية الزمنية إلى أن البيانات المستخدمة مؤخرًا يُرجَّح استخدامها مرة أخرى. ولذلك تتبنى الذاكرات المؤقتة الاستراتيجية نفسها التي استخدمها القسم السابق لإدارة رف الكتب في مثالنا: عند تقرير أي سطر في المجموعة سيُخلَّى، اختر السطر الأقل استخدامًا مؤخرًا (LRU). وتُعرف سياسة LRU بـ سياسة استبدال الذاكرة المؤقتة (cache replacement policy) لأنها تحكم آلية الإخلاء فيها.

وتتطلب سياسة LRU أن تخزّن كل مجموعة بتات إضافية من البيانات الوصفية لتحديد أي سطر في المجموعة استُخدم قبل أطول مدة. وكلما زاد عدد الأسطر في المجموعة، زاد عدد البتات اللازمة لترميز حالة LRU فيها. وتسهم بتات البيانات الوصفية الإضافية هذه في «التعقيد الأعلى» لتصاميم ترابط المجموعات مقارنةً بالتصاميم الأبسط المُخطَّطة مباشرة.

ويوضح الشكل 15 ذاكرة مؤقتة ترابط المجموعات من مسلكين، أي أن كل مجموعة تضم سطرين. وبسطرين فقط، تحتاج كل مجموعة بتًا واحدًا من بيانات LRU الوصفية لتتبّع أي سطر استُخدم قبل أطول مدة. وفي الشكل، تشير قيمة LRU البالغة صفرًا إلى أن السطر الأيسر هو الأقل استخدامًا مؤخرًا، وتشير القيمة واحد إلى أن السطر الأيمن هو الأقل استخدامًا مؤخرًا.

الشكل 15. ذاكرة مؤقتة مجموعة اتجاهية ثنائية تخزّن كل منها بتّة واحدة من بيانات LRU الوصفية لإعلام قرارات الإقصاء تحذير

اختيار الشكل 15 أن الصفر يعني «يسار» والواحد يعني «يمين» اختيار اعتباطي. ويختلف تفسير بتات LRU من ذاكرة مؤقتة إلى أخرى. وإذا طُلب منك التعامل مع ذاكرات مؤقتة في واجب دراسي، فلا تفترض أن الواجب يستخدم مخطط ترميز LRU نفسه!

أمثلة على ذاكرة ترابط المجموعات المؤقتة

فكّر في معالج بالخصائص التالية:

• عناوين ذاكرة بطول 16 بتًا.
• ذاكرة مؤقتة ترابط المجموعات من مسلكين فيها 64 مجموعة. لاحظ أن جعل الذاكرة المؤقتة ترابط المجموعات من مسلكين يضاعف سعتها التخزينية (سطران في المجموعة)، ولذلك يُنصّف هذا المثال عدد المجموعات بحيث تخزّن العدد نفسه من الأسطر الذي كان في مثال المُخطَّطة مباشرة السابق.
• كتل ذاكرة مؤقتة بحجم 32 بايتًا.
• سياسة استبدال LRU تشير إلى ما إذا كان السطر الأيسر في المجموعة هو الأقل استخدامًا مؤخرًا (LRU = 0) أو السطر الأيمن هو الأقل استخدامًا مؤخرًا (LRU = 1).

في البداية، تكون الذاكرة المؤقتة فارغة (جميع الأسطر غير صالحة وبتات LRU صفر)، كما يظهر في الشكل 16.

الشكل 16. ذاكرة مؤقتة مجموعة اتجاهية ثنائية فارغة كمثال

لنفترض أن برنامجًا يعمل على هذا المعالج يصل إلى مواقع الذاكرة التالية (مثل مثال المُخطَّطة مباشرة):

1. قراءة من العنوان 1010000001100100
2. قراءة من العنوان 1010000001100111
3. قراءة من العنوان 1001000000100000
4. قراءة من العنوان 1111000001100101
5. كتابة إلى العنوان 1111000001100000
6. كتابة إلى العنوان 1010000001100100

تقسيم العنوان

ابدأ بتحديد كيفية تقسيم عناوين الذاكرة إلى أجزاء الإزاحة والفهرس والوسم. وانظر إلى أجزاء العنوان من البتات الدنيا إلى العليا (من اليمين إلى اليسار):

• الإزاحة: حجم كتلة 32 بايتًا يعني أن البتات الخمس اليمنى من العنوان (log2 32 = 5) تشكّل جزء الإزاحة. وتتيح خمس بتات للإزاحة تحديد أي بايت في الكتلة تحديدًا فريدًا.
• الفهرس: ذاكرة مؤقتة فيها 64 مجموعة تعني أن البتات الست التالية من العنوان (log2 64 = 6) تشكّل جزء الفهرس. وتتيح ست بتات للفهرس تحديد كل مجموعة في الذاكرة المؤقتة تحديدًا فريدًا.
• الوسم: يتألف الوسم من أي بتات متبقية في العنوان لا تنتمي إلى الإزاحة أو الفهرس. وهنا، تبقى للعنوان خمس بتات للوسم (16 - (5 + 6) = 5).

الشكل 17. قراءة من العنوان 1010000001100100. كلا السطرين عند الفهرس 000011 (المجموعة 3) غير صالح، لذا يخفق الطلب وتحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية. بتّة LRU للمجموعة هي 0، لذا تحمّل الذاكرة المؤقتة البيانات في السطر الأيسر وتُحدّث بتّة LRU إلى 1.

الشكل 18. قراءة من العنوان 1010000001100111. السطر الأيسر عند الفهرس 000011 (المجموعة 3) يحمل وسماً مطابقاً، لذا يصيب الطلب.

الشكل 19. قراءة من العنوان 1001000000100000. كلا السطرين عند الفهرس 000001 (المجموعة 1) غير صالح، لذا يخفق الطلب وتحمّل الذاكرة المؤقتة البيانات من الذاكرة الرئيسية. بتّة LRU للمجموعة هي 0، لذا تحمّل الذاكرة المؤقتة البيانات في السطر الأيسر وتُحدّث بتّة LRU إلى 1.

الشكل 20. قراءة من العنوان 1111000001100101. عند الفهرس 000011 (المجموعة 3)، وسم أحد السطرين لا يطابق والسطر الآخر غير صالح، لذا يخفق الطلب. بتّة LRU للمجموعة هي 1، لذا تحمّل الذاكرة المؤقتة البيانات في السطر الأيمن وتُحدّث بتّة LRU إلى 0.

الشكل 21. كتابة إلى العنوان 1111000001100000. السطر الأيمن عند الفهرس 000011 (المجموعة 3) صالح ويحمل وسماً مطابقاً، لذا يصيب الطلب. وبما أن هذا الوصول كتابة، تضبط الذاكرة المؤقتة بتّة قذارة السطر على 1. وتبقى بتّة LRU عند 0 دلالةً على أن السطر الأيسر يظل الأقل استخداماً مؤخراً.

الشكل 22. كتابة إلى العنوان 1010000001100100. السطر الأيسر عند الفهرس 000011 (المجموعة 3) صالح ويحمل وسماً مطابقاً، لذا يصيب الطلب. وبما أن هذا الوصول كتابة، تضبط الذاكرة المؤقتة بتّة قذارة السطر على 1. وبعد الوصول إلى السطر الأيسر، تضبط الذاكرة المؤقتة بتّة LRU للسطر إلى 1.

في هذا المثال، تسلسل الوصول نفسه إلى الذاكرة الذي أنتج إخفاقَي تعارض في ذاكرة مُخطَّطة مباشرة لا يعاني أي تعارض في ذاكرة ترابط المجموعات من مسلكين.

ولأن الذاكرات المؤقتة تؤثر تأثيرًا كبيرًا في أداء البرنامج، توفر معظم الأنظمة أدوات تنميط لقياس استخدام البرنامج للذاكرة المؤقتة. ومن هذه الأدوات وضع cachegrind في Valgrind، ويستخدمه هذا القسم لتقييم أداء الذاكرة المؤقتة.

فكّر في البرنامج التالي الذي يولّد مصفوفة رياضية عشوائية بحجم N×N:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

int **genRandomMatrix(int n, int max) {
    int i, j;
    int **mat = malloc(n * sizeof(int *));

    for (i = 0; i < n; i++) {
        mat[i] = malloc(n * sizeof(int));

        for (j = 0; j < n; j++) {
            mat[i][j] = 1 + rand() % max;
        }
    }

    return mat;
}

void free_all(int **mat, int n) {
    int i;

    for (i = 0; i < n; i++) {
        free(mat[i]);
    }

    free(mat);
}

int main(int argc, char **argv) {
    int i, n;
    int **matrix;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <n>\n", argv[0]);
        fprintf(stderr, "where <n> is the dimension of the matrix\n");
        return 1;
    }

    n = strtol(argv[1], NULL, 10);
    srand(time(NULL));

    matrix = genRandomMatrix(n, 100);

    free_all(matrix, n);
    return 0;
}

قدّمت أقسام سابقة في هذا الفصل دالتين لحساب متوسط كل عنصر في مصفوفة رياضية. وهما تختلفان فقط في طريقة الفهرسة داخل المصفوفة الرياضية:

يستخدم هذا القسم أدوات تنميط الذاكرة المؤقتة لقياس الفروق بينهما كميًا.

11.5.1. تحليل أولي: التحليل النظري والقياس المرجعي

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

لنعدّل الدالة main لتضمين نداءات إلى الدالة gettimeofday لقياس الفرق في الأداء بين النسختين قياسًا دقيقًا:

int main(int argc, char** argv) {
   /* Validate command line parameters. */
   if (argc != 2) {
       fprintf(stderr, "usage: %s <n>\n", argv[0]);
       fprintf(stderr, "where <n> is the dimension of the matrix\n");
       return 1;
   }

   /* Declare and initialize variables. */
   int i;
   float res;
   double timer;
   int n = strtol(argv[1], NULL, 10);
   srand(time(NULL));
   struct timeval tstart, tend;
   int ** matrix = genRandomMatrix(n, 100);

   /* Time version 1. */
   gettimeofday(&tstart, NULL);
   res = averageMat_v1(matrix, n);
   gettimeofday(&tend, NULL);
   timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
   printf("v1 average is: %.2f; time is %g\n", res, timer);

   /* Time version 2. */
   gettimeofday(&tstart, NULL);
   res = averageMat_v2(matrix, n);
   gettimeofday(&tend, NULL);
   timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
   printf("v2 average is: %.2f; time is %g\n", res, timer);

   /* Clean up. */
   free_all(matrix, n);
   return 0;
}

وينتج عن تصريف الشيفرة وتشغيلها النتيجة التالية (لاحظ أن الأوقات ستتفاوت بحسب الآلة التي تُشغَّل عليها):

$ gcc -o cachex cachex.c
$ ./cachex 5000
v1 average is: 50.49; time is 0.053641
v2 average is: 50.49; time is 0.247644

هذا فرق كبير! ففي جوهر الأمر، الحل الذي يستخدم ترتيب الصفوف أولًا أسرع 4.61 مرة من الحل الثاني!

11.5.2. تحليل الذاكرة المؤقتة في العالم الواقعي: Cachegrind

التحليل النظري للحلين ثم تشغيلهما يؤكد أن النسخة الأولى أسرع من الثانية. لكنه لا يؤكد تفاصيل تحليل الذاكرة المؤقتة. لحسن الحظ، يمكن لمجموعة أدوات Valgrind المساعدة في ذلك. ناقشنا سابقًا في الكتاب كيف تساعد Valgrind في إيجاد تسربات الذاكرة في البرنامج. ويصف هذا القسم Cachegrind، محاكي الذاكرة المؤقتة في Valgrind. ويتيح Cachegrind للمبرمج دراسة كيفية تأثير برنامج أو دالة معينة في الذاكرة المؤقتة.

يحاكي Cachegrind كيفية تفاعل البرنامج مع هرم الذاكرة المؤقتة في الحاسوب. وفي كثير من الحالات، يستطيع Cachegrind اكتشاف تنظيم الذاكرة المؤقتة في الآلة تلقائيًا. وفي الحالات التي لا يستطيع فيها ذلك، يظل يحاكي ذاكرة المستوى الأول (L1) وذاكرة المستوى الأخير (LL). ويفترض أن ذاكرة المستوى الأول تتألف من مكوّنين مستقلين: ذاكرة التعليمات المؤقتة وذاكرة البيانات المؤقتة. وسبب ذلك أن لذاكرة المستوى الأخير أهم الآثار المترتبة على زمن التشغيل. كما أن لذاكرات L1 أدنى مستوى ترابط، فمن المهم ضمان تفاعل البرامج معها تفاعلًا جيدًا. وتطابق هذه الافتراضات بنية معظم الآلات الحديثة.

يجمع Cachegrind المعلومات التالية ويُخرجها:

• قراءات ذاكرة التعليمات المؤقتة (Ir)
• إخفاقات القراءة في ذاكرة التعليمات المؤقتة L1 (I1mr) وإخفاقات القراءة في ذاكرة التعليمات المؤقتة LL (ILmr)
• قراءات ذاكرة البيانات المؤقتة (Dr)
• إخفاقات القراءة في ذاكرة D1 المؤقتة (D1mr) وإخفاقات البيانات في ذاكرة LL المؤقتة (DLmr)
• كتابات ذاكرة البيانات المؤقتة (Dw)
• إخفاقات الكتابة في ذاكرة D1 المؤقتة (D1mw) وإخفاقات كتابة البيانات في ذاكرة LL المؤقتة (DLmw)

لاحظ أن إجمالي الوصول في D1 يُحسب بالعلاقة D1 = D1mr + D1mw وإجمالي الوصول في LL يُعطى بالعلاقة ILmr + DLmr + DLmw.

لنرَ كيف تعمل النسخة 1 من الشيفرة مع Cachegrind. لتشغيله، نفّذ Valgrind على الشيفرة المصرَّفة بالأمر التالي:

$ valgrind --tool=cachegrind --cache-sim=yes ./cachex 1000

في هذا الاستدعاء، تعمل أداة cachegrind في Valgrind كغلاف حول الملف التنفيذي cachex. ويساعد اختيار حجم مصفوفة رياضية أصغر مع Cachegrind على سرعة التنفيذ. ويُخرج Cachegrind معلومات عن عدد الإصابات والإخفاقات في الذاكرة المؤقتة في البرنامج ككل:

==28657== Cachegrind, a cache and branch-prediction profiler
==28657== Copyright (C) 2002-2017, and GNU GPL'd by Nicholas Nethercote et al.
==28657== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==28657== Command: ./cachex 1000
==28657==
--28657-- warning: L3 cache found, using its data for the LL simulation.
average is: 50.49; time is 0.080304
average is: 50.49; time is 0.09733
==28657==
==28657== I   refs:      122,626,329
==28657== I1  misses:          1,070
==28657== LLi misses:          1,053
==28657== I1  miss rate:        0.00%
==28657== LLi miss rate:        0.00%
==28657==
==28657== D   refs:       75,292,076  (56,205,598 rd   + 19,086,478 wr)
==28657== D1  misses:      1,192,118  ( 1,129,099 rd   +     63,019 wr)
==28657== LLd misses:         64,399  (     1,543 rd   +     62,856 wr)
==28657== D1  miss rate:         1.6% (       2.0%     +        0.3%  )
==28657== LLd miss rate:         0.1% (       0.0%     +        0.3%  )
==28657==
==28657== LL refs:         1,193,188  ( 1,130,169 rd   +     63,019 wr)
==28657== LL misses:          65,452  (     2,596 rd   +     62,856 wr)
==28657== LL miss rate:          0.0% (       0.0%     +        0.3%  )

لكن هذا التحليل يهمّه تحديدًا الإصابات والإخفاقات في نسختي دالة المتوسط هذه. ولعرض تلك المعلومات، استخدم أداة Cachegrind المسماة cg_annotate. ويُفترض أن تشغيل Cachegrind أنتج ملفًا في دليل العمل الحالي يشبه cachegrind.out.n، حيث n رقم معرّف عملية ما. لتشغيل cg_annotate، اكتب الأمر التالي (مع استبدال cachegrind.out.28657 باسم ملف المخرجات):

$ cg_annotate cachegrind.out.28657

I1 cache:         32768 B, 64 B, 8-way associative
D1 cache:         32768 B, 64 B, 8-way associative
LL cache:         8388608 B, 64 B, 16-way associative
Command:          ./cachex 1000
Data file:        cachegrind.out.28657
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:
User annotated:
Auto-annotation:  off

 ----------------------------------------------------------------------------
         Ir  I1mr  ILmr         Dr      D1mr  DLmr         Dw   D1mw   DLmw
 ----------------------------------------------------------------------------
122,626,329 1,070 1,053 56,205,598 1,129,099 1,543 19,086,478 63,019 62,856  PROGRAM TOTALS

 ----------------------------------------------------------------------------
        Ir I1mr ILmr         Dr      D1mr DLmr        Dw   D1mw   DLmw  file:function
 ----------------------------------------------------------------------------
14,009,017    3    3  9,005,008    62,688    0     1,004      0      0  averageMat_v1
14,009,017    0    0  9,005,008 1,062,996    0     1,004      0      0  averageMat_v2

وقد حرّرنا مخرجات هذا الأمر تحريرًا طفيفًا للتركيز على نسختي دالة المتوسط. وتُظهر هذه المخرجات أن النسخة 2 تنتج 1,062,996 إخفاقًا في البيانات، مقابل 62,688 إخفاقًا فقط في النسخة 1. ويقدّم Cachegrind دليلًا قاطعًا على أن تحليلنا صحيح!

ركّزت مناقشتنا للتخزين المؤقت حتى الآن على مستوى واحد من ذاكرة التخزين المؤقت على معالج أحادي النواة. لكن المعالجات الحديثة متعددة الأنوية وفيها عدة مستويات من الذاكرة المؤقتة. وعادةً يحتفظ كل نواة بذاكرة مؤقتة خاصة بها في أعلى مستوى (مستويات) هرم الذاكرة، ويتشارك الجميع ذاكرة مؤقتة واحدة في المستويات الأدنى. ويعرض الشكل 1 مثالًا على هرم الذاكرة في معالج رباعي الأنوية تحتوي فيه كل نواة على ذاكرة L1 مؤقتة خاصة، بينما تتشارك الأنوية الأربع ذاكرة L2 المؤقتة.

الشكل 1. مثال على تسلسل ذاكرة هرمي في معالج متعدد الأنوية. لكل من الأنوية الأربع ذاكرة مؤقتة L1 خاصة بها، وتتشارك الأنوية الأربع جميعها ذاكرة مؤقتة L2 واحدة يصلون إليها عبر ناقل مشترك. ويتصل المعالج متعدد الأنوية بذاكرة RAM عبر ناقل الذاكرة.

تذكّر أن المستويات الأعلى في هرم الذاكرة أسرع في الوصول وأصغر سعة من المستويات الأدنى. وبذلك تكون ذاكرة L1 المؤقتة أصغر وأسرع من ذاكرة L2 المؤقتة، التي تكون بدورها أصغر وأسرع من RAM. وتذكّر أيضًا أن الذاكرة المؤقتة تخزّن نسخة من قيمة من مستوى أدنى في هرم الذاكرة؛ فالقيمة المخزَّنة في ذاكرة L1 المؤقتة نسخة من القيمة نفسها المخزَّنة في ذاكرة L2 المؤقتة، التي هي نسخة من القيمة نفسها المخزَّنة في RAM. وبذلك تعمل المستويات الأعلى في هرم الذاكرة كذاكرات مؤقتة للمستويات الأدنى. ونتيجة لذلك، في مثال الشكل 1، تكون ذاكرة L2 المؤقتة ذاكرة مؤقتة لمحتويات RAM، وتكون ذاكرة L1 المؤقتة في كل نواة ذاكرة مؤقتة لمحتويات ذاكرة L2.

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

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

معلومات المعالج والذاكرة المؤقتة في أنظمة Linux

إذا كان تصميم معالجك يثير فضولك، فثمة طرق عديدة للحصول على معلومات عن المعالج وتنظيم ذاكرته المؤقتة على نظامك. فمثلًا، يعرض الأمر lscpu معلومات عن المعالج، بما في ذلك عدد أنويته ومستويات ذاكراته المؤقتة وأحجامها:

$ lscpu
...
CPU(s):                          12
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
...
L1d cache:                       192 KiB
L1i cache:                       384 KiB
L2 cache:                        3 MiB
L3 cache:                        16 MiB

توضح هذه المخرجات أن هناك ست أنوية إجمالًا (عدد Socket(s) مضروبًا في Core(s) per socket)، وأن كل نواة ذات خيطين فائقين (Thread(s) per core) لتبدو الأنوية الستة الفعلية 12 وحدة معالجة للنظام (انظر الفصل 5.9.2 لمزيد من المعلومات عن تعدد خيوط العتاد). وإضافةً إلى ذلك، تُظهر المخرجات وجود ثلاثة مستويات من الذاكرة المؤقتة (L1 وL2 وL3)، ووجود ذاكرتي L1 منفصلتين: واحدة لتخزين البيانات مؤقتًا (L1d) وأخرى لتخزين التعليمات مؤقتًا (L1i).

وإضافةً إلى lscpu، تحتوي ملفات في نظامي الملفات /proc و/sys معلومات عن المعالج. فمثلًا، يُخرج الأمر cat /proc/cpuinfo معلومات عن المعالج، ويسرد الأمر التالي معلومات عن الذاكرات المؤقتة لنواة معالج محددة (لاحظ أن هذه الملفات مسماة بحسب وحدات المعالجة الفائقة الخيوط لنواة، وفي هذا المثال cpu0 وcpu6 هما وحلتا المعالجة الفائقتا الخيوط في النواة 0):

$ ls /sys/devices/system/cpu/cpu0/cache
index0/  index1/  index2/  index3/

تشير هذه المخرجات إلى أن النواة 0 تملك أربع ذاكرات مؤقتة (index0 إلى index3). ولرؤية تفاصيل كل ذاكرة مؤقتة، افحص ملفات type وlevel وshared_cpu_list في دليل الفهرس:

$ cat /sys/devices/system/cpu/cpu0/cache/index*/type
Data
Instruction
Unified
Unified
$ cat /sys/devices/system/cpu/cpu0/cache/index*/level
1
1
2
3
$ cat /sys/devices/system/cpu/cpu0/cache/index*/shared_cpu_list
0,6
0,6
0,6
0-11

تشير مخرجات type إلى أن النواة 0 تملك ذاكرتين مؤقتتين منفصلتين للبيانات والتعليمات وذاكرتين موحّدتين أخريين. وربط مخرجات level بمخرجات type يكشف أن ذاكرتي البيانات والتعليمات كلتاهما من المستوى L1، بينما الذاكرتان الموحّدتان من المستويين L2 وL3 على الترتيب. وتُظهر shared_cpu_list كذلك أن ذاكرتي L1 وL2 خاصتان بالنواة 0 (تتشاركهما فقط وحلتا المعالجة 0 و6، وهما وحلتا المعالجة الفائقتا الخيوط في النواة 0)، وأن ذاكرة L3 مؤقتة يتشاركها جميع الأنوية الستة (جميع وحدات المعالجة الفائقة الخيوط الـ12، 0-11).

11.6.1. تماسك الذاكرة المؤقتة

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

وتنفّذ المعالجات متعددة الأنوية بروتوكول تماسك الذاكرة المؤقتة (cache-coherence protocol) لضمان رؤية متماسكة للذاكرة التي يمكن تخزينها مؤقتًا والوصول إليها من أنوية متعددة. ويضمن بروتوكول تماسك الذاكرة المؤقتة أن ترى أي نواة تصل إلى موقع ذاكرة أحدث قيمة معدَّلة لذلك الموقع، بدلًا من رؤية نسخة أقدم (بائتة) قد تكون مخزَّنة في ذاكرة L1 المؤقتة لديها.

11.6.2. بروتوكول MSI

ثمة بروتوكولات كثيرة مختلفة لتماسك الذاكرة المؤقتة. ونناقش هنا تفاصيل مثال واحد، هو بروتوكول MSI. ويضيف بروتوكول MSI (المعدَّلة، المشتركة، غير الصالحة: Modified, Shared, Invalid) ثلاثة أعلام (أو بتات) إلى كل سطر ذاكرة مؤقتة. وتكون قيمة العلم إما صفرًا (غير مضبوط) وإما واحدًا (مضبوط). وترمّز قيم الأعلام الثلاثة حالة كتلة بيانات السطر بالنسبة إلى تماسكها مع النسخ المخزَّنة مؤقتًا الأخرى للكتلة، وتُشغّل قيمها إجراءات تماسك الذاكرة المؤقتة عند القراءة أو الكتابة في كتلة البيانات في سطر الذاكرة المؤقتة. والأعلام الثلاثة التي يستخدمها بروتوكول MSI هي:

• علم M (المعدَّلة) الذي يدل عند ضبطه على أن الكتلة عُدِّلت، أي أن هذه النواة كتبت في نسختها من القيمة المخزَّنة مؤقتًا.
• علم S (المشتركة) الذي يدل عند ضبطه على أن الكتلة غير معدَّلة ويمكن مشاركتها بأمان، أي أن ذاكرات L1 مؤقتة متعددة يمكنها تخزين نسخة من الكتلة بأمان والقراءة من نسختها.
• علم I (غير الصالحة) الذي يدل عند ضبطه على أن الكتلة المخزَّنة مؤقتًا غير صالحة أو تحتوي بيانات بائتة (نسخة أقدم من البيانات لا تعكس القيمة الحالية لكتلة الذاكرة).

ويُفعَّل بروتوكول MSI عند عمليات القراءة والكتابة في مدخلات الذاكرة المؤقتة.

عند الوصول للقراءة:

• إذا كانت كتلة الذاكرة المؤقتة في الحالة M أو S، تُستخدم القيمة المخزَّنة مؤقتًا لتلبية القراءة (فقيمة نسختها هي أحدث قيمة لكتلة الذاكرة).
• وإذا كانت كتلة الذاكرة المؤقتة في الحالة I، فإن النسخة المخزَّنة مؤقتًا قديمة بالنسبة إلى إصدار أحدث من الكتلة، ويجب تحميل القيمة الجديدة للكتلة في سطر الذاكرة المؤقتة قبل أن يمكن تلبية القراءة. وإذا كانت ذاكرة L1 المؤقتة لنواة أخرى تخزّن القيمة الجديدة (أي أنها تخزّن القيمة مع ضبط علم M دلالةً على أنها تخزّن نسخة معدَّلة من القيمة)، فيجب على تلك النواة الأخرى أولًا كتابة قيمتها عودةً إلى المستوى الأدنى (مثلًا إلى ذاكرة L2 المؤقتة). وبعد تنفيذ الكتابة المرتجعة، تُلغي ضبط علم M في سطر الذاكرة المؤقتة (فنسختها والنسخة في المستوى الأدنى متوافقتان الآن) وتضبط بت S دلالةً على أن الكتلة في سطر الذاكرة المؤقتة هذا في حالة يمكن لأنوية أخرى تخزينها بأمان (فكتلة L1 متوافقة مع نسختها في ذاكرة L2 المؤقتة، وقد قرأت النواة القيمة الحالية للكتلة من نسخة L1 هذه). وبعد ذلك تستطيع النواة التي بدأت وصول القراءة على سطر مضبوط العلم I أن تحمّل القيمة الجديدة للكتلة في سطر ذاكرتها المؤقتة. فتُلغي ضبط علم I دلالةً على أن الكتلة صالحة الآن وتخزّن القيمة الجديدة، وتضبط علم S دلالةً على أن الكتلة يمكن مشاركتها بأمان (فهي تخزّن أحدث قيمة ومتوافقة مع النسخ المخزَّنة مؤقتًا الأخرى)، وتُلغي ضبط علم M دلالةً على أن قيمة كتلة L1 تطابق قيمة النسخة المخزَّنة في ذاكرة L2 المؤقتة (فالقراءة لا تعدّل النسخة المخزَّنة مؤقتًا في L1 من الذاكرة).

وعند الوصول للكتابة:

• إذا كانت الكتلة في الحالة M، اكتب في النسخة المخزَّنة مؤقتًا من الكتلة. ولا حاجة إلى تغييرات في الأعلام (فالكتلة تبقى في الحالة M).
• وإذا كانت الكتلة في الحالة I أو S، فأبلغ الأنوية الأخرى بأن الكتلة يُكتب فيها (تُعدَّل). وعلى ذاكرات L1 المؤقتة الأخرى التي تخزّن الكتلة في الحالة S أن تلغي ضبط بت S وتضبط بت I في كتلتها (فنسخها من الكتلة صارت قديمة بالنسبة إلى النسخة التي تكتب فيها النواة الأخرى). وإذا كانت ذاكرة L1 مؤقتة أخرى تملك الكتلة في الحالة M، فستكتب كتلتها عودةً إلى المستوى الأدنى وتضبط نسختها على I. ثم تحمّل النواة الكاتبة القيمة الجديدة للكتلة في ذاكرة L1 المؤقتة لديها، وتضبط علم M (فسيُعدَّل نسختها بالكتابة)، وتُلغي ضبط أعلام I (فنسختها صالحة الآن)، وتكتب في الكتلة المخزَّنة مؤقتًا.

وتتتبع الأشكال 2 حتى 4 مثالًا على تطبيق بروتوكول MSI لضمان تماسك عمليات القراءة والكتابة في كتلة ذاكرة مخزَّنة مؤقتًا في ذاكرات L1 الخاصة بنواتين. وفي الشكل 2، يبدأ مثالنا بنسخ كتلة البيانات المشتركة في ذاكرة L1 المؤقتة لكلتا النواتين مع ضبط علم S، ما يعني أن النسخ المخزَّنة مؤقتًا في L1 مطابقة لقيمة الكتلة في ذاكرة L2 المؤقتة (جميع النسخ تخزّن القيمة الحالية للكتلة، وهي 6). وعند هذه النقطة، تستطيع النواتان 0 و1 القراءة بأمان من النسخة المخزَّنة في ذاكرتيهما المؤقتتين من L1 من دون تفعيل إجراءات التماسك (فعلم S يدل على أن نسختهما المشتركة محدَّثة).

الشكل 2. في البداية، تمتلك كلتا الأنويتين نسخة من الكتلة في ذاكرتَي L1 الخاصتين بهما مع ضبط علَم S ‏(في الوضع المشترك)

وإذا كتبت النواة 0 بعد ذلك في نسخة الكتلة المخزَّنة في ذاكرتها المؤقتة من L1، يُخطر متحكم ذاكرة L1 المؤقتة لديها ذاكرات L1 المؤقتة الأخرى بأن تُبطل نسختها من الكتلة. فيُلغي متحكم ذاكرة L1 المؤقتة في النواة 1 ضبط علم S ويضبط علم I في نسخته، دلالةً على أن نسخته من الكتلة بائتة. وتكتب النواة 0 في نسختها من الكتلة في ذاكرة L1 المؤقتة لديها (فتغيّر قيمتها إلى 7 في مثالنا)، وتضبط علم M وتُلغي ضبط علم S في سطر الذاكرة المؤقتة دلالةً على أن نسختها عُدِّلت وتخزّن القيمة الحالية للكتلة. وعند هذه النقطة، تكون النسختان في ذاكرة L2 المؤقتة وفي ذاكرة L1 المؤقتة للنواة 1 بائتتين. وتظهر حالة الذاكرة المؤقتة الناتجة في الشكل 3.

الشكل 3. الحالة الناتجة للذاكرتين المؤقتتين بعد كتابة النواة 0 إلى نسختها من الكتلة

وعند هذه النقطة، تستطيع النواة 0 القراءة بأمان من نسختها من الكتلة المخزَّنة مؤقتًا لأن نسختها في الحالة M، أي أنها تخزّن أحدث قيمة مكتوبة للكتلة.

وإذا قرأت النواة 1 بعد ذلك من كتلة الذاكرة، يدل علم I في نسختها المخزَّنة مؤقتًا في L1 على أن نسختها من الكتلة في L1 بائتة ولا يمكن استخدامها لتلبية القراءة. ويجب على متحكم ذاكرة L1 المؤقتة في النواة 1 أولًا تحميل القيمة الجديدة للكتلة في ذاكرة L1 المؤقتة قبل أن يمكن تلبية القراءة. ولتحقيق ذلك، يجب على متحكم ذاكرة L1 المؤقتة في النواة 0 أولًا كتابة قيمتها المعدَّلة للكتلة عودةً إلى ذاكرة L2 المؤقتة، حتى تستطيع ذاكرة L1 المؤقتة في النواة 1 قراءة القيمة الجديدة للكتلة في ذاكرتها المؤقتة. ونتيجة هذه الإجراءات (كما يظهر في الشكل 4) أن النسختين المخزَّنتين مؤقتًا في L1 لكل من النواتين 0 و1 صارتا مخزَّنتين في الحالة S، دلالةً على أن نسخة L1 لكل نواة محدَّثة ويمكن استخدامها بأمان لتلبية القراءات اللاحقة في الكتلة.

الشكل 4. الحالة الناتجة للذاكرتين المؤقتتين بعد قراءة النواة 1 للكتلة تالياً

11.6.3. تنفيذ بروتوكولات تماسك الذاكرة المؤقتة

لتنفيذ بروتوكول تماسك الذاكرة المؤقتة، يحتاج المعالج إلى آلية ما لتحديد متى تتطلب عمليات الوصول إلى محتويات ذاكرة L1 المؤقتة لنواة ما تغييرات في حالة التماسك تشمل محتويات ذاكرة L1 المؤقتة لأنوية أخرى. ومن طرق تنفيذ هذه الآلية التجسّس (snooping) على ناقل تتشاركه جميع ذاكرات L1 المؤقتة. فيستمع متحكم ذاكرة مؤقتة متجسّس (يتجسّس) على الناقل بحثًا عن قراءات أو كتابات في كتل يخزّنها. ولأن كل طلب قراءة أو كتابة يكون بعنوان ذاكرة، يستطيع متحكم ذاكرة L1 مؤقتة متجسّس تحديد أي قراءة أو كتابة من ذاكرة L1 مؤقتة أخرى في كتلة يخزّنها، ثم الاستجابة على النحو المناسب بناءً على بروتوكول التماسك. فمثلًا، يستطيع ضبط علم I في سطر ذاكرة مؤقتة عندما يتجسّس كتابة في العنوان نفسه من ذاكرة L1 مؤقتة أخرى. وهذا المثال هو كيفية تنفيذ بروتوكول الإبطال عند الكتابة (write-invalidate protocol) بالتجسّس.

وبروتوكول MSI وبروتوكولات مشابهة مثل MESI وMOESI بروتوكولات إبطال عند الكتابة؛ أي بروتوكولات تُبطل نسخ المدخلات المخزَّنة مؤقتًا عند الكتابة. ويمكن استخدام التجسّس أيضًا في بروتوكولات تماسك الذاكرات المؤقتة بالإحلال (write-update)، حيث تُتجسَّس القيمة الجديدة للبيانات من الناقل وتُطبَّق لتحديث جميع النسخ المخزَّنة في ذاكرات L1 المؤقتة الأخرى.

وبدلًا من التجسّس، يمكن استخدام آلية تماسك ذاكرة مؤقتة قائمة على الأدلة (directory-based) لتفعيل بروتوكولات تماسك الذاكرة المؤقتة. وتتوسع هذه الطريقة أفضل من التجسّس بسبب قيود الأداء المترتبة على تشارك أنوية متعددة ناقلًا واحدًا. غير أن الآليات القائمة على الأدلة تتطلب حالة أكثر لاكتشاف مشاركة كتل الذاكرة، وهي أبطأ من التجسّس.

11.6.4. المزيد عن التخزين المؤقت متعدد الأنوية

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

ومع أن تماسك الذاكرة المؤقتة يحل مشكلة تماسك الذاكرة في المعالجات متعددة الأنوية ذات ذاكرات L1 المؤقتة المنفصلة، ثمة مشكلة أخرى قد تنشأ نتيجة بروتوكولات تماسك الذاكرة المؤقتة في المعالجات متعددة الأنوية. وهذه المشكلة، المسماة المشاركة الزائفة (false sharing)، قد تنشأ عندما تعمل خيوط متعددة من برنامج متوازٍ واحد متعدد الخيوط في الوقت نفسه عبر الأنوية المتعددة وتصل إلى مواقع ذاكرة قريبة من مواقع تصل إليها خيوط أخرى. وفي القسم 14.5 من الفصل 14، نناقش مشكلة المشاركة الزائفة وبعض حلولها.

ولمزيد من المعلومات والتفاصيل عن التخزين المؤقت في العتاد على المعالجات متعددة الأنوية، بما في ذلك البروتوكولات المختلفة وكيفية تنفيذها، راجع كتابًا في معمارية الحاسوب1.

الحواشي

1. من الاقتراحات «Computer Organization and Design: The Hardware and Software Interface» لـ David A. Patterson وJohn L. Hennessy.

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

ولأن الأنظمة الحديثة تحتاج إلى سعة عالية وأداء جيد معًا، يبني مصممو الأنظمة حواسيب بصور تخزين متعددة. والأهم أن النظام يجب أن يدير أي جهاز تخزين يحتفظ بأي جزء معين من البيانات. وتهدف الأنظمة إلى تخزين البيانات المستخدمة فعليًا في أجهزة تخزين أسرع، وتنقل البيانات قليلة الاستخدام إلى أجهزة تخزين أبطأ.

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

• المحلية الزمنية: تميل البرامج إلى الوصول إلى البيانات نفسها مرارًا مع مرور الوقت.
• المحلية المكانية: تميل البرامج إلى الوصول إلى بيانات قريبة من بيانات سبق الوصول إليها.

وتعمل المحلية أساسًا لذاكرات المعالج المؤقتة، التي تخزّن مجموعة جزئية صغيرة من الذاكرة الرئيسية في تخزين سريع على شريحة المعالج مباشرةً. وعندما يحاول برنامج الوصول إلى الذاكرة الرئيسية، يتحقق المعالج أولًا من وجود البيانات في الذاكرة المؤقتة؛ فإذا وجدها هناك، أمكنه تجنّب الرحلة الأكثر كلفة إلى الذاكرة الرئيسية.

وعندما يصدر برنامج طلبًا لقراءة الذاكرة أو الكتابة فيها، يقدّم عنوان موقع الذاكرة الذي يريد الوصول إليه. وتستخدم ذاكرات المعالج المؤقتة ثلاثة أجزاء من بتات عنوان الذاكرة لتحديد أي مجموعة جزئية من الذاكرة الرئيسية يخزّنها سطر ذاكرة مؤقتة:

1. بتات الفهرس الوسطى في العنوان تخطّط العنوان إلى موقع تخزين في الذاكرة المؤقتة.
2. بتات الوسم العليا تحدد بشكل فريد أي مجموعة جزئية من الذاكرة يخزّنها موقع الذاكرة المؤقتة.
3. بتات الإزاحة الدنيا تحدد أي بايتات من البيانات المخزَّنة يريد البرنامج الوصول إليها.

وأخيرًا، اختتم هذا الفصل ببيان كيف يمكن لأداة Cachegrind تمكين تنميط أداء الذاكرة المؤقتة لبرنامج قيد التشغيل. فيحاكي Cachegrind تفاعل البرنامج مع هرم الذاكرة المؤقتة ويجمع إحصاءات عن استخدام البرنامج للذاكرة المؤقتة (مثل معدلات الإصابة والإخفاق).

• جميع تمارين الفصل 11