java لماذا هو أسرع لمعالجة صف مصنفة من صفيف لم يتم فرزها؟





10 Answers

التنبؤ فرع.

باستخدام الصفيف الذي تم فرزه ، تكون data[c] >= 128 الشرط data[c] >= 128 false لأول مرة لسلسلة من القيم ، ثم تصبح true لكل القيم الأحدث. هذا من السهل التنبؤ به. مع مجموعة غير مجزأة ، تدفعه مقابل تكلفة المتفرعة.

java c++ performance optimization branch-prediction

هنا هو قطعة من رمز C ++ التي تبدو غريبة جدا. لسبب غريب ، يؤدي ترتيب البيانات إلى جعل الشفرة أسرع بمعدل ست مرات.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • بدون std::sort(data, data + arraySize); ، يعمل الرمز في 11.54 ثانية.
  • مع البيانات التي تم فرزها ، يتم تشغيل التعليمات البرمجية في 1.93 ثانية.

في البداية ، اعتقدت أن هذا قد يكون مجرد لغة أو مترجم شاذ. لذلك حاولت في جافا.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

مع نتيجة مشابهة إلى حد ما ولكن أقل تطرفا.

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

  • ما الذي يجري؟
  • لماذا هو أسرع لمعالجة صف مصنفة من صفيف لم يتم فرزها؟
  • تلخص الشفرة بعض المصطلحات المستقلة ، ويجب ألا يهم الأمر.



إذا كنت تشعر بالفضول بشأن المزيد من التحسينات التي يمكن القيام بها لهذا الرمز ، ففكر في هذا:

بدءا من الحلقة الأصلية:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

من خلال تبادل الحلقات ، يمكننا تغيير هذه الحلقة بأمان:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

ثم ، يمكنك أن ترى أن الشرطية if ثابتة طوال تنفيذ حلقة i ، حتى يمكنك رفع if الخروج:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

ثم ، سترى أنه يمكن طي الحلقة الداخلية في تعبير واحد ، على افتراض أن نموذج النقطة العائمة يسمح بذلك (/ fp: يتم طرح سريع ، على سبيل المثال)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

هذا واحد هو 100000x أسرع من ذي قبل




لقد قرأت للتو عن هذا السؤال وأجوبته ، وأشعر أن هناك إجابة مفقودة.

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

يعمل هذا النهج بشكل عام إذا:

  1. إنها طاولة صغيرة ومن المحتمل تخزينها مؤقتًا في المعالج
  2. أنت تقوم بتشغيل الأشياء في حلقة ضيقة جدًا و / أو يمكن للمعالج تحميل البيانات مسبقًا

الخلفية ولماذا

ما هذا الجحيم الذي من المفترض أن يعني؟

من منظور المعالج ، تكون الذاكرة بطيئة. للتعويض عن الاختلاف في السرعة ، فإنها تقوم ببناء مخابئ في المعالج (L1 / L2 cache) لتعويض ذلك. لذا تخيل أنك تقوم بحساباتك الحسنة وتكتشف أنك بحاجة إلى جزء من الذاكرة. سيحصل المعالج على عملية "التحميل" ويحمّل قطعة الذاكرة في ذاكرة التخزين المؤقت - ثم يستخدم ذاكرة التخزين المؤقت لإجراء بقية العمليات الحسابية. نظرًا لأن الذاكرة بطيئة نسبيًا ، سيؤدي هذا "التحميل" إلى إبطاء البرنامج.

مثل التنبؤ بالفرع ، تم تحسين ذلك في معالجات Pentium: يتوقع المعالج أنه يحتاج إلى تحميل جزء من البيانات ويحاول تحميله في ذاكرة التخزين المؤقت قبل أن تضرب العملية فعليًا ذاكرة التخزين المؤقت. كما رأينا سابقاً ، فإن التنبؤ بالفروع يذهب أحياناً بشكل خاطئ - في أسوأ الحالات ، تحتاج إلى العودة والانتظار فعليًا لحمل ذاكرة ، والذي سيستغرق إلى الأبد ( وبعبارة أخرى: فشل التنبؤ بالفرع هو سيئ ، ذاكرة تحميل بعد فشل فرع التنبؤ هو مجرد الرهيبة! ).

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

أول شيء نحتاج إلى معرفته هو ما هو صغير ؟ بينما يكون الأصغر بشكل عام أفضل ، فإن القاعدة الأساسية هي الالتصاق بجداول البحث التي تبلغ <= 4096 بايت في الحجم. كحد أعلى: إذا كان جدول البحث أكبر من 64 كيلو بايت ، فربما يستحق الأمر إعادة النظر.

