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

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

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

لكل بايت عنوان، وهو رقم يقول أين يوجد. لإيجاد سطر عنوان اقسمه على حجم السطر وأهمل الباقي. يطبع الكود أدناه سطر أربعة عناوين.

line_bytes = 64for address in (0, 63, 64, 130):    print(address, "is in line", address // line_bytes)

0 is in line 0
63 is in line 0
64 is in line 1
130 is in line 2

العنوانان 0 و63 يتشاركان السطر 0، فبعد تحميل أحدهما يصبح الآخر مجانًا. يبدأ العنوان 64 السطر 1 ويقع 130 في السطر 2. كل هذا الموضوع ينبع من تلك القسمة الصحيحة.

أبسط ذاكرة مخبئية جدول فيه فتحة واحدة لكل سطر تستطيع حمله. ذاكرة بحجم 32 كيلوبايت وأسطر من 64 بايت فيها 512 فتحة. يُسمح لكل سطر من الذاكرة بفتحة واحدة فقط تُعرف بباقي القسمة: رقم السطر modulo عدد الفتحات. وهذه ذاكرة مخبئية مباشرة التعيين. ولأن أسطرًا كثيرة تتشارك فتحة، تحتفظ الفتحة أيضًا بـوسم يقول أي سطر تحوي الآن.

1. 1
   ابحث عن السطراقسم العنوان على حجم السطر.
2. 2
   ابحث عن الفتحةخذ رقم السطر modulo عدد الفتحات.
3. 3
   قارن الوسمإن كانت الفتحة تحوي هذا السطر فهي إصابة.
4. 4
   استبدل عند الإخفاقحمّل السطر في الفتحة وانسَ السطر الذي كان فيها.

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

def line_of(address, line_bytes):    return address // line_bytesclass Cache:    def __init__(self, size_bytes, line_bytes):        self.line_bytes = line_bytes        self.n_lines = size_bytes // line_bytes        self.tags = [None] * self.n_lines        self.hits = 0        self.misses = 0    def access(self, address):        line = line_of(address, self.line_bytes)1        slot = line % self.n_lines        if self.tags[slot] == line:2            self.hits += 1            return True        self.misses += 1        self.tags[slot] = line        return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")

[False, True, True, True, False, True, True, False, False]
5 hits and 4 misses

1. 1الفتحة هي رقم السطر modulo عدد الفتحات.
2. 2الإصابة تعني أن وسم الفتحة هو هذا السطر نفسه.

اقرأ قائمة الأعلام: القراءة الأولى تخفق وتحمّل السطر 0 والثلاث التالية تصيب لأنها في السطر 0 والعنوان 64 يخفق ويحمّل السطر 1 و72 يصيب والعودة إلى 0 تصيب مجددًا لأن السطر 0 لم يُطرد. ثم العنوان 512 هو السطر 8 الذي يُعيَّن أيضًا إلى الفتحة 0 (8 modulo 8) فيطرد السطر 0 وآخر قراءة للعنوان 0 تخفق من جديد: كلّفنا تعارض واحد إخفاقًا.

الآن استعمل الذاكرة المخبئية. قيمة float64 تأخذ 8 بايت فالسطر يحوي ثماني منها. اقرأ مصفوفة بالترتيب فتخفق أول قراءة في كل سطر وتصيب السبع التالية: إخفاق واحد من كل ثمانية. اقرأها بـخطوة أي بتخطي عدد ثابت من القيم بين القراءات فتقع القراءات في أسطر مختلفة. يقيس الكود التالي معدل الإخفاق لخطوات 1 و2 و4 و8 و16 قيمة.

def sequential_trace(n, elem_bytes):    return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride):    return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64):    cache = Cache(size_bytes, line_bytes)    for address in trace:        cache.access(address)    return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16):    print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))

stride 1 values: 0.125
stride 2 values: 0.25
stride 4 values: 0.5
stride 8 values: 1.0
stride 16 values: 1.0

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

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

closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout:   ", as_rows)

column layout: 0.125
row layout:    0.625

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

يطلب المختبر القطع التي قرأتها للتو بالترتيب نفسه وينتهي بالدراسة على جدول SPY الحقيقي.

• الدالة · السؤالتعتمد على
• line_of(address, line_bytes)أي سطر يحوي هذا العنوان؟القسمة الصحيحة
• Cache(size_bytes, line_bytes).access(address)هل هذه القراءة إصابة؟line_of
• sequential_trace(n, elem_bytes)ما العناوين التي تمسّها قراءة بالترتيب؟حساب بسيط
• strided_trace(n, elem_bytes, stride)ما العناوين التي تمسّها قراءة بقفزات؟حساب بسيط
• miss_rate(trace, size_bytes, line_bytes)ما نسبة التتبع التي تخفق؟Cache
• study(bars)كم تكلّف تخطيط الصفوف لإغلاقات SPY؟miss_ratestrided_trace

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