المشاركة الزائفة والحشو

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

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

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

يحتفظ الصنف أدناه لكل نواة بمجموعة الأسطر التي تحملها. نعيد ثلاث خطوات: تكتب النواة 0 البايت 0 ثم تكتب النواة 1 البايت 8 (السطر نفسه) ثم تكتب النواة 0 البايت 0 مرة أخرى.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1الكتابة تزيل السطر من كل نواة أخرى تحمله وتعدّ إبطالًا واحدًا لكل نسخة.

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

طريقة شائعة لعدّ الأحداث على التوازي هي إعطاء كل نواة عدّادها الخاص حتى لا تنتظر نواة أخرى. حجم كل عدّاد 8 بايت. ضعها واحدًا بعد آخر في مصفوفة فيتسع أربعة منها في سطر من 64 بايت. نبني كتابات 50 جولة تحديث بكتابة لكل نواة في كل جولة ونعيد تشغيلها والعدّادات متباعدة 8 بايت (متراصة) و64 بايت (محشوة). الزمن 1 ns لوصول في ذاكرة النواة نفسها و60 ns لإخفاق يجلب السطر من نواة أخرى.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

عند التراص تخفق الكتابات الـ200 كلها و199 منها تبطل الكاتب السابق: 12000 ns. وعند الحشو تحتفظ كل نواة بعدّادها في سطر خاص بها: أربعة إخفاقات باردة في البداية ثم تصيب كل كتابة ولا إبطال: 436 ns. هذا أسرع بـ27 مرة لنفس الحساب تمامًا لأن الأنوية الأربع لم تعد تنتزع السطر من بعضها.

لإعطاء كل عدّاد سطرًا خاصًا يجب أن تكون المسافة بين عدّادين مضاعفًا لحجم السطر فيُقرَّب حجم العنصر إلى المضاعف التالي للعدد 64. عدّاد من 8 بايت يأخذ 64 بايت أي يهدر 56. وعنصر من 65 بايت يأخذ 128. تقوم الدالة أدناه بالتقريب.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

في المختبر تعدّ أربع أنوية كل منها أيام التداول التي تتولاها ويذهب اليوم رقم i من جدول SPY إلى النواة يوم الأسبوع % 4. تقود أول 1000 يوم الكتابات بترتيب التاريخ. ولأن الأيام تتبع التقويم نادرًا ما تكتب النواة نفسها مرتين متتاليتين فيُنتزع السطر مرة بعد مرة. مع العدّادات المتراصة تخفق 818 كتابة من 1000 وتبطل 817 منها نواة أخرى؛ ومع المحشوّة تخفق الكتابات الأربع الأولى فقط.

يبني المختبر نموذج التماسك وتتبّعات العدّادات لكل نواة بخطوة معطاة وإعادة التشغيل وقاعدة الحشو ونموذج الزمن والدراسة على تواريخ SPY.

• الدالة · السؤالتعتمد على
• CoherentCaches(n_cores).access(core, address, write)إصابة أم إخفاق ومن يفقد نسخة؟حساب بسيط
• counter_address(core, stride_bytes)أين يوجد عدّاد نواة؟حساب بسيط
• update_trace(n_cores, n_updates, stride_bytes)ما الكتابات التي تجريها الأنوية؟counter_address
• run_trace(trace, n_cores)كم إخفاقًا وإبطالًا؟CoherentCaches
• padding_needed(item_bytes)كم يجب أن تتباعد العناصر؟حساب بسيط
• time_ns(stats)كم تستغرق عملية التشغيل؟كلفتا الإصابة والإخفاق
• study(bars)كم تكلّف المشاركة الزائفة على تواريخ SPY؟run_tracepadding_neededtime_ns

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