فرع (علوم الحاسوب)
التفرع أو القفز أو النقل هو تعليمة في برنامج الحاسوب تُمكن الحاسوب من بدء تنفيذ تسلسل تعليمات مختلف، وبالتالي الخروج عن سلوكه الافتراضي المتمثل في تنفيذ التعليمات بالتسلسل. [ أ ] قد يشير التفرع (أو التفرع ، أو المتفرع ) أيضًا إلى عملية تحويل التنفيذ إلى تسلسل تعليمات مختلف نتيجةً لتنفيذ تعليمة التفرع. تُستخدم تعليمات التفرع لتنفيذ التحكم في تدفق البرنامج في الحلقات والشروط (أي تنفيذ تسلسل معين من التعليمات فقط إذا تحققت شروط معينة).
يمكن أن تكون تعليمة التفرع إما تفرعًا غير مشروط ، والذي يؤدي دائمًا إلى التفرع، أو تفرعًا مشروطًا ، والذي قد يؤدي أو لا يؤدي إلى التفرع بناءً على شرط معين. كما تُصنف تعليمة التفرع عمومًا إلى مباشرة أو غير مباشرة أو نسبية ، وذلك بحسب كيفية تحديدها لعنوان تسلسل التعليمات الجديد (عنوان "الهدف"). بمعنى أن التعليمة تحتوي على عنوان الهدف، أو تحدد مكان وجود عنوان الهدف (مثل سجل أو موقع في الذاكرة)، أو تحدد الفرق بين العنوان الحالي وعنوان الهدف.
تطبيق
تستطيع تعليمات التفرع تغيير محتويات عداد البرنامج (PC) الخاص بوحدة المعالجة المركزية (أو مؤشر التعليمات في معالجات إنتل). يحتفظ عداد البرنامج بعنوان الذاكرة الخاص بتعليمات الآلة التالية التي سيتم جلبها وتنفيذها. وبالتالي، يؤدي تنفيذ التفرع إلى قيام وحدة المعالجة المركزية بتنفيذ التعليمات البرمجية من عنوان ذاكرة جديد، مما يغير منطق البرنامج وفقًا للخوارزمية التي خطط لها المبرمج.
أحد أنواع التفرعات على مستوى الآلة هو تعليمة القفز . قد تؤدي هذه التعليمة إلى تحميل أو تعديل عداد البرنامج (PC) بقيمة جديدة مختلفة عن قيمته الأصلية (أي زيادة قيمته بعد التعليمة الحالية للإشارة إلى التعليمة التالية). تتخذ تعليمة القفز عادةً شكلين: غير مشروط ومشروط، حيث يُنفذ الشكل المشروط أو لا يُنفذ (أي لا يُعدل عداد البرنامج) بناءً على شرط معين.
النوع الثاني من التفرعات على مستوى الآلة هو تعليمة الاستدعاء، والتي تُستخدم لتنفيذ الإجراءات الفرعية . وكما هو الحال في تعليمات القفز، قد تُعدّل الاستدعاءات عداد البرنامج (PC) أو لا تُعدّله وفقًا لرموز الحالة، ولكن بالإضافة إلى ذلك، يتم حفظ عنوان العودة في مكان آمن في الذاكرة (عادةً في بنية بيانات مقيمة في الذاكرة تُسمى المكدس ). عند اكتمال الإجراء الفرعي، يُعاد عنوان العودة هذا إلى عداد البرنامج، وبالتالي يستأنف تنفيذ البرنامج بالتعليمة التي تلي تعليمة الاستدعاء.
النوع الثالث من التفرعات على مستوى الآلة هو تعليمة الإرجاع . تقوم هذه التعليمة بسحب عنوان الإرجاع من المكدس وتحميله في سجل عداد البرنامج، مما يعيد التحكم إلى الروتين المُستدعي. يمكن أيضًا تنفيذ تعليمات الإرجاع بشكل مشروط. ينطبق هذا الوصف على الممارسة الشائعة؛ ومع ذلك، يتمتع مبرمج الآلة بصلاحيات واسعة للتلاعب بعنوان الإرجاع في المكدس، وبالتالي إعادة توجيه تنفيذ البرنامج بطرق متعددة.
بحسب المعالج، قد تُغيّر تعليمات القفز والاستدعاء محتويات سجل عداد البرنامج (PC) بطرق مختلفة. فقد يتم تحميل عنوان مطلق، أو قد تُضاف قيمة (أو إزاحة) إلى محتويات عداد البرنامج الحالية أو تُطرح منها، مما يجعل عنوان الوجهة نسبيًا للموقع الحالي في البرنامج. وقد يختلف مصدر قيمة الإزاحة، كقيمة فورية مضمنة في التعليمة، أو محتويات سجل المعالج أو موقع الذاكرة، أو محتويات موقع ما مضافًا إليها قيمة فهرس.
يُستخدم مصطلح "التفرع" أيضًا عند الإشارة إلى البرامج المكتوبة بلغات البرمجة عالية المستوى . في هذه اللغات، عادةً ما تتخذ التفرعات شكل عبارات شرطية متنوعة تُغلف تسلسل التعليمات الذي سيتم تنفيذه عند تحقق الشروط. تُستخدم تعليمات التفرع غير المشروطة، مثل GOTO، للانتقال مباشرةً إلى تسلسل تعليمات مختلف. إذا كانت الخوارزمية تتطلب تفرعًا شرطيًا، فإن عبارة GOTO (أو استدعاء روتين فرعي GOSUB) تسبقها عبارة IF-THEN تُحدد الشرط (أو الشروط). تدعم جميع لغات البرمجة عالية المستوى خوارزميات تُعيد استخدام التعليمات البرمجية كحلقة تكرارية ، وهي بنية تحكم تُكرر تسلسلًا من التعليمات حتى يتحقق شرط ما يُؤدي إلى إنهاء الحلقة. تُعتبر الحلقات التكرارية أيضًا من تعليمات التفرع. على مستوى الآلة، تُنفذ الحلقات التكرارية كقفزات شرطية عادية تُعيد توجيه التنفيذ إلى التعليمات البرمجية المُكررة.
في وحدات المعالجة المركزية المزودة بسجلات علامات ، تقوم تعليمة سابقة بتعيين شرط في سجل العلامات. قد تكون هذه التعليمة حسابية أو منطقية ، وغالبًا ما تكون قريبة من نقطة التفرع، وإن لم تكن بالضرورة التعليمة التي تسبقها مباشرةً . يُستخدم الشرط المُخزّن في نقطة تفرع، مثل " القفز إذا تم تعيين علامة تجاوز السعة" . تُخزّن هذه المعلومات المؤقتة عادةً في سجل العلامات، ولكن قد تُخزّن في مكان آخر. تصميم سجل العلامات بسيط في الحواسيب البطيئة والبسيطة. أما في الحواسيب السريعة، فقد يُشكّل سجل العلامات عائقًا أمام السرعة، لأن التعليمات التي يُمكن تنفيذها بالتوازي (في عدة وحدات تنفيذ ) تحتاج إلى تعيين بتات العلامات بتسلسل مُحدد.
توجد أيضًا آلات (أو تعليمات محددة) حيث يمكن التحقق من الشرط بواسطة تعليمة القفز نفسها، مثل: `branch <label> if register X negative` . في تصميمات الحواسيب البسيطة، تُنفذ فروع المقارنة عمليات حسابية أكثر وقد تستهلك طاقة أكبر من فروع سجلات العلامات. أما في تصميمات الحواسيب السريعة، فيمكن أن تعمل فروع المقارنة بشكل أسرع من فروع سجلات العلامات، لأنها تستطيع الوصول إلى السجلات بتوازي أكبر، باستخدام آليات وحدة المعالجة المركزية نفسها المستخدمة في الحساب.
تُنفّذ بعض معماريات وحدات المعالجة المركزية المبكرة الموجهة نحو الكلمات [ ب ] عمليات "تجاوز التعليمات التالية" المشروطة، حيث تنتقل إلى NSI أو NSI+1 أو NSI+2 (PC+1، PC+2، PC+3) بناءً على نتائج المقارنة. قد لا تُنفّذ بعض معماريات وحدات المعالجة المركزية البسيطة، التي لا تزال موجودة في المتحكمات الدقيقة، القفز المشروط، بل تُنفّذ فقط عمليات التجاوز والقفز غير المشروط. وبالتالي، يُنفّذ القفز أو الاستدعاء المشروط كتجاوز مشروط لتعليمات القفز أو الاستدعاء غير المشروط.
أمثلة
بحسب بنية الحاسوب ، يكون اختصار تعليمة القفز في لغة التجميع عادةً شكلاً مختصراً من كلمة " قفز" أو كلمة " تفرع" ، مصحوباً غالباً بأحرف أخرى (أو مُعامل إضافي) تُشير إلى الحالة. أحياناً تُضاف تفاصيل أخرى أيضاً، مثل نطاق القفزة (حجم الإزاحة) أو نمط عنونة خاص يُستخدم لتحديد الإزاحة الفعلية.
يسرد هذا الجدول تعليمات التفرع أو القفز على مستوى الآلة الموجودة في العديد من البنى المعروفة:
| الشرط أو النتيجة | x86 | PDP-11، VAX | ARM (جزئياً 6502) | معادلة |
|---|---|---|---|---|
| الصفر (يعني التساوي في عملية الطرح/المقارنة) | JZ؛ JNZ | BEQ; BNE | BEQ; BNE | صفر؛ ليس صفراً |
| سالب (N)، إشارة (S)، أو ناقص (M) | JS; JNS | مؤشر كتلة الجسم؛ مستوى خط الأساس | مؤشر كتلة الجسم؛ مستوى خط الأساس | سلبي؛ ليس سلبياً |
| تجاوز الحساب (علامة تسمى O أو V) | JO; JNO | بي في إس؛ بي في سي | بي في إس؛ بي في سي | تجاوز؛ ليس تجاوز |
| الحمل (من الجمع، المقارنة، التحويل، إلخ) | JC؛ JNC | BCS؛ BCC | BCS؛ BCC | يحمل؛ لا يحمل |
| غير موقع أدناه (أسفل) | JB | بلو | بلو * | يستعير |
| غير مُوقّع، أقل من أو يساوي (أصغر أو نفسه) | JBE | بلوس | مكتب إحصاءات العمل الأمريكي (BLS ) * | استعارة أو صفر |
| غير مُوقّع أعلى أو يساوي (أعلى أو نفسه) | جاي | بهيس | بي إتش إس * | لا تستعير |
| غير موقع أعلاه (أعلى) | جا | BHI | BHI * | لا اقتراض ولا صفر |
| تم التوقيع على أقل من | JL | بي إل تي | بي إل تي | لا يعني رمز التجاوز (sign-) تجاوز الحد المسموح به (overflow). |
| التوقيع أقل من أو يساوي | JLE | بلوتوث | بلوتوث | (الإشارة ≠ تجاوز السعة) أو صفر |
| أكبر من أو يساوي الموقع | JGE | بي جي إي | بي جي إي | sign=overflow |
| تم التوقيع أكبر من | جي جي | برنامج المواهب البريطانية (BGT) | برنامج المواهب البريطانية (BGT) | (الإشارة = تجاوز السعة) وليس صفرًا |
في معالجات x86، وPDP-11، وVAX، وبعض المعالجات الأخرى، يتم ضبط علامة الحمل للإشارة إلى الاستعارة ، ومسحها للإشارة إلى عدم وجود استعارة . أما في معالجات ARM، و 6502 ، وPIC، وبعض المعالجات الأخرى، فيتم عكس ذلك في عمليات الطرح. يُشار إلى هذه الوظيفة المعكوسة لعلامة الحمل في بعض التعليمات بعلامة ( * )، أي أن الاستعارة تعني عدم وجود حمل في بعض أجزاء الجدول، ولكن ما لم يُذكر خلاف ذلك، فإن الاستعارة تعني وجود حمل. مع ذلك، فإن الحمل في عمليات الجمع يُعالج بنفس الطريقة في معظم البنى.
مشاكل في أداء تعليمات التفرع
لتحقيق أداء عالٍ، تعتمد المعالجات الحديثة على تقنية خطوط الأنابيب . تتكون هذه المعالجات من أجزاء متعددة، يقوم كل جزء منها بمعالجة جزء من التعليمات، ثم يمرر نتائجه إلى المرحلة التالية في خط الأنابيب، ويبدأ العمل على التعليمات التالية في البرنامج. يفترض هذا التصميم أن تُنفذ التعليمات بتسلسل ثابت ومحدد. إلا أن تعليمات التفرع الشرطي تجعل من المستحيل معرفة هذا التسلسل. لذا، قد تتسبب التفرعات الشرطية في حدوث "توقفات" تستدعي إعادة تشغيل خط الأنابيب على جزء مختلف من البرنامج.
تحسين الأداء عن طريق تقليل حالات التوقف في الفروع
تعمل عدة تقنيات على تحسين السرعة عن طريق تقليل حالات التوقف الناتجة عن الفروع المشروطة.
تلميحات التنبؤ بالفروع
تاريخيًا، اعتمد التنبؤ بالتفرع على الإحصائيات، واستخدم نتائجها لتحسين الكود. كان المبرمج يُجمّع نسخة تجريبية من البرنامج، ويُشغّلها ببيانات اختبارية. يحسب الكود التجريبي عدد مرات تنفيذ التفرعات. ثم يستخدم المُجمّع الإحصائيات المُستخرجة من الكود التجريبي لتحسين تفرعات الكود النهائي. يضمن التحسين أن يكون أسرع اتجاه للتفرع (سواءً نُفّذ أم لا) هو مسار التحكم الأكثر استخدامًا. ولتحقيق ذلك، يجب تصميم وحدات المعالجة المركزية بتوقيت تفرع قابل للتنبؤ (أو على الأقل أن يكون لديها هذا التوقيت). تحتوي بعض وحدات المعالجة المركزية على مجموعات تعليمات (مثل Power ISA ) مصممة بـ"تلميحات التفرع" بحيث يُمكن للمُجمّع إخبار وحدة المعالجة المركزية بكيفية تنفيذ كل تفرع.
تكمن مشكلة التنبؤ بتفرعات البرمجيات في أنها تتطلب عملية تطوير برمجيات معقدة.
مؤشرات تفرع الأجهزة
لتشغيل أي برنامج، نقلت مُتنبئات التفرعات المادية الإحصائيات إلى الدوائر الإلكترونية. مُتنبئات التفرعات هي أجزاء من المعالج تُخمّن نتيجة التفرع الشرطي. ثم يُراهن منطق المعالج على هذا التخمين ببدء تنفيذ تدفق التعليمات المتوقع. مثال على مخطط تنبؤ تفرع مادي بسيط هو افتراض أن جميع التفرعات العكسية (أي إلى عداد برنامج أصغر) تُنفذ (لأنها جزء من حلقة تكرارية)، وأن جميع التفرعات الأمامية (إلى عداد برنامج أكبر) لا تُنفذ (لأنها تخرج من حلقة تكرارية). يتم تطوير مُتنبئات تفرع أفضل والتحقق من صحتها إحصائيًا عن طريق تشغيلها في محاكاة على مجموعة متنوعة من برامج الاختبار. عادةً ما تحسب المُتنبئات الجيدة نتائج عمليات التنفيذ السابقة للتفرع. يمكن لأجهزة الكمبيوتر الأسرع والأكثر تكلفة أن تعمل بشكل أسرع من خلال الاستثمار في إلكترونيات تنبؤ تفرع أفضل. في وحدة المعالجة المركزية المزودة بتنبؤ تفرع مادي، تسمح تلميحات التفرع لتنبؤ التفرع المُفترض أنه أفضل من تنبؤ التفرع المادي بتجاوز تنبؤ التفرع الأبسط في الأجهزة.
رمز خالٍ من الفروع
يمكن كتابة بعض المنطق بدون فروع أو بعدد أقل منها. غالبًا ما يكون من الممكن استخدام عمليات البت ، أو النقلات الشرطية ، أو غيرها من أساليب التنبؤ بدلًا من الفروع. [ 2 ] [ 3 ] في الواقع، يُعدّ الكود الخالي من الفروع ضروريًا في علم التشفير نظرًا لهجمات التوقيت . [ 4 ]
فتحة التأخير
تُعدّ خانة تأخير التفرع تقنية أخرى . في هذا الأسلوب، تُنفَّذ تعليمة واحدة على الأقل بعد التفرع دائمًا، مع بعض الاستثناءات مثل تعليمة التفرع المحتملة/غير المحتملة في معمارية MIPS القديمة . بالتالي، يمكن للحاسوب استخدام هذه التعليمة لإنجاز مهام مفيدة سواءً توقف خط الأنابيب أم لا. كان هذا الأسلوب شائعًا تاريخيًا في حواسيب RISC . في عائلة من وحدات المعالجة المركزية المتوافقة، يُعقّد هذا الأسلوب وحدات المعالجة المركزية متعددة الدورات (بدون خط أنابيب)، ووحدات المعالجة المركزية الأسرع ذات خطوط الأنابيب الأطول من المتوقع، ووحدات المعالجة المركزية فائقة التوازي (التي يمكنها تنفيذ التعليمات خارج الترتيب).
انظر أيضاً
ملحوظات
- ↑ على الأقل من الناحية المفاهيمية؛ انظر التنفيذ خارج الترتيب .
- ↑ مثال: قارن بين المُراكم والتخزين (CAS) وقارن بين المُراكم المنطقي والتخزين (LAS) على جهاز IBM 7094 [ 1 ]
مراجع
- ↑ "تعليمات التحكم" (ملف PDF) . مبادئ تشغيل IBM 7094 (ملف PDF) . مكتبة مراجع الأنظمة. صفحة 53. A22-6703-4 . تاريخ الاسترجاع: 22 سبتمبر 2025 .
- ↑ كنوت، دونالد (2008). فن برمجة الحاسوب . المجلد 4، الجزء التمهيدي 1أ (الطبعة السادسة المنقحة ). الصفحات 48-49 .
- ↑ "تجنب التفرعات" . ويكي برمجة الشطرنج .
- ↑ "التشفير ذو الوقت الثابت" . BearSSL .
روابط خارجية
- وثائق مجانية حول معالجات IA-32 و x86-64 ، مقدمة من شركة إنتل
- الأسئلة الشائعة حول جهاز PDP-11
- مجموعة تعليمات ARM
- تدفق التحكم
- معالجة التعليمات
- لغة الآلة