التوازي على مستوى الحلقة

كثافة العمليات أ ، ب ؛ // s1 أ = 2 ; // s2 ب = أ + 40 ؛ // S3

s2 ->T s3، مما يعني أن s2 لديه اعتماد حقيقي على s3 لأن s2 يكتب إلى المتغير a، الذي يقرأ منه s3.

كثافة العمليات أ ، ب = 40 ؛ // s1 أ = ب - 38 ؛ // s2 ب = -1 ; // S3

s2 ->A s3، مما يعني أن s2 لديه اعتماد عكسي على s3 لأن s2 يقرأ من المتغير bقبل أن يكتب s3 إليه.

كثافة العمليات أ ، ب = 40 ؛ // s1 أ = ب - 38 ؛ // s2 أ = 2 ; // S3

s2 ->O s3، مما يعني أن s2 يعتمد في مخرجاته على s3 لأن كلاهما يكتب إلى المتغير a.

int a , b , c = 2 ; // s1 a = c - 1 ; // s2 b = c + 1 ; // s3

s2 ->I s3، مما يعني أن s2 يعتمد على s3 في الإدخال لأن s2 و s3 كلاهما يقرأ من المتغير c.

يمكن أن تحتوي الحلقات على نوعين من التبعية:

• الاعتماد الذي تحمله الحلقة
• التبعية المستقلة عن الحلقة

في التبعية المستقلة عن الحلقات، توجد تبعية بين الحلقات فيما بينها، ولكن لا توجد تبعية بين التكرارات. يمكن التعامل مع كل تكرار كوحدة مستقلة وتنفيذه بالتوازي دون الحاجة إلى جهود تزامن إضافية.

في مثال الكود التالي المستخدم لتبديل قيم مصفوفتين بطول n، هناك اعتماد مستقل عن الحلقة لـ s1 ->T s3.

for ( int i = 1 ; i < n ; ++ i ) { tmp = a [ i ]; // s1 a [ i ] = b [ i ]; // s2 b [ i ] = tmp ; // s3 }

في التبعية المُحملة في الحلقة، تعتمد التعليمات في تكرار حلقة ما على التعليمات في تكرار آخر من نفس الحلقة. وتستخدم التبعية المُحملة في الحلقة نسخة مُعدلة من صيغة التبعية التي تم شرحها سابقًا.

مثال على التبعية المنقولة في الحلقة حيث يشير s1[i] ->T s1[i + 1]، حيث iيشير إلى التكرار الحالي، i + 1ويشير إلى التكرار التالي.

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + 1 ; // s1 }

يُظهر الرسم البياني للاعتمادات المنقولة عبر الحلقة الاعتمادات المنقولة بين التكرارات. يُدرج كل تكرار كعقدة على الرسم البياني، وتُظهر الحواف الموجهة الاعتمادات الحقيقية والمضادة واعتمادات المخرجات بين كل تكرار.

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

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += d [ i ]; // s2 }

تحتوي الحلقة على تبعية مرتبطة بالحلقة، s1[i] ->T s1[i + 1]لكن s2 و s1 لا تحتويان على تبعية مستقلة عن الحلقة، لذلك يمكننا إعادة كتابة الكود على النحو التالي.

// loop1 for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 }// الحلقة الثانية for ( int i = 1 ; i < n ; ++ i ) { c [ i ] += d [ i ]; // s2 }

لاحظ أنه يمكن الآن تنفيذ الحلقتين loop1 و loop2 بالتوازي. فبدلاً من تنفيذ تعليمة واحدة بالتوازي على بيانات مختلفة كما هو الحال في التوازي على مستوى البيانات، تقوم الحلقات المختلفة هنا بتنفيذ مهام مختلفة على بيانات مختلفة. لنفترض أن زمن تنفيذ s1 و s2 هو${\displaystyle T_{s_{1}}}$و${\displaystyle T_{s_{2}}}$إذن، يكون وقت تنفيذ الشكل التسلسلي للكود أعلاه هو${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$والآن، بما أننا قمنا بتقسيم العبارتين ووضعناهما في حلقتين مختلفتين، فإن ذلك يعطينا وقت تنفيذ قدره${\displaystyle n\cdot T_{s_{1}}+T_{s_{2}}}$نطلق على هذا النوع من التوازي اسم التوازي الوظيفي أو التوازي المتعلق بالمهام.

يتحقق التوازي DOALL عندما يمكن تنفيذ التعليمات داخل حلقة تكرارية بشكل مستقل (أي عندما لا توجد تبعية ناتجة عن الحلقة). ^{[ 1 ]} على سبيل المثال، لا يقرأ الكود التالي من المصفوفة a، ولا يُحدّث المصفوفات b, c. لا توجد أي تكرارات تعتمد على أي تكرار آخر.

for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 }

لنفترض أن زمن تنفيذ واحد لـ s1 هو${\displaystyle T_{s_{1}}}$إذن، يكون وقت تنفيذ الشكل التسلسلي للكود أعلاه هو${\displaystyle n\cdot T_{s_{1}}}$وبما أن التوازي في تنفيذ جميع العمليات (DOALL) موجود عندما تكون جميع التكرارات مستقلة، فإنه يمكن تحقيق تسريع من خلال تنفيذ جميع التكرارات بالتوازي، مما يعطينا وقت تنفيذ قدره${\displaystyle T_{s_{1}}}$، وهو الوقت المستغرق لتكرار واحد في التنفيذ التسلسلي.

يوضح المثال التالي، باستخدام رمز زائف مبسط، كيف يمكن موازاة حلقة لتنفيذ كل تكرار بشكل مستقل.

beginParallelism ();for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 endParallelism (); }حاجز ()؛