بناء طاولة

لذلك اكتشفنا أنه يمكننا إنشاء طاولة صغيرة. والشيء التالي الذي يجب عمله هو الحصول على وظيفة البحث في مكانها. دالات البحث عادة ما تكون وظائف صغيرة تستخدم زوجين من العمليات الأساسية الأساسية (و ، أو ، xor ، shift ، add ، remove و might multiply). إذا كنت تريد أن تتم ترجمة إدخالك من خلال وظيفة البحث إلى نوع من "المفتاح الفريد" في الجدول الخاص بك ، فهذا يعني ببساطة أنه يوفر لك الإجابة عن كل الأعمال التي تريد أن تقوم بها.

في هذه الحالة:> = 128 يعني أنه يمكننا الاحتفاظ بالقيمة ، يعني <128> أننا نتخلص منها. أسهل طريقة للقيام بذلك هي استخدام "AND": إذا احتفظنا بها ، فإننا نحن و 7 CFFFFFF ؛ إذا أردنا التخلص منه ، ونحن مع 0. لاحظ أيضا أن 128 هي قوة 2 - حتى نتمكن من المضي قدما وجعل جدول من 32768/128 الأعداد الصحيحة وملئه مع صفر واحد والكثير من و7FFFFFFFF.

اللغات المدارة

قد تتساءل لماذا يعمل هذا بشكل جيد في اللغات المدارة. بعد كل شيء ، تحقق اللغات المدارة من حدود المصفوفات مع فرع لضمان عدم العبث ...

حسنا ، ليس بالضبط ... :-)

كان هناك بعض العمل على القضاء على هذا الفرع للغات المدارة. فمثلا:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

في هذه الحالة ، من الواضح أن المحول البرمجي لن يتم ضرب شرط الحدود. على الأقل مترجم Microsoft JIT (ولكن أتوقع Java يفعل أشياء مشابهة) سوف تلاحظ هذا وإزالة الاختيار تماما. نجاح باهر - وهذا يعني عدم وجود فرع. وبالمثل ، فإنه سيتناول الحالات الواضحة الأخرى.

إذا واجهت مشكلة مع عمليات البحث في اللغات التي تتم إدارتها - فالمفتاح هو إضافة علامة & 0x[something]FFF إلى وظيفة البحث الخاصة بك لجعل التحقق الحد المتوقع - ومشاهدته تسير بشكل أسرع.

نتيجة هذه القضية

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();



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

لكن في هذه الحالة ، نعرف أن القيم في النطاق [0 ، 255] ونحن نهتم فقط بالقيم> = 128. وهذا يعني أنه يمكننا بسهولة استخراج بت واحد يخبرنا ما إذا كنا نريد قيمة أم لا: عن طريق التحول البيانات إلى اليمين 7 بت ، نحن مع ترك بت 0 أو 1 بت ، ونحن نريد فقط إضافة القيمة عندما يكون لدينا 1 بت. دعونا نسمي هذا بت "قرار البت".

باستخدام قيمة 0/1 من بت القرار كمؤشر في صفيف ، يمكننا أن نجعل التعليمات البرمجية التي ستكون بنفس السرعة إذا تم فرز البيانات أو لا يتم فرزها. سيضيف رمزنا دائمًا قيمة ، ولكن عندما تكون بتة القرار هي 0 ، سنضيف القيمة إلى مكان لا نهتم به. هنا الرمز:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

هذا التعليمة البرمجية تهدر نصف عدد المرات ، ولكن لا يوجد به أي فشل في التنبؤ بالفرع. انها أسرع بشكل كبير على البيانات العشوائية من الإصدار مع بيان if الفعلي.

ولكن في الاختبار الخاص بي ، كان جدول البحث السريع أسرع قليلاً من هذا ، ربما بسبب الفهرسة في جدول البحث كان أسرع قليلاً من نقل بت. يوضح هذا كيفية إعداد التعليمة البرمجية الخاصة بي واستخدامها في جدول البحث (يسمى بشكل غير lutمتوقع "LookUp Table" في التعليمات البرمجية). إليك رمز C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

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

تحرير: شيء واحد نسيت أن تضع فيه.

