تقاطع حلقي

في نظرية المترجمات ، يُعرف تبديل الحلقات بأنه عملية تبديل ترتيب متغيري التكرار المستخدمين في حلقة متداخلة . ينتقل المتغير المستخدم في الحلقة الداخلية إلى الحلقة الخارجية، والعكس صحيح. يُستخدم هذا التبديل غالبًا لضمان الوصول إلى عناصر المصفوفة متعددة الأبعاد بالترتيب الذي تظهر به في الذاكرة، مما يُحسّن من موضعية الوصول .

على سبيل المثال، في جزء الكود التالي:

لكل قيمة j من 0 إلى 20 لكل i من 0 إلى 10 a[i,j] = i + j

سيؤدي تبادل الحلقات إلى ما يلي:

لكل i من 0 إلى 10 لكل قيمة j من 0 إلى 20 a[i,j] = i + j

في بعض الأحيان، قد يخلق هذا التحول فرصًا لمزيد من التحسين، مثل التحويل التلقائي لتعيينات المصفوفة.

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

في لغة البرمجة C ، تُخزَّن عناصر المصفوفة في الصف نفسه بشكل متسلسل في الذاكرة (a[1,1], a[1,2], a[1,3]) - أي بترتيب الصفوف . بينما في برامج FORTRAN ، تُخزَّن عناصر المصفوفة من العمود نفسه معًا (a[1,1], a[2,1], a[3,1]) باستخدام ترتيب الأعمدة . لذا، فإن ترتيب متغيري التكرار في المثال الأول مناسب لبرنامج FORTRAN، بينما يُعدّ المثال الثاني أفضل لبرنامج C. ^{[ 1 ]} تستطيع مُجمِّعات التحسين اكتشاف الترتيب غير الصحيح من قِبل المبرمجين وتغييره لتحسين أداء الذاكرة المؤقتة.

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

كرر من i = 1 إلى 10000، ثم من j = 1 إلى 1000 ، ثم اجعل a [ i ] = a [ i ] + b [ j , i ] * c [ i ] ، ثم كرر .

يمكن لتبديل الحلقات في هذا المثال تحسين أداء ذاكرة التخزين المؤقت للوصول إلى b(j,i)، ولكنه سيؤدي إلى إفساد إعادة استخدام a(i) و c(i) في الحلقة الداخلية، حيث يُضيف عمليتي تحميل إضافيتين (لـ a(i) و c(i)) وعملية تخزين إضافية واحدة (لـ a(i)) خلال كل تكرار. ونتيجة لذلك، قد يتدهور الأداء العام بعد تبديل الحلقات.

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

• تقسيم الحلقة
• انحراف الحلقة
• الانشطار والاندماج الحلقي
• فك الحلقة

• كينيدي، كين ؛ ألين، راندي (2002). تحسين المترجمات للبنى الحديثة: منهج قائم على التبعية (طبعة رقمية مطبوعة لعام 2011 من  الطبعة الأولى). أكاديميك برس / مورغان كوفمان للنشر / إلسيفير . ISBN 978-1-55860-286-1. إل سي سي إن 2001092381 .