الانشطار والاندماج الحلقي

الموسوعة الحرة

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

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

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

الانشطار

مثال بلغة C

int a [ 100 ]; int b [ 100 ]; for ( int i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; b [ i ] = 2 ; }

يعادل ما يلي:

int a [ 100 ]; int b [ 100 ]; for ( int i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; } for ( int i = 0 ; i < 100 ; i ++ ) { b [ i ] = 2 ; }

الاندماج

مثال بلغة C++ و MATLAB

انظر إلى كود MATLAB التالي:

x = 0 : 999 ; % إنشاء مصفوفة من الأرقام من 0 إلى 999 (يشمل النطاق) y = sin ( x ) + 4 ; % حساب جيب قيمة x (عنصرًا عنصرًا) وإضافة 4 إلى كل عنصر

يمكن تحقيق نفس الصيغة في لغة C++ باستخدام تحميل الدوال والمعاملات الزائدة:

استيراد < cassert > ;استيراد std ؛باستخدام std :: unique_ptr ؛class FloatArray { private : size_t length ; std :: unique_ptr < float [] > data ; // مُنشئ داخلي يُنتج مصفوفة غير مُهيأة explicit FloatArray ( size_t n ) : length { n }, data { new float [ n ]} { } public : // دالة مصنع لإنتاج مصفوفة ضمن نطاق عدد صحيح ( الحد الأعلى غير شامل، على عكس نطاقات MATLAB). [[ nodiscard ]] static FloatArray range ( size_t start , size_t end ) { assert ( end > start ); size_t length = end - start ; FloatArray a ( length ); for ( size_t i = 0 ; i < length ; ++ i ) { a [ i ] = start + i ; } return a ; } // عمليات المصفوفة الأساسية [[ nodiscard ]] size_t size () const noexcept { return length ; }float & operator []( size_t i ) noexcept { return data [ i ]; }const float & operator []( size_t i ) const noexcept { return data [ i ]; }// تعريف عامل جمع مُحمّل كدالة صديقة حرة (يُعرّف هذا // التركيب عامل الجمع كدالة حرة صديقة لهذه // الفئة، على الرغم من ظهوره كإعلان دالة عضو). friend FloatArray operator + ( const FloatArray & a , float b ) { FloatArray c ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { c [ i ] = a [ i ] + b ; } return c ; } // وبالمثل، يمكننا تعريف تحميل زائد لدالة sin(). عمليًا، // سيكون من غير العملي تعريف جميع العمليات الرياضية المُحمّلة الممكنة كـ // دوال صديقة داخل الفئة بهذه الطريقة، ولكن هذا مجرد مثال. friend FloatArray sin ( const FloatArray & a ) { FloatArray b ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } return b ; } };int main ( int argc , char * argv []) { // هنا، نقوم بنفس العملية الحسابية كما في مثال MATLAB FloatArray x = FloatArray :: range ( 0 , 1000 ); FloatArray y = sin ( x ) + 4 ; // طباعة النتيجة - فقط للتأكد من أن المُحسِّن لا يحذف // كل شيء (إذا كان ذكيًا بما يكفي للقيام بذلك). std :: println ( "النتيجة هي: " ); for ( float f : y ) { std :: println ( "{}" , f ); } return 0 ; }

مع ذلك، يُخصّص المثال أعلاه مصفوفة مؤقتة لنتيجة العملية دون داعٍ sin(x). يُفضّل في التنفيذ الأكثر كفاءة تخصيص مصفوفة واحدة فقط y، وحساب النتيجة yفي حلقة تكرارية واحدة. لتحسين ذلك، يحتاج مُصرّف لغة C++ إلى ما يلي:

  1. قم بتضمين استدعاءات الدوال sinوالوظائف operator+.
  2. قم بدمج الحلقات في حلقة واحدة.
  3. قم بإزالة المخازن غير المستخدمة إلى المصفوفات المؤقتة (يمكن استخدام سجل أو متغير مكدس بدلاً من ذلك).
  4. قم بإزالة التخصيص غير المستخدم وحرر الذاكرة.

جميع هذه الخطوات ممكنة بشكل فردي. حتى الخطوة الرابعة ممكنة رغم أن دوالًا مثل ` mallocand` freeلها تأثيرات جانبية عامة، لأن بعض المترجمات تُضمّن رموزًا مثل ` mallocand` freeبشكل ثابت لإزالة التخصيصات غير المستخدمة من الكود. [ 6 ] مع ذلك، بدءًا من clang 12.0.0 و gcc 11.1، لا يحدث دمج الحلقات وإزالة التخصيصات الزائدة - حتى على أعلى مستوى من التحسين. [ 7 ] [ 8 ]

قد تتضمن بعض اللغات المصممة خصيصًا للحوسبة العددية، مثل جوليا، مفهوم دمج الحلقات بشكل مضمن في بنيتها، حيث يلاحظ المترجم عمليات العناصر المتجاورة ويدمجها في حلقة واحدة. [ 9 ] حاليًا، لتحقيق نفس الصيغة في لغات الأغراض العامة مثل C++، يجب على sinالدوال operator+تخصيص مصفوفات بشكل متشائم لتخزين نتائجها، نظرًا لعدم معرفتها بالسياق الذي ستُستدعى منه. يمكن تجنب هذه المشكلة في C++ باستخدام صيغة مختلفة لا تعتمد على المترجم لإزالة التخصيصات المؤقتة غير الضرورية (مثل استخدام الدوال والتحميل الزائد للعمليات الموضعية، مثل ` operator+=for` أو `for` std::transform).

انظر أيضاً

مراجع

  1. ↑ واي إن سريكانت؛ بريتي شانكار (3 أكتوبر 2018). دليل تصميم المترجمات: التحسينات وتوليد كود الآلة، الطبعة الثانية . مطبعة سي آر سي. رقم ISBN 978-1-4200-4383-9.
  2. 1 2 كينيدي، كين وآلين، راندي. (2001). تحسين المترجمات للهياكل الحديثة: منهج قائم على التبعية . مورغان كوفمان. ISBN 1-55860-286-0.
  3. ↑ ستيفن موشنيك؛ موشنيك وشركاؤه (15 أغسطس 1997). تصميم وتنفيذ المترجمات المتقدمة . مورغان كوفمان. ISBN 978-1-55860-320-2دمج الحلقات .
  4. 1 2 جونسون، ستيفن ج. (21 يناير 2017). "المزيد من النقاط: دمج الحلقات النحوية في جوليا" . julialang.org . تم الاسترجاع في 25 يونيو 2021 .
  5. ↑ "دمج الحلقات" . إنتل . تم الاسترجاع في 25-06-2021 .
  6. ↑ غودبولت، مات. "مستكشف المترجم - لغة سي++ (x86-64 clang 12.0.0)" . godbolt.org . تم الاطلاع عليه بتاريخ 25-06-2021 .
  7. ↑ غودبولت، مات. "مستكشف المترجم - لغة سي++ (x86-64 clang 12.0.0)" . godbolt.org . تم الاطلاع عليه بتاريخ 25-06-2021 .
  8. ↑ جودبولت، مات. "مستكشف المترجم - لغة سي++ (x86-64 gcc 11.1)" . godbolt.org . تم الاطلاع عليه بتاريخ 25-06-2021 .
  9. ↑ "الدوال · لغة جوليا" . docs.julialang.org . تم الاطلاع عليه بتاريخ 25-06-2021 .
  • الانشطار الحلقي