يمكن استخدام تقنية الفهرسة في مصفوفة ، بدلاً من استخدام ifعبارة ، لتحديد أي مؤشر لاستخدامه. رأيت المكتبة التي نفذت شجرة ثنائية، وبدلا من وجود اثنين من المؤشرات المسماة ( pLeftو pRightأو أيا كان) كان مجموعة طول 2 من مؤشرات واستخدام تقنية "قرار قليلا" لاتخاذ قرار واحد لمتابعة. على سبيل المثال ، بدلاً من:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

هذه المكتبة ستفعل شيئًا مثل:

i = (x < node->value);
node = node->link[i];

إليك رابط لهذا الرمز: Red Black Trees ، Confluzzled عبر الزمن




السلوك أعلاه يحدث بسبب التنبؤ فرع.

لفهم التنبؤ بالفرع يجب على المرء أولاً فهم خط أنابيب التعليمات :

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

عموما ، المعالجات الحديثة لديها خطوط أنابيب طويلة جدا ، ولكن لسهولة دعونا ننظر في هذه الخطوات الأربع فقط.

  1. IF - جلب التعليمات من الذاكرة
  2. معرف - فك التعليمات
  3. EX - تنفيذ التعليمات
  4. WB - اكتب إلى سجل وحدة المعالجة المركزية

خط أنابيب من 4 مراحل بصفة عامة لتعليمتين.

بالرجوع إلى السؤال أعلاه دعنا نفكر في الإرشادات التالية:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

دون التنبؤ فرع ، سيحدث ما يلي:

لتنفيذ التعليمة B أو التعليمة C ، يجب على المعالج الانتظار حتى لا يصل التعليمة A إلى مرحلة EX في خط الأنابيب ، لأن قرار الانتقال إلى B أو التعليمة C يعتمد على نتيجة التعليمة A. لذا فإن خط الأنابيب سيبدو هكذا.

عندما يعود الشرط صحيحا:

في حالة إرجاع حالة false:

كنتيجة لانتظار نتيجة التعليمة A ، فإن إجمالي دورات CPU التي يتم قضاؤها في الحالة أعلاه (بدون توقع فرع ، لكل من true و false) هي 7.

إذن ما هو التنبؤ فرع؟

سوف يحاول متنبئ الفرع تخمين الطريقة التي سيذهب بها الفرع (وهو هيكل إذا كان ثم آخر) قبل أن يكون هذا معروفًا على وجه اليقين. لن تنتظر التعليمة A للوصول إلى مرحلة EX من خط الأنابيب ، ولكنها ستخمن القرار وتذهب إلى تلك التعليمات (B أو C في حالة مثالنا).

في حالة وجود تخمين صحيح ، فإن خط الأنابيب يبدو كالتالي:

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

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

  1. جميع العناصر أقل من 128
  2. جميع العناصر أكبر من 128
  3. بعض عناصر البدء الجديدة أقل من 128 ثم تصبح أكبر من 128

دعونا نفترض أن المتنبئ سوف يفترض دائما الفرع الحقيقي في الجولة الأولى.

لذلك في الحالة الأولى ، ستأخذ دائماً الفرع الحقيقي لأن جميع تنبؤاتها صحيحة تاريخياً. في الحالة الثانية ، سوف يتنبأ بشكل خاطئ في البداية ، ولكن بعد بضعة تكرارات ، سوف يتنبأ بشكل صحيح. في الحالة الثالثة ، سوف يتنبأ في البداية بشكل صحيح حتى تكون العناصر أقل من 128. وبعد ذلك ستفشل لبعض الوقت وتصحيح نفسها عندما ترى فشل توقع الفرع في التاريخ.

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

ولكن في حالة وجود مصفوفة عشوائية غير مجزأة ، سيحتاج التنبؤ إلى تجاهل التعليمات المنفذة جزئياً والبدء من جديد مع الفرع الصحيح في معظم الوقت وينتج المزيد من دورات CPU مقارنة بالصفيف الذي تم فرزه.




في نفس السطر (أعتقد أن هذا لم يتم إبرازه بأي إجابة) من الجيد أن نذكر أنه في بعض الأحيان (خاصة في البرامج التي يكون فيها الأداء مهمًا - كما في Linux kernel) ، يمكنك العثور على بعض العبارات إذا كانت كالتالي:

if (likely( everything_is_ok ))
{
    /* Do something */
}

أو بالمثل:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

