المشروع الختامي: إعادة تخطيط جدول تيكات وإثبات انخفاض الإخفاقات

يلتقي كل ما علّمته هذه المهارة في جدول تيكات واحد. ثمانية أعمدة وثلاث مهام تقرؤه بطرق مختلفة وثلاثة تخطيطات في الذاكرة. تنمذج عنوان كل قيمة وتعدّ إخفاقات كل مهمة بالذاكرة المخبئية التي بنيتها وتقدّر كلفتها بنموذج الكمون وتثبت أي تخطيط يفوز. لا يفوز تخطيط في كل المهام؛ والهجين يفوز بالمزيج بإخفاقات أقل بـ1.5 مرة من مصفوفة البنى.

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

التخطيطات الثلاثة فكرة واحدة. التخطيط قائمة من مجموعات الأعمدة. تُخزَّن قيم المجموعة الواحدة صفًّا بعد صف وتتتابع المجموعات. مجموعة واحدة بكل الأعمدة هي مصفوفة البنى؛ ومجموعة لكل عمود هي بنية المصفوفات؛ ومجموعتان من أربعة أعمدة هما هجيننا. وهكذا تعطي دالة واحدة عنوان أي قيمة في أي تخطيط: تجاوز المجموعات التي تسبق مجموعة العمود ثم تقدّم row * len(group) + position قيمة داخلها.

def address(groups, row, col, n_rows, elem_bytes=ELEM_BYTES):    base = 0    for group in groups:        if col in group:            return base + (row * len(group) + group.index(col)) * elem_bytes        base += n_rows * len(group) * elem_bytes1    raise ValueError("column %d is in no group" % col)print(address([[0, 1, 2]], 2, 1, 10))print(address([[0], [1], [2]], 2, 1, 10))print(address([[1, 2], [0]], 3, 0, 10))

56
96
184

1. 1تشغل المجموعة n_rows * len(group) * elem_bytes بايت: وتبدأ المجموعة التالية بعدها مباشرة.

تحقق من النتائج الثلاث يدويًا. مع مجموعة واحدة من ثلاثة أعمدة يكون الصف 2 العمود 1 هو القيمة رقم 2 × 3 + 1 = 7 عند البايت 56. ومع مجموعة لكل عمود يبدأ العمود 1 بعد القيم العشر للعمود 0 عند البايت 80 ويبعد الصف 2 عنه 16 بايت: 96. وفي الهجين [[1, 2], [0]] تأتي مجموعة العمود 0 ثانية بعد 10 صفوف من قيمتين (160 بايت) ويبعد الصف 3 24 بايت: 184.

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

def workload_trace(groups, n_rows, reads, rows):    return [address(groups, row, col, n_rows) for row in rows for col in reads]def layout_misses(groups, n_rows, reads, rows=None):    rows = range(n_rows) if rows is None else rows    return count_misses(workload_trace(groups, n_rows, reads, rows))def compare_layouts(layouts, n_rows, reads, rows=None):    return {name: layout_misses(groups, n_rows, reads, rows) for name, groups in layouts.items()}def best_layout(misses):    return min(misses, key=misses.get)def time_ns(accesses, misses, hit_ns=HIT_NS, miss_ns=MISS_NS):    return (accesses - misses) * hit_ns + misses * miss_nsprint(workload_trace([[0, 1]], 4, [1, 0], [2]))for job, reads in WORKLOADS.items():    rows = sampled_rows(4000) if job == "lookup" else None    result = compare_layouts(LAYOUTS, 4000, reads, rows)    print(job, result, "->", best_layout(result))

[40, 32]
scan {'aos': 4000, 'soa': 500, 'hybrid': 2000} -> soa
quote {'aos': 4000, 'soa': 1500, 'hybrid': 2000} -> soa
lookup {'aos': 1000, 'soa': 8000, 'hybrid': 2000} -> aos

يريد المسح عمودًا واحدًا: بنية المصفوفات تحزم ثمانية أسعار في السطر (500 إخفاق) ومصفوفة البنى تهدر سبعة أثمان كل سطر تحمّله (4000 إخفاق). ويريد البحث النقطي القيم الثماني للصف: تأخذ مصفوفة البنى سطرًا واحدًا (1000 إخفاق) وبنية المصفوفات ثمانية (8000). وتقرأ مهمة العرض ثلاثة من أربعة أعمدة المجموعة الساخنة فالهجين جيد لكنه ليس الأفضل. واختيار التخطيط يتوقف على تكرار تنفيذ كل مهمة وهذا ما يقيسه المزيج.

def study(bars):    n_rows = min(int(bars.shape[0]), 4000)    misses = {}    accesses = 0    for job, reads in WORKLOADS.items():        rows = sampled_rows(n_rows) if job == "lookup" else None        misses[job] = compare_layouts(LAYOUTS, n_rows, reads, rows)        accesses += len(reads) * (len(rows) if rows is not None else n_rows)    mixed = {name: sum(misses[job][name] for job in WORKLOADS) for name in LAYOUTS}    best = best_layout(mixed)    return {"mixed": mixed, "mixed_best": best, "reduction": mixed["aos"] / mixed[best],            "ns": {name: time_ns(accesses, mixed[name]) for name in LAYOUTS}}out = study(load_bars())print(out["mixed"], "->", out["mixed_best"])print(round(out["reduction"], 2), "times fewer misses than the array of structs")print({name: round(ns / 1000) for name, ns in out["ns"].items()}, "microseconds")

{'aos': 9000, 'soa': 10000, 'hybrid': 6000} -> hybrid
1.5 times fewer misses than the array of structs
{'aos': 735, 'soa': 814, 'hybrid': 498} microseconds

بالجمع يخطئ مصفوفة البنى 9000 مرة وبنية المصفوفات 10000 والهجين 6000. لا يفوز الهجين في مهمة فوزًا مطلقًا ولا يخسر في أي منها خسارة فادحة: يكلّف المسح والعرض ضعف ما تدفعه بنية المصفوفات ويكلّف البحث ضعف ما تدفعه مصفوفة البنى ويفضّل المزيج التخطيط الذي لا يكون سيئًا أبدًا. في نموذج الكمون يعني ذلك 498 µs مقابل 735 µs لمصفوفة البنى: إخفاقات أقل بـ1.5 مرة وثلث أقل من الزمن. هذا هو الإثبات الذي يطلبه المشروع الختامي ولا يصح إلا لهذا المزيج من المهام.

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

• الدالة · السؤالتعتمد على
• address(groups, row, col, n_rows)أين هذه القيمة في الذاكرة؟حساب بسيط
• workload_trace(groups, n_rows, reads, rows)ما العناوين التي تمسّها المهمة؟address
• layout_misses(groups, n_rows, reads, rows)كم إخفاقًا في هذا التخطيط؟workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)وفي كل تخطيط؟layout_misses
• best_layout(misses)أيها يفوز؟حساب بسيط
• time_ns(accesses, misses)كم يكلّف من الزمن؟حساب بسيط
• study(bars)أي تخطيط يفوز بمزيج المهام؟compare_layoutsbest_layouttime_ns

المهارة التالية: انتهى جانب الذاكرة من الأداء. تنتقل المهارات التالية في مسار التحسين إلى المعالج: تنفيذ العملية نفسها على قيم كثيرة دفعة واحدة في مسجلات متجهة وتقاسم البيانات بين النوى دون أقفال.