الجلب المسبق

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

حتى الآن كانت الذاكرة المخبئية تحمّل سطرًا حين تخفق قراءة. أما الجلب المسبق فيحمّله قبل ذلك. فإن صح التخمين وجدت القراءة اللاحقة السطر في الذاكرة المخبئية أصلًا وأصابت. لكل معالج حديث جالبات مسبقة عتادية تراقب عناوين القراءات وتخمّن التالي. أبسط تخمين: من قرأ السطر L سيريد السطر L + 1 بعده. في ذاكرتنا المعطاة دالة fill تحمّل سطرًا دون عدّ إصابة أو إخفاق وهذا هو الجلب المسبق بالضبط.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1جلب السطر التالي مسبقًا لا يكلّف شيئًا هنا: لا تُحتسب fill إصابة ولا إخفاقًا.

عند قراءة 800 قيمة بالترتيب تخفق ذاكرة عادية مرة لكل سطر أي 100 مرة. ومع جالب السطر التالي تخفق مرة واحدة فقط: بعد القراءة الأولى بالذات يكون السطر المطلوب بعدها موجودًا دائمًا. أما الحالة الثانية فتُظهر الحد. إن قفز البرنامج 4096 بايت في كل مرة فالسطر الذي يلي الحالي عديم الفائدة ولا يوفّر الجالب شيئًا: ما زالت 50 إخفاقًا من 50 قراءة.

تبحث الجالبات المسبقة الحقيقية عن نمط في الأسطر التي يقرؤها البرنامج. أشيعها الخطوة الثابتة: يقرأ البرنامج الأسطر 0 و3 و6 و9 قافزًا ثلاثة أسطر في كل مرة. يتذكر كاشف الخطوة آخر سطر وآخر فارق. وحين يساوي الفارق الجديد السابق فهو نمط والسطر التالي هو الحالي زائد الفارق. يلزم فارقان متساويان للتأكد فلا يخمّن أبدًا في أول قراءتين.

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

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1فارقان متساويان متتاليان: هذه خطوة فالسطر التالي هو الحالي زائد الفارق.

التتابع الأول خطوة من ثلاثة أسطر. لا يقول الكاشف شيئًا في أول قراءتين ثم يتوقع 9 و12 و15 دائمًا بخطوة واحدة إلى الأمام. وفي التتابع الثاني تُتجاهل القراءات المكررة للسطر 5 ولا تتأكد الخطوة 1 إلا عند القراءة الأخيرة. الكاشف الجيد حذر: فللتخمين الخاطئ ثمن كما سنرى.

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

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

في القراءة المرتبة يزيل الجالب 98.8% من الإخفاقات ويُستعمل 99.6% من جلباته. وفي القراءة المخلوطة لا يفعل شيئًا: فمن دون خطوة متكررة لا يصدر جلبًا إلا نادرًا (واحدًا فقط) فلا يضرّ أيضًا. هذا هو السلوك المطلوب. أما جالب يخمّن طوال الوقت فسيملأ الذاكرة المخبئية بأسطر لا يقرؤها أحد.

يقرأ المختبر 2000 إغلاق بثلاث طرق: مخزَّنة واحدًا بعد آخر ومقروءة بالترتيب، ومخزَّنة داخل صفوف من خمس قيم (خطوة 40 بايت)، ومخزَّنة واحدًا بعد آخر لكن مقروءة بترتيب حجم التداول المتصاعد. للأوليين نمط منتظم؛ أما الثالثة فتزور الأيام بترتيب يبدو عشوائيًا لأن حجم تداول يوم لا يقول شيئًا عن حجم اليوم التالي.

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

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

• الدالة · السؤالتعتمد على
• baseline_misses(trace)كم إخفاقًا بلا جلب مسبق؟Cache
• next_line_misses(trace)كم إخفاقًا مع جالب السطر التالي؟Cache.fill
• StridePrefetcher().observe(line)أي سطر يأتي بعد ذلك؟آخر سطر وآخر فارق
• run_with_prefetcher(trace, prefetcher)ماذا حدث: إخفاقات وجلبات ومفيدة؟Cache
• quality(trace)ما التغطية والدقة اللتان يبلغهما؟baseline_missesrun_with_prefetcher
• study(bars)أين يفيد الجالب في إغلاقات SPY؟qualitynext_line_misses

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