هرم الذاكرة وأرقام التأخير

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

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

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

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

كل مستوى أبطأ بعدة أضعاف من الذي فوقه، وRAM أبطأ من L1 بـ80 ضعفًا. تدور هذه المهارة كلها حول ضمان أن يُجاب عن معظم عمليات الوصول قرب القمة.

يبدأ الوصول من L1. إن كانت القيمة هناك كلّف الوصول تأخير L1 وانتهى. وإلا سأل المعالج L2 ثم L3 ثم RAM التي تملك القيمة دائمًا. كل مستوى يسأله يكلّف زمنًا سواء أصاب أم لا، فالوصول الذي وُجد في L3 قد دفع ثمن L1 وL2 وL3.

1. 1
   اسأل L1ادفع 1 ns. تنهي الإصابة الوصول.
2. 2
   عند الإخفاق اسأل L2ادفع 4 ns إضافية. تنهي الإصابة الوصول.
3. 3
   عند الإخفاق اسأل L3ادفع 15 ns إضافية. تنهي الإصابة الوصول.
4. 4
   عند الإخفاق اذهب إلى RAMادفع 80 ns إضافية. RAM تملك القيمة دائمًا.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

الوصول الذي تجيب عنه L3 يكلّف 20 ns لا 15: فالـ1 ns والـ4 ns المنفقة على الإخفاقين السابقين جزء من الفاتورة.

لا يوجد وصول واحد نموذجي، لذا نسأل عن المتوسط على كثير من عمليات الوصول. رجّح كلفة كل مسار بمدى تكراره. كل وصول يدفع تأخير L1؛ والنسبة التي تخفق في L1 فقط تدفع L2؛ والتي تخفق فيهما معًا تدفع L3؛ وهكذا. مكتوبًا في تعبير واحد بأقواس متداخلة مثل المستويات:

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

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h هي نسبة عمليات الوصول التي تخفق، فيُضرب كل قوس في النسبة التي تصل إلى ذلك الحد.

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

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

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach هي نسبة عمليات الوصول التي تزور كل مستوى: كلها تزور L1.
2. 2sum(cost) هو متوسط زمن الوصول: نفس 2.18 ns السابقة.

تجيب RAM عن 0.6% فقط من عمليات الوصول لكنها تستأثر بـ22% من زمن الانتظار، بينما تجيب L1 عن 90% منها وتأخذ 46% من الوقت. هذه هي الحقيقة المحورية وراء كل تحسين في هذه المهارة: لا تعدّ عمليات الوصول بل عدّ أين يذهب الوقت.

ما مدى أهمية هذا في جدول حقيقي؟ جدول أشرطة SPY اليومية في المختبر فيه 5405 صفوف وخمسة أعمدة (الافتتاح والأعلى والأدنى والإغلاق والحجم) أي 27025 قيمة. اقرأ كل قيمة مرة واحدة في ثلاث حالات: ذاكرات مخبئية ساخنة يصيب فيها كل شيء تقريبًا وفاترة وباردة يخفق فيها نصف عمليات الوصول في كل مستوى.

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

• الدالة · السؤالتعتمد على
• average_access_time(hit_rates)كم يكلّف وصول واحد في المتوسط؟جدول التأخير
• slowdown(hit_rates)كم مرة أبطأ من الإصابة دائمًا في L1؟average_access_time
• levels_served(hit_rates)أي مستوى يجيب عن عمليات الوصول؟معدلات الإصابة المحلية
• time_shares(hit_rates)أي مستوى يأخذ الوقت؟average_access_time
• scan_time_us(n_accesses, hit_rates)كم تستغرق n من عمليات الوصول؟average_access_time
• study(bars)كم تكلّف قراءة جدول SPY كاملًا؟scan_time_ustime_shares

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