الترابطية وإخفاقات التعارض

في ذاكرة مخبئية بفتحة واحدة لكل سطر يطرد سطران نشطان يتشاركان فتحة أحدهما الآخر مرة بعد مرة. امنح كل فتحة عدة طرق فتكاد المشكلة تختفي، إلا إذا تباعدت صفوف جدولك بمقدار 4096 بايت بالضبط. يبني هذا الدرس ذاكرة مخبئية ترابطية بالمجموعات ويبيّن كيف يمكن لحجم صف هو قوة للعدد 2 أن يجعل 100% من القراءات تخفق.

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

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

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

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1الوسم وفهرس المجموعة والإزاحة: كل منها قسمة صحيحة أو باقي قسمة للعنوان.

العنوان 74565 هو البايت 5 من السطر 1165. يذهب السطر 1165 إلى المجموعة 13 (1165 modulo 64) و18 هو ما تبقى من رقم السطر أي الوسم. كل سطر مجموعته 13 يتنافس على الطرق الثمانية لتلك المجموعة أيًّا كان وسمه.

حين تمتلئ مجموعة ويصل سطر جديد يجب أن يرحل أحد الأسطر. القاعدة المعتادة هي LRU: يُطرد السطر الأقل استعمالًا مؤخرًا. يمكننا حفظ كل مجموعة قائمة Python مرتبة من الأقل استعمالًا مؤخرًا إلى الأكثر استعمالًا مؤخرًا.

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

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

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1نقل السطر المصيب إلى النهاية يُبقي القائمة مرتبة: المدخل الأول هو دائمًا الأقل استعمالًا مؤخرًا.
2. 2تفقد المجموعة الممتلئة مدخلها الأول وهو السطر الأقل استعمالًا مؤخرًا.

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

الآن الفخ. جدول من 512 عمودًا من النوع float64 صفوفه بحجم 4096 بايت بالضبط. قراءة عمود تعني قراءة العناوين 0 و4096 و8192 وهكذا. في ذاكرتنا فهرس المجموعة هو رقم السطر modulo 64 والـ4096 بايت هي 64 سطرًا بالضبط، فكل هذه العناوين لها فهرس المجموعة نفسه. يطبع الكود مجموعة الصفوف الستة الأولى لحجم صف 4096 بايت ولحجم 4160 بايت أي 4096 مع سطر إضافي.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

مع صفوف 4096 بايت تتنازع كل إغلاقات العمود المجموعة 0. ومع صفوف 4160 بايت تتوزع على المجموعات 0 و1 و2 و3 وهكذا فتستعمل الذاكرة المخبئية كلها. يقرأ الكود التالي 96 إغلاقًا مرتين ويقيس معدل الإخفاق بطريق واحد وطريقين وأربعة وثمانية.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

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

يتبع المختبر الدرس: تقسيم العنوان والذاكرة المخبئية LRU ونوعا التتبّع والمقارنة حسب عدد الطرق والدراسة على جدول SPY الحقيقي.

• الدالة · السؤالتعتمد على
• split_address(address, line_bytes, n_sets)ما الوسم والمجموعة والإزاحة لعنوان؟القسمة الصحيحة
• SetAssocCache(size_bytes, line_bytes, ways).access(address)هل هذه القراءة إصابة في ذاكرة LRU متعددة الطرق؟مجموعات أسطر بترتيب LRU
• conflict_trace(n_lines, line_bytes, n_sets, rounds)ما العناوين التي تتصادم كلها في مجموعة واحدة؟حساب بسيط
• column_trace(n_rows, row_bytes, passes)ما العناوين التي تمسّها قراءة عمود؟حساب بسيط
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)كيف تغيّر الطرق الأكثر معدل الإخفاق؟SetAssocCache
• study(bars)كم تكلّف صفوف تتباعد 4096 بايت؟column_tracemiss_rates_by_ways

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