كلا likely()و unlikely()هي في وحدات الماكرو الحقيقة التي تم تعريفها باستخدام شيء من هذا القبيل في دول مجلس التعاون الخليجي __builtin_expectلمساعدة المترجم رمز إدراج التنبؤ لصالح حالة مع الأخذ بعين الاعتبار المعلومات المقدمة من قبل المستخدم. تدعم دول مجلس التعاون الخليجي بنى أخرى يمكن أن تغير سلوك البرنامج الجاري أو تصدر تعليمات منخفضة المستوى مثل مسح ذاكرة التخزين المؤقت ، وما إلى ذلك. انظر هذه الوثائق التي تمر من خلال مواطني دول مجلس التعاون الخليجي المتاحة.

عادةً ما يتم العثور على هذا النوع من التحسينات بشكل أساسي في التطبيقات ذات الوقت الفعلي أو الأنظمة المضمنة حيث يكون وقت التنفيذ أمرًا هامًا. على سبيل المثال ، إذا كنت تبحث عن بعض حالات الخطأ التي تحدث فقط في الأوقات 1/10000000 ، فلماذا لا تخبر المترجم بهذا؟ بهذه الطريقة ، افتراضياً ، سيفترض توقع الفرع أن الشرط خاطئ.




بالتأكيد!...

يجعل توقع الفرع المنطقي أبطأ ، بسبب التبديل الذي يحدث في التعليمات البرمجية الخاصة بك! انها مثل كنت تسير في الشارع المستقيم أو الشارع مع الكثير من الخراطة ، وبالتأكيد سوف يتم القيام به بشكل مستقيم! ...

إذا تم فرز المصفوفة ، تكون حالتك خاطئة في الخطوة الأولى: data[c] >= 128، ثم تصبح قيمة حقيقية للطريق كله إلى نهاية الشارع. هكذا تصل إلى نهاية المنطق بشكل أسرع. من ناحية أخرى ، باستخدام مصفوفة لم يتم فرزها ، تحتاج إلى الكثير من الدوران والمعالجة مما يجعل تشغيل الكود أبطأ بالتأكيد ...

انظر إلى الصورة التي أنشأتها لك أدناه. أي شارع سينتهي بشكل أسرع؟

لذلك برمجيا ، يسبب التنبؤ الفرعى أن تكون العملية أبطأ ...

أيضًا في النهاية ، من الجيد أن نعرف أن لدينا نوعين من تنبؤات الفروع التي سيؤثر كل منها على شفرتك بشكل مختلف:

1. ثابت

2. ديناميكية

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

من أجل كتابة التعليمات البرمجية الخاصة بك بشكل فعال للاستفادة من هذه القواعد ، عند كتابة if-else أو عبارات التبديل ، قم بفحص الحالات الأكثر شيوعًا أولاً ثم قم بالعمل تدريجيا إلى الأقل شيوعًا. لا تتطلب الحلقات بالضرورة أي طلب خاص من التعليمات البرمجية للتنبؤ الفرعى الثابت ، حيث يتم استخدام حالة تكرار الحلقة فقط عادة.




كسب التنبؤ الفروع!

من المهم أن نفهم أن سوء فهم الفرع لا يبطئ البرامج. إن تكلفة التنبؤ الفائت هي كما لو أن التوقع الفرعي لم يكن موجودًا وانتظرت تقييم التعبير لتحديد الكود المطلوب تشغيله (مزيد من الشرح في الفقرة التالية).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

عندما يكون هناك عبارة if-else\ switchstatement ، يجب تقييم التعبير لتحديد الكتلة المطلوب تنفيذها. في رمز التجميع الذي تم إنشاؤه بواسطة المحول البرمجي ، يتم إدراج تعليمات branch الشرطي .

يمكن أن يتسبب تعليمة الفروع في أن يبدأ الكمبيوتر في تنفيذ تسلسل تعليمي مختلف ، ومن ثم ينحرف عن سلوكه الافتراضي لتنفيذ التعليمات بالترتيب (أي إذا كان التعبير خاطئًا ، يتخطى البرنامج شفرة ifالكتلة) بناءً على بعض الشروط ، تقييم التعبير في حالتنا.

ومع ذلك ، يحاول المترجم التنبؤ بالنتيجة قبل تقييمها فعليًا. وسوف تجلب التعليمات من ifالكتلة ، وإذا تبين أن التعبير صحيح ، ثم رائع! لقد حصلنا على الوقت الذي استغرقته لتقييمه وإحراز تقدم في الشفرة ؛ إذا لم يكن الأمر كذلك فإننا ندير الكود الخاطئ ، يتم مسح خط الأنابيب ، ويتم تشغيل الكتلة الصحيحة.

