تحسين تداخل الحلقات

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

تُسمى التقنية المستخدمة لإنتاج هذا التحسين بتقسيم الحلقات ، ^{[ 1 ]} والمعروفة أيضًا باسم حجب الحلقات ^{[ 2 ]} أو التعدين والتبادل .

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

حلقة عادية

for ( i = 0 ; i < N ; ++ i ) { ... }

يمكن حظرها بحجم كتلة B عن طريق استبدالها بـ

for ( j = 0 ; j < N ; j += B ) { for ( i = j ; i < min ( N , j + B ); ++ i ) { .... } }

حيث min()تمثل دالة تُرجع أصغر قيمة من بين وسائطها.

فيما يلي مثال على ضرب المصفوفة بالمتجه. توجد ثلاث مصفوفات، كل منها تحتوي على 100 عنصر. لا يقوم البرنامج بتقسيم المصفوفات إلى أحجام أصغر.

int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i ++ ) { c [ i ] = 0 ; for ( j = 0 ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ][ j ] * b [ j ]; } }

بعد تطبيق التجانب الحلقي باستخدام كتل 2 × 2، يبدو الكود كما يلي:

int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i += 2 ) { c [ i ] = 0 ; c [ i + 1 ] = 0 ; for ( j = 0 ; j < n ; j += 2 ) { for ( x = i ; x < min ( i + 2 , n ); x ++ ) { for ( y = j ; y < min ( j + 2 , n ); y ++ ) { c [ x ] = c [ x ] + a [ x ][ y ] * b [ y ]; } } } }

مساحة تكرار الحلقة الأصلية هي n × n . الجزء الذي يتم الوصول إليه من المصفوفة a[i, j] هو أيضًا n × n . عندما تكون n كبيرة جدًا ويكون حجم ذاكرة التخزين المؤقت للجهاز صغيرًا جدًا، فقد تعبر عناصر المصفوفة التي يتم الوصول إليها في تكرار حلقة واحد (على سبيل المثال، i = 1) j = 1 to nخطوط ذاكرة التخزين المؤقت، مما يتسبب في فقدان البيانات في ذاكرة التخزين المؤقت.

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

تُقضي العديد من العمليات الحسابية الكبيرة على أجهزة الكمبيوتر معظم وقتها في ضرب المصفوفات . وهذه العملية هي:

ج = أ × ب

حيث A و B و C عبارة عن مصفوفات N×N. تكون الرموز السفلية، للوصف التالي، على شكل C[row][column].

الحلقة الأساسية هي:

