تحسين الحلقة

في نظرية المترجمات ، يُعدّ تحسين الحلقات عمليةً لزيادة سرعة التنفيذ وتقليل النفقات العامة المرتبطة بها . ويلعب دورًا هامًا في تحسين أداء الذاكرة المؤقتة والاستفادة الفعّالة من إمكانيات المعالجة المتوازية . يُقضى معظم وقت تنفيذ البرنامج العلمي في الحلقات؛ ولذلك، طُوّرت العديد من تقنيات تحسين المترجمات لتسريعها.

بما أن التعليمات داخل الحلقات قابلة للتنفيذ بشكل متكرر، فإنه غالبًا ما يتعذر تحديد حد أقصى لعدد مرات تنفيذ التعليمات التي ستتأثر بتحسين الحلقة. وهذا يطرح تحديات عند التفكير في صحة وفوائد تحسين الحلقة، وتحديدًا تمثيلات الحساب الذي يتم تحسينه والتحسينات التي يتم إجراؤها. ^{[ 1 ]}

يمكن النظر إلى تحسين الحلقات على أنه تطبيق سلسلة من تحويلات الحلقات المحددة (المذكورة أدناه أو في تحويلات المُصرّف للحوسبة عالية الأداء ^{[ 2 ]} ) على شفرة المصدر أو التمثيل الوسيط ، مع وجود اختبار مُرتبط بكل تحويل للتأكد من صحته. يجب أن يحافظ التحويل (أو سلسلة التحويلات) عمومًا على التسلسل الزمني لجميع التبعيات للحفاظ على نتيجة البرنامج (أي أن يكون تحويلًا صحيحًا). قد يكون تقييم فائدة التحويل أو سلسلة التحويلات صعبًا للغاية ضمن هذا النهج، حيث قد يتطلب تطبيق تحويل مفيد واحد استخدام تحويل أو أكثر مسبقًا، والتي قد تؤدي، في حد ذاتها، إلى انخفاض الأداء.

تشمل تحويلات الحلقات الشائعة ما يلي:

