التنبؤ بالتفرعات

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

يعمل المعالج كخط تجميع: بينما تنفَّذ تعليمة تكون التي تليها قد جُلبت وفُكَّ ترميزها. يكسر if الخط لأن التعليمة التالية تعتمد على جوابه وهو لم يجهز بعد. لذلك يجري المعالج تنبؤًا بالتفرع ويتقدم بناءً عليه. إن صح التخمين لا يضيع شيء. وإن أخطأ يُرمى العمل المنجز على المسار الخاطئ ويعاد تشغيل الخط، وهذا يكلّف نحو 15 دورة في نواة حديثة أي بقدر زيارة الذاكرة المخبئية من المستوى الثاني. نكتب نتيجة التفرع True حين يُؤخذ. وفي حلقة تداول يكون التفرع مثلًا if daily_return > 0 وتدفق نتائجه هو ببساطة True أو False لكل يوم.

def taken_sequence(values, threshold):    return [bool(value > threshold) for value in values]def always_taken_mispredicts(outcomes):    return sum(1 for outcome in outcomes if not outcome)returns = [0.004, -0.012, 0.007, 0.001, -0.003, 0.009]outcomes = taken_sequence(returns, 0)print(outcomes)print(always_taken_mispredicts(outcomes), "misses out of", len(outcomes))

[True, False, True, True, False, True]
2 misses out of 6

من ستة أيام كان لأربعة منها عائد موجب، فيُؤخذ التفرع أربع مرات ولا يُؤخذ مرتين. أبسط متنبئ، مأخوذ دائمًا، يخطئ بالضبط في النتيجتين False. إنه يصيب بقدر ما يُؤخذ التفرع ويتجاهل التاريخ.

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

def one_bit_mispredicts(outcomes):    guess = False    wrong = 0    for outcome in outcomes:        if guess != outcome:            wrong += 1        guess = outcome    return wrongdef two_bit_mispredicts(outcomes):    counter = 1    wrong = 0    for outcome in outcomes:        if (counter >= 2) != outcome:            wrong += 1        counter = min(3, counter + 1) if outcome else max(0, counter - 1)1    return wrongruns = [True] * 4 + [False] * 4 + [True] * 4stray = [True] * 6 + [False] + [True] * 6for name, stream in (("runs", runs), ("one stray", stray)):    print(name, "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", two_bit_mispredicts(stream))

runs | 1-bit 3 | 2-bit 5
one stray | 1-bit 3 | 2-bit 2

1. 1يتحرك العدّاد خطوة نحو النتيجة ويقف عند 0 و3: هذا ما يجعله مشبعًا.

في سلاسل الأربعة يخطئ المتنبئان ثلاث مرات (التخمين الأول والتحولان). ومع False شاذ واحد بين نتائج مأخوذة يخطئ متنبئ البت الواحد ثلاث مرات ومتنبئ البتين مرة واحدة فقط لأن العدّاد ينزل من 3 إلى 2 ويظل يخمّن «مأخوذ». ولهذا تفضّل المعالجات الحقيقية العدّادات. وتذكّر الجانب الآخر: حين لا يكون للنتائج نمط لا يستطيع أي متنبئ أن يتفوق على تخمين الجواب الأكثر تكرارًا.

لتحويل الإخفاقات إلى زمن نجمعها: كل تفرع يكلّف دورة أساسية واحدة وكل خطأ يضيف عقوبة 15. والآن التجربة التي سُمّي بها هذا الدرس: خذ أول 4000 عائد يومي لـSPY ونفّذ التفرع return > 0 مرتين، على العوائد بترتيب التواريخ وعلى العوائد نفسها بعد الفرز. الفرز لا يغيّر الأرقام بل ترتيبها فقط، لكنه يحوّل النتائج من رمي عملة إلى سلسلتين طويلتين: كل الـFalse أولًا وكل الـTrue بعدها.

def cycles(n_branches, mispredicts, penalty=PENALTY, base=BASE_CYCLES):    return base * n_branches + penalty * mispredictsdef sorted_stream(values, threshold):    return taken_sequence(sorted(values), threshold)returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:4000]for name, stream in (("unsorted", taken_sequence(returns, 0)), ("sorted", sorted_stream(returns, 0))):    wrong = two_bit_mispredicts(stream)    print(name, "| always", always_taken_mispredicts(stream), "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", wrong, "|", cycles(len(stream), wrong), "cycles")

unsorted | always 1800 | 1-bit 2035 | 2-bit 1950 | 33250 cycles
sorted | always 1800 | 1-bit 1 | 2-bit 2 | 4030 cycles

بترتيب التواريخ 2200 من 4000 عائد موجبة، فيُؤخذ التفرع 55% من الوقت ويقفز من جواب إلى آخر بلا نمط تقريبًا: «المأخوذ دائمًا» يخطئ 1800 مرة ومتنبئ البت الواحد 2035 ومتنبئ البتين 1950. المتنبئات ذات الذاكرة أسوأ حتى من التخمين البسيط لأنها تتبع كل انقلاب. وبعد الفرز تكون النتائج 1800 False يتبعها 2200 True ويخطئ متنبئ البتين مرتين فقط. تنخفض الكلفة من 33250 إلى 4030 دورة أي أقل بـ8.3 مرة بالبيانات نفسها والحلقة نفسها.

يتبع المختبر الدرس: نتائج تفرع والمتنبئات الثلاثة والكلفة بالدورات والتدفق المفروز ودراسة لعوائد SPY بترتيب التواريخ وبعد الفرز.

• الدالة · السؤالتعتمد على
• taken_sequence(values, threshold)ماذا يفعل التفرع لكل قيمة؟حساب بسيط
• always_taken_mispredicts(outcomes)كم مرة يخطئ «المأخوذ دائمًا»؟حساب بسيط
• one_bit_mispredicts(outcomes)وماذا عن متنبئ يتذكر آخر نتيجة؟حساب بسيط
• two_bit_mispredicts(outcomes)وماذا عن عدّاد مشبع؟حساب بسيط
• cycles(n_branches, mispredicts)كم يكلّف كل ذلك؟حساب بسيط
• sorted_stream(values, threshold)وماذا لو فُرزت القيم أولًا؟taken_sequence
• study(bars)كم يوفّر الفرز في SPY؟sorted_streamtwo_bit_mispredictscycles

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