التصور:

لنفترض أنك بحاجة إلى اختيار الطريق 1 أو الطريق 2. في انتظار التحقق من الشريك للخريطة ، توقفت عند ## وانتظرت ، أو يمكنك فقط اختيار الطريق 1 وإذا كنت محظوظًا (الطريق 1 هو المسار الصحيح) ، عندئذٍ لم تكن مضطرًا إلى الانتظار حتى يتحقق شريكك من الخريطة (التي قمت بحفظ الوقت الذي كان سيأخذها إليه للتحقق من الخريطة) ، وإلا فإنك ستعود إلى الخلف.

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------



انها عن التنبؤ فرع. ما هذا؟

  • يعتبر متنبئ الفرع أحد تقنيات تحسين الأداء القديمة التي لا تزال تجد أهمية في معماريات حديثة. في حين أن تقنيات التنبؤ البسيطة توفر بحثًا سريعًا وكفاءة في استهلاك الطاقة ، فإنها تعاني من نسبة عالية من الخطأ في التنبؤ.

  • من ناحية أخرى ، فإن التنبؤات المعقدة للفرع ، سواء كانت قائمة على أساس جيني أو متغيرات من التنبؤ ذي الفروع على مستويين ، توفر دقة أفضل للتنبؤ ، ولكنها تستهلك المزيد من القوة والتعقيد وتزداد أضعافا مضاعفة.

  • بالإضافة إلى ذلك ، في تقنيات التنبؤ المعقدة ، فإن الوقت المستغرق للتنبؤ بالفروع يكون في حد ذاته مرتفعًا جدًا من 2 إلى 5 دورات - وهو ما يقارن بوقت تنفيذ الفروع الفعلية.

  • يعتبر توقع الفروع أساسًا مشكلة تحسين (تقليل) حيث يتم التركيز على تحقيق أقل معدل ممكن للفشل ، وانخفاض استهلاك الطاقة ، وانخفاض التعقيد مع الحد الأدنى من الموارد.

هناك بالفعل ثلاثة أنواع مختلفة من الفروع:

الفروع المشروطة إلى الأمام - استناداً إلى شرط وقت التشغيل ، يتم تغيير الكمبيوتر (عداد البرنامج) للإشارة إلى عنوان إلى الأمام في دفق التعليمات.

الفروع المشروطة المتخلفة - يتم تغيير جهاز الكمبيوتر ليشير إلى الخلف في تيار التعليمات. يعتمد الفرع على بعض الشروط ، مثل التفرع إلى بداية حلقة البرنامج عندما ينص اختبار في نهاية الحلقة على أنه يجب تنفيذ الحلقة مرة أخرى.

الفروع غير المشروطة - وهذا يشمل القفزات ومكالمات الإجراء والعائدات التي ليس لها شرط محدد. على سبيل المثال ، قد يتم ترميز تعليمة قفزة غير مشروطة في لغة التجميع بأنها "jmp" ، ويجب توجيه تيار التعليمات على الفور إلى الموقع المستهدف المشار إليه بواسطة تعليمات القفزة ، في حين أن القفزة المشروطة التي قد يتم ترميزها بأنها "jmpne" إعادة توجيه دفق التوجيه فقط إذا أظهرت نتيجة مقارنة بين قيمتين في إرشادات "مقارنة" سابقة أن القيم غير متساوية. (يضيف نظام العنونة المجزأ المستخدم من قبل بنية x86 تعقيدات إضافية ، حيث يمكن أن تكون القفزات إما "قريبة" (داخل مقطع) أو "بعيد" (خارج المقطع). لكل نوع تأثيرات مختلفة على خوارزميات التنبؤ الفرعية.)

توقع فرع ثابت / ديناميكي : يتم استخدام التنبؤ الفرعى الثابت من قبل المعالجات الدقيقة في المرة الأولى التي يتم فيها مواجهة الفرع الشرطي ، ويتم استخدام التنبؤ الديناميكي للفرع في عمليات التنفيذ التالية لرمز الفرع الشرطي.

المراجع:




إلى جانب حقيقة أن توقع الفرع قد يبطئك ، فإن مصفوفة الفرز لها ميزة أخرى:

يمكن أن يكون لديك شرط إيقاف بدلاً من مجرد التحقق من القيمة ، وبهذه الطريقة تقوم فقط بحل البيانات ذات الصلة ، وتجاهل الباقي.
سوف تفوت التنبؤ فرع مرة واحدة فقط.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }



Related