تفرع (علم الحاسوب)
المحتويات
بدايةً، تفرع أو القفز أو النقل هو تعليمة في برنامج الحاسوب تُؤدي إلى بدء تنفيذ تسلسل تعليمات مختلف، وبالتالي الخروج عن سلوكه الافتراضي في تنفيذ التعليمات بالتسلسل.[أ] يُشير التفرع كذلك إلى عملية تحويل التنفيذ إلى تسلسل تعليمات مختلف نتيجةً لتنفيذ تعليمة تفرع. تُستعمل تعليمات التفرع للتحكم في تدفق البرنامج في الحلقات والشروط (أي تنفيذ تسلسل تعليمات مُحدد فقط إذا تحققت شروط مُعينة). ونتناول فيما يلي مزيدًا من التفاصيل.
وعلى صعيد آخر، يُستعمل مصطلح التفرع كذلك عند الإشارة إلى البرامج المكتوبة بلغات البرمجة عالية المستوى. وعادةً ما تتخذ التفرعات في هذه اللغات شكل تعبيرات شرطية متنوعة تُغلف تسلسل التعليمات الذي سيُنفذ عند تحقق الشروط. تُستعمل تعليمات التفرع غير المشروطة، مثل تعليمة "انتقل إلى"، للانتقال مباشرةً إلى تسلسل تعليمات مختلف. إذا كانت الخوارزمية تتطلب تفرعًا شرطيًا، فإن عبارة GOTO (أو استدعاء روتين فرعي GOSUB) تسبقها عبارة IF-THEN تُحدد الشرط (أو الشروط). تدعم جميع لغات البرمجة عالية المستوى خوارزميات تُعيد استخدام التعليمات البرمجية كحلقة تكرارية، وهي بنية تحكم تُكرر تسلسلًا من التعليمات حتى يتحقق شرط ما يُنهي الحلقة.
مشاكل الأداء مع تعليمات التفرع
إضافةً إلى ذلك، تعتمد المعالجات الحديثة على استخدام خطوط أنابيب التعليمات لتحقيق أداء عالٍ. تتكون هذه المعالجات من أجزاء متعددة بحيث يقوم كل جزء منها بمعالجة جزء من التعليمات، ثم يمرر نتائجه إلى المرحلة التالية في خط الأنابيب، ليبدأ بعدها العمل على التعليمات التالية في البرنامج. يفترض هذا التصميم أن تُنفذ التعليمات بتسلسل ثابت ومحدد. إلا أن تعليمات التفرع الشرطية تجعل من المستحيل معرفة هذا التسلسل. لذا، قد تتسبب التفرعات الشرطية في حدوث توقفات تستدعي إعادة تشغيل خط الأنابيب على جزء مختلف من البرنامج.
أمثلة
وفي السياق ذاته، يُبين الجدول التالي تعليمات التفرع أو القفز على مستوى الآلة الموجودة في الكثير من البنى الحاسوبية المعروفة:
في هذا الإطار، يكون اختصار تعليمة التفرع في لغة التجميع بحسب بنية الحاسوب عادةً اختصارًا لكلمة "قفز" أو "تفرع"، وغالبًا ما يُضاف إلى هذا الاختصار أحرف أخرى (أو مُعامل إضافي) تُشير إلى الحالة. أحيانًا تُضاف تفاصيل أخرى كذلك، مثل نطاق القفزة (حجم الإزاحة) أو نمط عنونة خاص يُستعمل لتحديد الإزاحة الفعلية.
وعلى صعيد آخر، في معالجات إكس 86، وبي دي بي-11، وفاكس، وبعض المعالجات الأخرى، يتم ضبط علامة الحمل للإشارة إلى الاستعارة، ومسحها للإشارة إلى عدم وجود استعارة. أما في المعالجات التي تعتمد على معماريات أرم، و6502، وبي آر سي. يُشار إلى هذه الوظيفة المعكوسة لعلامة الحمل في بعض اعليمات بعلامة (*)، أي أن الاستعارة تعني عدم وجود حمل في بعض أجزاء الجدول، ولكن ما لم يُذكر خلاف ذلك، فإن الاستعارة تعني وجود حمل. مع ذلك، فإن أغلب البنى المعمارية تتعامل مع الحمل في عمليات الجمع بنفس الطريقة.
تعليمة الاستدعاء
وفي هذا السياق، تُستعمل تعليمة الاستدعاء لتنفيذ الإجراءات الفرعية. وعلى غرار تعليمات القفز، فإنّ تعليمة الاستدعاء يُمكنها أن تُعدّل عداد البرنامج أو لا تُعدّله بحسب رموز الحالة، ولكن فضلًا عن ذلك، يُحفظ عنوان العودة في مكان آمن في الذاكرة (عادةً في بنية بيانات مقيمة في الذاكرة تُسمى المكدس). وعند اكتمال الروتين الفرعي، يُعاد عنوان العودة إلى عداد البرنامج، وبالتالي يستأنف تنفيذ البرنامج بالتعليمات التي تلي تعليمة الاستدعاء.
تحسين الأداء بتقليل حالات التوقف عند التفرعات
من جانب آخر، يُمكن تحسين أداء الأجهزة والمعالجات باستخدام عدة تقنيات تعتمد على تقليل حالات التوقف عند التفرعات الشرطية. ومن أشهر هذه التقنيات ما يلي:
أنواع تعليمات التفرع
وفي هذا الصدد، يُمكن تصنيف تعليمات التفرع بشكل عام اعتمادًا على كيفية تحديد عنوان تسلسل التعليمات الجديد (عنوان الهدف)، إلى:
وفي هذا السياق، تعليمات تفرع مباشرة: وهي التعليمات التي تحتوي على عنوان الهدف.
في هذا الإطار، تعليمات تفرع غير مباشرة: وهي التعليمات التي تحدد مكان وجود عنوان الهدف (مثلًا، سجل أو موقع ذاكرة).
كذلك، كذلك يمكن أن تكون تعليمة التفرع إما تعليمات تفرع غير مشروط، والذي يُؤدي دائمًا إلى حدوث التفرع، أو تعليمات تفرعًا مشروط، والذي قد يُؤدي أو لا يُؤدي إلى التفرع اعتمادًا على شرط مُعين.
وفي السياق ذاته، تعليمات تفرع نسبية: وهي التعليمات التي تحدد الفرق بين العنوان الحالي وعنوان الهدف.
تعليمة القفز
وفي السياق ذاته، تعليمة قفز مشروط: وفيها يُمكن تنفيذ التفرع أو عدم تنفيذه (أي تعديل عداد البرنامج أو عدم تعديله) بناءً على شرط معين.
كذلك، تعليمة قفز غير مشروط: وهي التي لا تحتوي شروطًا معينة لتنفيذ التفرع أو عدم تنفيذه (تعديل عداد البرنامج أو عدم تعديله).
ومن جهة أخرى، تُعد تعليمة القفز نوعًا من أنواع تعليمات التفرع على مستوى الآلة. وقد تؤدي هذه التعليمة إلى تحميل عداد البرنامج أو تعديله بقيمة جديدة مختلفة عن قيمته الأصلية (أي زيادته عن قيمة التعليمة الحالية ليشير إلى التعليمة التالية). وعادةً ما يكون لتعليمات القفز شكلان:
متنبئات التفرعات المادية
ومن جهة أخرى، نقلت متنبئات التفرعات المادية الإحصائيات إلى الدوائر الإلكترونية لتشغيل أي برنامج. تكون مُتنبئات التفرعات عبارة عن أجزاء من المعالج تُخمّن نتيجة التفرع الشرطي، ثمّ يُراهن منطق المعالج على هذا التخمين ببدء تنفيذ مسار التعليمات المتوقع. ولنأخذ مثالًا لمخطط تنبؤ تفرع بسيط في الأجهزة، وهو افتراض أن جميع التفرعات العكسية (أي إلى عداد برنامج أصغر) تُنفّذ (لأنها جزء من حلقة تكرارية)، وأن جميع التفرعات الأمامية (إلى عداد برنامج أكبر) لا تُنفّذ (لأنها تخرج من حلقة تكرارية). يتم تطوير مُتنبئات تفرع أفضل والتحقق من صحتها إحصائيًا عن طريق تشغيلها في محاكاة على مجموعة متنوعة من برامج الاختبار. عادةً ما تحسب المُتنبئات الجيدة نتائج عمليات التنفيذ السابقة للتفرع. وبالتالي، يمكن لأجهزة الحاسوب الأسرع والأكثر تكلفة أن تعمل بشكل أسرع من خلال الاستثمار في الدوائر الإلكترونية لمتنبئات تفرعات أفضل. في وحدة المعالجة المركزية المزودة بتنبؤ تفرع في الأجهزة، تسمح تلميحات التفرع لتنبؤ التفرع، الذي يُفترض أنه أفضل، بتجاوز تنبؤ التفرع الأبسط في هذه الأجهزة.
تعليمة العودة
ومن جهة أخرى، في وحدات المعالجة المركزية المزودة بسجلات الأعلام، تقوم تعليمة سابقة بتعيين شرط في سجل الأعلام. قد تكون هذه التعليمة حسابية أو منطقية، ولكنها غالبًا ما تكون قريبة من نقطة التفرع، وإن لم تكن بالضرورة التعليمة التي تسبقها مباشرةً. يُستعمل الشرط المُخزّن في تفرع مثل "القفز إذا تم تعيين علامة تجاوز السعة". تُخزّن هذه المعلومات المؤقتة عادةً في سجل الأعلام، ولكن قد توجد كذلك في مكان آخر. يكون تصميم سجل الأعلام بسيطًا في الحواسيب البطيئة والبسيطة. أما في الحواسيب السريعة، فقد يُشكّل سجل الأعلام عائقًا أمام السرعة، لأن التعليمات التي يُمكنها العمل بالتوازي (في عدة وحدات تنفيذ) تحتاج إلى تعيين بتات الأعلام بتسلسل مُحدد. توجد كذلك أجهزة (أو تعليمات مُحددة) حيث يُمكن التحقق من الشرط بواسطة تعليمة القفز نفسها، مثل "التفرع <التسمية> إذا كان السجل X سالبًا". تُنفّذ تفرعات المقارنة في الحواسيب ذات التصميمات البسيطة عمليات حسابية أكثر، وقد تستهلك طاقة أكبر من تفرعات سجل الأعلام. أما في الحواسيب ذات التصميمات السريعة، فيُمكن لتفرعات المقارنة أن تعمل بصورة أسرع من تفرعات سجل الأعلام، لأنها تستطيع الوصول إلى السجلات بتوازي أكبر، باستخدام آليات وحدة المعالجة المركزية نفسها المُستعملة في الحوسبة. تُنفّذ بعض معماريات وحدات المعالجة المركزية المبكرة الموجهة نحو الكلمات عمليات "تجاوز التعليمات التالية" المشروطة بناءً على نتائج المقارنة. بينما قد لا تُنفّذ بعض معماريات وحدات المعالجة المركزية البسيطة، التي لا تزال موجودة في المتحكمات الدقيقة، القفز المشروط، بل تُنفّذ فقط عمليات التجاوز والقفز غير المشروط. وبالتالي، يُنفّذ القفز أو الاستدعاء المشروط كتجاوز مشروط للقفز أو الاستدعاء غير المشروط.
كذلك، تقوم هذه التعليمة بسحب عنوان العودة من المكدس وتحميله في سجل عداد البرنامج، مما يُعيد التحكم إلى الروتين المُستدعي. يمكن كذلك تنفيذ تعليمات العودة بشكل مشروط. ينطبق هذا الوصف على الممارسة الشائعة؛ ومع ذلك، يتمتع مُبرمج الآلة بصلاحيات واسعة للتلاعب بعنوان العودة في المكدس، وبالتالي إعادة توجيه تنفيذ البرنامج بعدة طرق مختلفة.
ومن ناحية أخرى، قد تُغيّر تعليمات القفز والاستدعاء محتويات سجل عداد البرنامج بطرق مختلفة اعتمادًا على المُعالج. فمثلًا، قد يتم تحميل عنوان مطلق، أو قد تُضاف قيمة (أو إزاحة) إلى محتويات عداد البرنامج الحالية أو تُطرح منها، مما يجعل عنوان الوجهة نسبيًا للموقع الحالي في البرنامج. كذلك قد يختلف مصدر قيمة الإزاحة، كأن تكون قيمة فورية مضمنة في التعليمة، أو محتويات سجل المعالج أو موقع الذاكرة، أو محتويات موقع ما مضافًا إليها قيمة فهرس. تُعتبر الحلقات التكرارية كذلك من تعليمات التفرع. على مستوى الآلة، حيث تُنفذ الحلقات التكرارية كقفزات شرطية عادية تُعيد توجيه التنفيذ إلى التعليمات البرمجية المتكررة.
تلميحات التنبؤ بالتفرعات
وفي السياق ذاته، اعتمد التنبؤ بالتفرعات تاريخيًا على الإحصائيات، والتي استعمل نتائجها لتحسين النص البرمجي. كان المبرمج يُجمّع نسخة تجريبية من البرنامج، ويُشغّلها ببيانات اختبارية بحيث يحسب النص البرمجي التجريبي عدد مرات تنفيذ التفرعات. ثم يستعمل المُجمّع الإحصائيات المُستخرجة من النص البرمجي التجريبي لتحسين تفرعات النص البرمجي النهائي. يضمن التحسين أن يكون مسار التفرع الأسرع (سواءً نُفّذ أم لا) هو مسار التحكم الأكثر استخدامًا. ولتحقيق ذلك، يجب تصميم وحدات المعالجة المركزية بتوقيت تفرعات قابل للتنبؤ (أو على الأقل أن يكون لها توقيت تفرعات قابل للتنبؤ). تحتوي بعض وحدات المعالجة المركزية على مجموعات تعليمات مصممة بـتلميحات تفرع تُمكّن المُجمّع من إخبار وحدة المعالجة المركزية بكيفية تنفيذ كل تفرع. تكمن مشكلة التنبؤ بالتفرعات في البرمجيات في أنها تتطلب عملية تطوير برمجيات معقدة.
نص برمجي بلا تفرعات
علاوةً على ذلك، يمكن كتابة بعض النصوص البرمجية بلا تفرعات أو بتفرعات أقل، وغلبًا ما يُمكن عمل ذلك من خلال استخدام عمليات على مستوى البت، أو عمليات نقل شرطية، أو تنبؤات أخرى عوضًا عن التفرعات. يعد النص البرمجي الخالي من التفرعات في الواقع أمرًا ضروريًا عند التشفير للحد من هجمات التوقيت.
التنفيذ
ومن ناحية أخرى، تستطيع تعليمات التفرع تغيير محتويات عداد البرنامج في وحدة المعالجة المركزية (أو مؤشر التعليمات في معالجات إنتل). يحتفظ عداد البرنامج بعنوان الذاكرة للتعليمات التالية التي سيتم جلبها وتنفيذها. لذا، عند تنفيذ التفرع، تُجبر وحدة المعالجة المركزية على تنفيذ التعليمات البرمجية من عنوان ذاكرة جديد، مما يُغير منطق البرنامج بحسب الخوارزمية التي وضعها المبرمج.
خانة التأخير
من جانب آخر، في تقنية خانة تأخير التفرع يتم تنفيذ تعليمة واحدة على الأقل تلي التفرع دائمًا، مع بعض الاستثناءات مثل تعليمة التفرع المحتملة/غير المحتملة في معمارية ميبس القديمة. بالتالي، يمكن للحاسوب استخدام هذه التعليمة لإنجاز مهام مفيدة سواءً توقف خط الأنابيب أم لا. كانت هذه الطريقة شائعة تاريخيًا في الأجهزة التي اعتمدت على الحوسبة بمجموعة تعليمات مخفضة. في عائلة من وحدات المعالجة المركزية المتوافقة، تُعقّد هذه الطريقة عمل وحدات المعالجة المركزية متعددة الدورات (بدون خط أنابيب)، ووحدات المعالجة المركزية الأسرع ذات خطوط الأنابيب الأطول من المتوقع، ووحدات المعالجة المركزية فائقة التوازي (التي يمكنها تنفيذ التعليمات خارج الترتيب).
التفرع على مستوى الآلة
- تنقسم أنواع تعليمات التفرع على مستوى الآلة إلى ما يلي:
- تعليمة القفز
- تعليمة الاستدعاء
- تعليمة العودة
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