int i , j , k ;for ( i = 0 ; i < N ; ++ i ) { for ( j = 0 ; j < N ; ++ j ) { C [ i ][ j ] = 0 ;for ( k = 0 ; k < N ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } }

هناك ثلاث مشاكل يجب حلها:

• تستغرق عمليات جمع الأعداد العشرية عددًا من الدورات لإتمامها. ولإبقاء وحدة الجمع ذات زمن الاستجابة المتعدد مشغولة، يجب على البرنامج تحديث عدة مُراكمات بالتوازي.
• تستطيع الآلات عادةً إجراء عملية ذاكرة واحدة فقط لكل عملية ضرب وجمع ، لذلك يجب إعادة استخدام القيم المحملة مرتين على الأقل.
• لا تستطيع أنظمة ذاكرة الكمبيوتر الشخصي النموذجية استيعاب سوى كلمة مزدوجة واحدة بحجم 8 بايت لكل 10 إلى 30 عملية ضرب وجمع ذات دقة مزدوجة، لذلك يجب إعادة استخدام القيم المحملة في ذاكرة التخزين المؤقت عدة مرات.

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

for ( i = 0 ; i < N ; i += 2 ) { for ( j = 0 ; j < N ; j += 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; for ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } }

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

سيعمل هذا الكود بكفاءة مقبولة على جهاز Cray Y-MP (الذي صُنع في أوائل الثمانينيات)، والذي يمكنه استيعاب 0.8  عملية ضرب وجمع لكل عملية ذاكرة في الذاكرة الرئيسية. أما جهاز مثل  Pentium 4 بسرعة 2.8 جيجاهرتز  ، الذي صُنع عام 2003، فيمتلك نطاق ترددي أقل قليلاً للذاكرة وأداءً أفضل بكثير في العمليات الحسابية ذات الفاصلة العائمة، مما يسمح له باستيعاب 16.5  عملية ضرب وجمع لكل عملية ذاكرة. ونتيجة لذلك، سيعمل الكود المذكور أعلاه بشكل أبطأ على جهاز  Pentium 4 بسرعة 2.8 جيجاهرتز  مقارنةً بجهاز  Y-MP بسرعة 166 ميجاهرتز!

تتطلب الآلة ذات زمن استجابة جمع الفاصلة العائمة الأطول أو التي تحتوي على عدة وحدات جمع عددًا أكبر من المُراكمات للعمل بالتوازي. من السهل تغيير الحلقة المذكورة أعلاه لحساب كتلة 3x3 بدلًا من كتلة 2x2، ولكن الكود الناتج ليس أسرع دائمًا. تتطلب الحلقة سجلات لتخزين كل من المُراكمات وقيم A وB المُحمّلة والمُعاد استخدامها. تتطلب كتلة 2x2 سبعة سجلات، بينما تتطلب كتلة 3x3 ثلاثة عشر سجلًا، وهو ما لن يعمل على آلة تحتوي على ثمانية سجلات فقط للفاصلة العائمة في مجموعة تعليمات المعالج . إذا لم يكن لدى وحدة المعالجة المركزية عدد كافٍ من السجلات، فسيقوم المُصرّف بجدولة عمليات تحميل وتخزين إضافية لتفريغ السجلات في خانات المكدس، مما سيؤدي إلى إبطاء الحلقة مقارنةً بحلقة أصغر حجمًا.

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

لا يستغل الكود أعلاه الذاكرة المؤقتة بكفاءة. أثناء حساب شريط أفقي من نتائج C، يتم تحميل شريط أفقي واحد من A، بالإضافة إلى تحميل المصفوفة B بأكملها. خلال عملية الحساب بأكملها، يتم تخزين C مرة واحدة (وهذا جيد)، ويتم تحميل A في الذاكرة المؤقتة مرة واحدة (بافتراض أن شريط A يتسع في الذاكرة المؤقتة مع شريط B)، بينما يتم تحميل B عدد N/ib من المرات، حيث ib هو حجم الشريط في مصفوفة C، ليصبح المجموع N ^/ ib من عمليات تحميل الكلمات المزدوجة من الذاكرة الرئيسية. في الكود أعلاه، قيمة ib تساوي 2.

تتمثل الخطوة التالية لتقليل حركة البيانات في الذاكرة في جعل قيمة ib أكبر ما يمكن. يجب أن تكون أكبر من قيمة "التوازن" التي تُبلغ عنها التدفقات. في حالة نظام  Pentium  4 بتردد 2.8 جيجاهرتز المستخدم في هذا المثال، تبلغ قيمة التوازن 16.5. لا يمكن توسيع مثال الكود الثاني أعلاه مباشرةً، لأن ذلك سيتطلب عددًا أكبر بكثير من سجلات المُراكم. بدلاً من ذلك، يتم حظر الحلقة عند قيمة i. (من الناحية الفنية، هذه هي المرة الثانية التي يتم فيها حظر i، لأن المرة الأولى كانت من مضاعفات 2).

for ( ii = 0 ; ii < N ; ii += ib ) { for ( j = 0 ; j < N ; j += 2 ) { for ( i = ii ; i < ii + ib ; i += 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; for ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } }

باستخدام هذا الكود، يمكن ضبط قيمة ib على أي قيمة مرغوبة، وسيتم تقليل عدد مرات تحميل المصفوفة B بهذا المقدار. لكن هذه المرونة لها ثمن: يتم الاحتفاظ بـ N×ib شريحة من المصفوفة A في الذاكرة المؤقتة. وطالما أن هذا العدد مناسب، فلن يكون هذا الكود مقيدًا بنظام الذاكرة.

إذن، ما هو حجم المصفوفة المناسب؟ النظام المستخدم في المثال، وهو  معالج بنتيوم 4 بسرعة 2.8 جيجاهرتز، يحتوي على ذاكرة تخزين مؤقتة للبيانات الأساسية بسعة 16 كيلوبايت. مع قيمة ib=20، ستكون شريحة المصفوفة A في هذا الكود أكبر من ذاكرة التخزين المؤقتة الأساسية عندما تكون N > 100. أما بالنسبة للمسائل الأكبر من ذلك، فيلزم استخدام حيلة أخرى.

تتمثل هذه الحيلة في تقليل حجم شريط المصفوفة B عن طريق حجب حلقة k بحيث يصبح حجم الشريط ib × kb. ويعني حجب حلقة k أنه سيتم تحميل وتخزين مصفوفة C عدد N/kb من المرات، ليصبح المجموع ⁠${\displaystyle 2*N^{3}/kb}$عمليات نقل الذاكرة . لا يزال يتم نقل B N/ib مرة، لـ${\displaystyle N^{3}/ib}$التحويلات . طالما

2*N/kb + N/ib < N/balance

سيواكب نظام ذاكرة الجهاز وحدة الفاصلة العائمة، وسيعمل البرنامج بأقصى أداء. ذاكرة التخزين المؤقت (الكاش) بسعة 16 كيلوبايت في معالج بنتيوم 4 ليست كافية تمامًا: فإذا تم اختيار ib=24 و kb=64 بدلًا من ذلك، فسيتم استخدام 12 كيلوبايت من ذاكرة التخزين المؤقت - مما يمنع امتلائها بالكامل، وهو أمر مرغوب فيه لكي يتوفر للمصفوفات C و B مساحة كافية للتدفق. هذه الأرقام قريبة بنسبة 20% من ذروة سرعة الفاصلة العائمة للمعالج.

إليك الكود مع kحظر الحلقة.

for ( ii = 0 ; ii < N ; ii += ib ) { for ( kk = 0 ; kk < N ; kk += kb ) { for ( j = 0 ; j < N ; j += 2 ) { for ( i = ii ; i < ii + ib ; i += 2 ) { if ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; else { acc00 = C [ i + 0 ][ j + 0 ]; acc01 = C [ i + 0 ][ j + 1 ]; acc10 = C [ i + 1 ][ j + 0 ]; acc11 = C [ i + 1 ][ j + 1 ]; } for ( k = kk ; k < kk + kb ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } } }

لا تُظهر أمثلة التعليمات البرمجية أعلاه تفاصيل التعامل مع قيم N التي ليست من مضاعفات عوامل الحجب. تُصدر المترجمات التي تُجري تحسينًا لتداخل الحلقات تعليمات برمجية لتنظيف حواف الحساب. على سبيل المثال، من المرجح أن تفصل معظم مترجمات LNO تكرار kk == 0 عن بقية التكرارات kk، لإزالة عبارة if من iالحلقة. هذه إحدى مزايا هذا النوع من المترجمات: فبينما يسهل كتابة الحالات البسيطة لهذا التحسين، فإن الحفاظ على صحة جميع التفاصيل أثناء تكرار التعليمات البرمجية وتحويلها عمليةٌ عُرضةٌ للأخطاء.

لن تحقق الحلقة المذكورة أعلاه سوى 80% من ذروة عمليات الفاصلة العائمة على النظام الموضح في المثال عند حظرها لحجم ذاكرة التخزين المؤقت من المستوى الأول (L1) البالغ 16 كيلوبايت. وسيكون أداؤها أسوأ على الأنظمة ذات أنظمة الذاكرة غير المتوازنة. لحسن الحظ، يحتوي معالج بنتيوم 4 على ذاكرة تخزين مؤقت من المستوى الثاني (L2) عالية النطاق الترددي بسعة 256 كيلوبايت (أو أكثر، حسب الطراز)، بالإضافة إلى ذاكرة التخزين المؤقت من المستوى الأول (L1). لديك خيار:

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

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

• جهاز داف
• تحسين الحلقة

1. وولف، م. المزيد من تبليط مساحة التكرار . الحوسبة الفائقة 89، الصفحات 655-664، 1989.
2. وولف، إم إي ولام، إم. خوارزمية تحسين موضع البيانات . PLDI '91، الصفحات 30-44، 1991.
3. Irigoin, F. and Triolet, R. Supernode Partitioning . POPL '88, pages 319–329, 1988.
4. Xue, J. Loop Tiling for Parallelism . Kluwer Academic Publishers. 2000.
5. إم إس لام، إي إي روثبرغ، وإم إي وولف. أداء ذاكرة التخزين المؤقت وتحسينات الخوارزميات المحظورة . في وقائع المؤتمر الدولي الرابع حول الدعم المعماري للغات البرمجة وأنظمة التشغيل، الصفحات 63-74، أبريل 1991.

• نتائج قياس أداء Streams ، والتي توضح التوازن العام بين عمليات الفاصلة العائمة وعمليات الذاكرة للعديد من أجهزة الكمبيوتر المختلفة
• "CHiLL: إطار عمل تحويل الحلقات عالي المستوى القابل للتركيب"