توجد التوازية في DOACROSS حيث يتم تنفيذ تكرارات حلقة ما بالتوازي عن طريق استخراج العمليات الحسابية التي يمكن إجراؤها بشكل مستقل وتشغيلها في وقت واحد. ^{[ 5 ]}

توجد خاصية التزامن لفرض التبعية التي تحملها الحلقة.

ضع في اعتبارك الحلقة المتزامنة التالية مع التبعية s1[i] ->T s1[i + 1].

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ] + 1 ; }

تُنفذ كل دورة تكرارية إجراءين

• احسبa[i - 1] + b[i] + 1
• قم بتعيين القيمة إلىa[i]

يمكن تقسيم عملية حساب القيمة a[i - 1] + b[i] + 1، ثم إجراء عملية الإسناد، إلى سطرين (العبارتين s1 و s2):

int tmp = b [ i ] + 1 ; // s1 a [ i ] = a [ i - 1 ] + tmp ; // s2

السطر الأول، int tmp = b[i] + 1;، لا يعتمد على حلقة التكرار. يمكن بعد ذلك تنفيذ الحلقة بالتوازي عن طريق حساب القيمة المؤقتة بالتوازي، ثم مزامنة عملية الإسناد إلى a[i].

post ( 0 ); for ( int i = 1 ; i < n ; ++ i ) { int tmp = b [ i ] + 1 ; // s1 wait ( i - 1 );a [ i ] = a [ i - 1 ] + tmp ; // s2 post ( i ); }

لنفترض أن وقت تنفيذ s1 و s2 هو${\displaystyle T_{s_{1}}}$و${\displaystyle T_{s_{2}}}$إذن، يكون وقت تنفيذ الشكل التسلسلي للكود أعلاه هو${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$والآن، بفضل وجود التوازي في DOACROSS، يمكن تحقيق تسريع من خلال تنفيذ التكرارات بطريقة متسلسلة، مما يمنحنا وقت تنفيذ قدره${\displaystyle T_{s_{1}}+n\cdot T_{s_{2}}}$.

تُطبّق خوارزمية DOPIPE التوازي المُتدرّج لمعالجة التبعية المُتوارثة في الحلقات، حيث يتم توزيع تكرار الحلقة على حلقات مُتزامنة مُتعددة. ^{[ 1 ]} يهدف DOPIPE إلى العمل كخط تجميع، حيث تبدأ كل مرحلة بمجرد توفر بيانات كافية لها من المرحلة السابقة. ^{[ 6 ]}

ضع في اعتبارك الكود المتزامن التالي مع وجود تبعية s1[i] ->T s1[i + 1].

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += a [ i ]; // s2 }

يجب تنفيذ s1 بالتسلسل، بينما لا تعتمد s2 على حلقة تكرارية. يمكن تنفيذ s2 بالتوازي باستخدام DOALL Parallelism بعد إجراء جميع العمليات الحسابية اللازمة لـ s1 بالتسلسل. مع ذلك، يكون تحسين السرعة محدودًا في هذه الحالة. يتمثل النهج الأفضل في التوازي بحيث يتم تنفيذ s2 المقابل لكل s1 عند انتهاء s1.

يؤدي تطبيق التوازي المتسلسل إلى مجموعة الحلقات التالية، حيث يمكن تنفيذ الحلقة الثانية لفهرس بمجرد أن تنتهي الحلقة الأولى من فهرسها المقابل.

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 post ( i ); }for ( int i = 1 ; i < n ; i ++ ) { wait ( i ); c [ i ] += a [ i ]; // s2 }

لنفترض أن وقت تنفيذ s1 و s2 هو${\displaystyle T_{s_{1}}}$و${\displaystyle T_{s_{2}}}$إذن، يكون وقت تنفيذ الشكل التسلسلي للكود أعلاه هو${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$والآن، بفضل وجود التوازي في DOPIPE، يمكن تحقيق تسريع من خلال تنفيذ التكرارات بطريقة متسلسلة، مما يمنحنا وقت تنفيذ قدره${\displaystyle n\cdot T_{s_{1}}+({\frac {n}{p}})\cdot T_{s_{2}}}$، حيث يمثل p عدد المعالجات المتوازية.