• الانشطار أو التوزيع – يحاول انشطار الحلقة تقسيم حلقة تكرارية إلى حلقات متعددة ضمن نفس نطاق الفهرس، ولكن كل حلقة جديدة تستخدم جزءًا فقط من جسم الحلقة الأصلية. وهذا يُحسّن من موضعية الوصول ، سواءً للبيانات التي يتم الوصول إليها داخل الحلقة أو للتعليمات البرمجية الموجودة في جسم الحلقة.
• الدمج أو الجمع - هذا يجمع أجزاء حلقتين متجاورتين تتكرران بنفس عدد المرات (سواء كان هذا العدد معروفًا في وقت الترجمة أم لا)، طالما أنهما لا يشيران إلى بيانات بعضهما البعض.
• التبديل أو الاستبدال – تعمل هذه التحسينات على تبديل الحلقات الداخلية مع الحلقات الخارجية. عندما تُفهرس متغيرات الحلقة في مصفوفة، يمكن لهذا التحويل تحسين موضعية المرجع، وذلك بحسب تخطيط المصفوفة.
• تقنية الانعكاس – تُحوّل هذه التقنية حلقة while القياسية إلى حلقة do/while (المعروفة أيضًا باسم repeat/until ) مُغلّفة بشرط if ، مما يُقلّل عدد القفزات بمقدار قفزتين في الحالات التي تُنفّذ فيها الحلقة. يُكرّر هذا التحقق من الشرط (مما يزيد من حجم الكود)، ولكنه أكثر كفاءة لأن القفزات عادةً ما تُسبّب توقفًا في خط الأنابيب . بالإضافة إلى ذلك، إذا كان الشرط الأولي معروفًا وقت الترجمة، وكان من المعروف أنه خالٍ من الآثار الجانبية ، فيمكن تخطّي شرط if الأولي .
• نقل التعليمات البرمجية غير المتأثرة بالحلقات - يمكن لهذه التقنية تحسين الكفاءة بشكل كبير عن طريق نقل عملية حسابية من داخل الحلقة إلى خارجها، وحساب القيمة مرة واحدة فقط قبل بدء الحلقة، إذا كانت القيمة الناتجة عن الحساب ستكون نفسها في كل تكرار للحلقة (أي قيمة غير متأثرة بالحلقات). يُعد هذا الأمر بالغ الأهمية مع تعابير حساب العناوين الناتجة عن الحلقات على المصفوفات. لضمان التنفيذ الصحيح، يجب استخدام هذه التقنية مع عكس التعليمات البرمجية، لأنه ليس من الآمن نقل جميع التعليمات البرمجية خارج الحلقة.
• التوازي – هو حالة خاصة من التوازي التلقائي تركز على الحلقات، حيث يتم إعادة هيكلتها لتشغيلها بكفاءة على أنظمة المعالجات المتعددة. يمكن القيام بذلك تلقائيًا بواسطة المترجمات ( التوازي التلقائي ) أو يدويًا (بإدراج توجيهات التوازي مثل OpenMP ).
• الانعكاس – تحسين دقيق يعكس ترتيب إسناد القيم إلى متغير الفهرس. يساعد هذا في التخلص من التبعيات ، وبالتالي تمكين تحسينات أخرى. تستخدم بعض البنى هياكل تكرارية على مستوى لغة التجميع ، تحسب في اتجاه واحد فقط (مثل: التناقص-القفز-إذا-لم-يكن-صفرًا [DJNZ] ^{[ 3 ]} ).
• الجدولة - هذا يقسم الحلقة إلى أجزاء متعددة يمكن تشغيلها في وقت واحد على معالجات متعددة.
• التحريف - يتم تطبيق هذه التقنية على حلقة متداخلة تتكرر على مصفوفة متعددة الأبعاد، حيث يعتمد كل تكرار للحلقة الداخلية على التكرارات السابقة، ويعيد ترتيب عمليات الوصول إلى المصفوفة بحيث تكون التبعيات الوحيدة بين تكرارات الحلقة الخارجية.
• تقنية خطوط الأنابيب البرمجية - نوع من التنفيذ خارج الترتيب لتكرارات الحلقة لإخفاء زمن استجابة وحدات وظائف المعالج.
• تقسيم الحلقة أو تقشيرها - يهدف هذا الأسلوب إلى تبسيط الحلقة أو إزالة التبعيات بتقسيمها إلى حلقات متعددة لها نفس البنية ولكنها تتكرر على أجزاء مختلفة من نطاق الفهرس. ومن الحالات الخاصة تقشير الحلقة ، الذي يُبسّط الحلقة التي تحتوي على تكرار أولي إشكالي بتنفيذ هذا التكرار بشكل منفصل قبل الدخول إلى الحلقة.
• التجزئة أو الحظر - يعيد تنظيم حلقة للتكرار على كتل من البيانات بحجم يناسب ذاكرة التخزين المؤقت.
• التوجيه المتجهي - محاولات لتشغيل أكبر عدد ممكن من تكرارات الحلقة في نفس الوقت على نظام SIMD .
• فكّ الحلقة - يُكرّر جسم الحلقة عدة مرات لتقليل عدد مرات اختبار شرط الحلقة وعدد القفزات، مما قد يُؤثر سلبًا على الأداء من خلال تعطيل مسار تنفيذ التعليمات. يُزيل فكّ الحلقة بالكامل جميع النفقات العامة (باستثناء جلب التعليمات المتعددة وزيادة وقت تحميل البرنامج)، ولكنه يتطلب معرفة عدد التكرارات وقت الترجمة (باستثناء حالة الترجمة الفورية ). يجب أيضًا الحرص على ألا تُشكّل إعادة حساب المتغيرات المفهرسة عبئًا عامًا أكبر من تحريك المؤشرات داخل الحلقة الأصلية.
• إلغاء التبديل - ينقل الشرط من داخل حلقة إلى خارجها عن طريق تكرار جسم الحلقة، ووضع نسخة منه داخل كل من عبارات if و else الخاصة بالشرط.
• تقنية تقسيم الحلقات أو استخراج البيانات من الشرائح - التي طُرحت في معالجات المتجهات - هي تقنية لتحويل الحلقات تُمكّن من ترميز الحلقات باستخدام SIMD (تعليمات واحدة، بيانات متعددة) وتحسين أداء الذاكرة. وتتضمن هذه التقنية تنفيذ كل عملية متجهة بحجم لا يتجاوز أو يساوي أقصى طول للمتجه على آلة متجهة معينة. ^{[ 4 ] [ 5 ]}

• تحسين تداخل الحلقات
• نموذج متعدد الأوجه
• التوازي القابل للتوسع
• موقع قابل للتوسع