تحليل الخوارزميات المتوازية

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

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

خلفية

طُوِّر إطار عمل يُعرف باسم "زمن العمل" (WT) (ويُسمى أحيانًا "عمق العمل" أو "مدى العمل") في الأصل من قِبَل شيلواخ وفيشكين [ 1 ] لتصور ووصف الخوارزميات المتوازية. في إطار عمل زمن العمل، تُوصَف الخوارزمية المتوازية أولًا من حيث الجولات المتوازية. في كل جولة، تُحدَّد العمليات المطلوب تنفيذها، ولكن يمكن إغفال بعض التفاصيل. على سبيل المثال، ليس من الضروري توضيح عدد العمليات في كل جولة، ولا ذكر المعالجات، ولا مراعاة أي معلومات قد تُساعد في تخصيص المعالجات للمهام. ثانيًا، تُقدَّم المعلومات المُغفلة. ويستند تضمين هذه المعلومات إلى برهان نظرية جدولة منسوبة إلى برنت [ 2 ] ، والتي سيتم شرحها لاحقًا في هذه المقالة. يُعد إطار عمل زمن العمل مفيدًا لأنه، على الرغم من قدرته على تبسيط الوصف الأولي للخوارزمية المتوازية بشكل كبير، فإن إدراج التفاصيل المُغفلة في ذلك الوصف الأولي غالبًا ما يكون سهلًا. على سبيل المثال، تم اعتماد إطار عمل WT كإطار عرض أساسي في كتب الخوارزميات المتوازية ( لنموذج آلة الوصول العشوائي المتوازية PRAM) [ 3 ] و [ 4 ] ، وكذلك في ملاحظات المحاضرات [ 5 ] . يوضح العرض التقديمي أدناه كيفية استخدام إطار عمل WT لتحليل خوارزميات متوازية أكثر عمومية، حتى عندما لا يتوفر وصفها ضمن إطار عمل WT.

التعريفات

لنفترض أن العمليات الحسابية تُنفذ على جهاز يحتوي على p معالج. ولنرمز بـ T<sub> p</sub> إلى الوقت المنقضي بين بداية العملية الحسابية ونهايتها. يركز تحليل وقت تشغيل العملية الحسابية على المفاهيم التالية:

  • يُعرَّف عمل عملية حسابية تُنفَّذ بواسطة p معالج بأنه إجمالي عدد العمليات الأولية التي تُجريها هذه المعالجات. [ 6 ] وبإهمال تكلفة الاتصال الناتجة عن مزامنة المعالجات، فإن هذا يساوي الوقت المُستخدَم لتشغيل العملية الحسابية على معالج واحد، ويُرمز له بـ T1 .
  • العمق أو المدى هو طول أطول سلسلة من العمليات التي يجب تنفيذها بالتتابع بسبب تبعيات البيانات (المسار الحرج ). يُمكن أيضًا تسمية العمقبطول المسار الحرجللحساب. [ 7 ] يُعدّ تقليل العمق/المدى أمرًا بالغ الأهمية في تصميم الخوارزميات المتوازية، لأنّ العمق/المدى يُحدّد أقصر وقت تنفيذ ممكن. [ 8 ] بدلاً من ذلك، يُمكن تعريف المدى على أنّه الوقت T∞ المُستغرق في الحساب باستخدام جهاز مثالي ذي عدد لا نهائي من المعالجات. [ 9 ]
  • تكلفة الحساب هي الكمية pT p . وهذا يعبر عن إجمالي الوقت الذي تستغرقه جميع المعالجات في كل من الحساب والانتظار. [ 6 ]

تترتب على تعريفات العمل والنطاق والتكلفة عدة نتائج مفيدة:

  • قانون العمل . التكلفة دائمًا لا تقل عن العمل: pT p ≥ T 1. وينتج هذا عن حقيقة أن p معالجًا يمكنها تنفيذ p عملية على الأكثر بالتوازي. [ 6 ] [ 9 ]
  • قانون المدى . لا يمكن لعدد محدود p من المعالجات أن يتفوق على عدد لا نهائي، بحيث يكون T p ≥ T ∞ . [ 9 ]

باستخدام هذه التعريفات والقوانين، يمكن تقديم مقاييس الأداء التالية:

  • يُعرَّف التسريع بأنه الزيادة في السرعة الناتجة عن التنفيذ المتوازي مقارنةً بالتنفيذ التسلسلي: S <sub>p</sub> = T <sub>1 </sub> / T <sub> p</sub> . عندما يكون التسريع Ω( p ) لعدد p من المعالجات (باستخدام ترميز Big O )، يكون التسريع خطيًا، وهو الأمثل في نماذج الحوسبة البسيطة لأن قانون العمل ينص على أن T<sub> 1</sub> / T <sub> p </sub> ≤ p ( قد يحدث تسريع فائق الخطية عمليًا بسبب تأثيرات التسلسل الهرمي للذاكرة ). تُسمىالحالة T<sub> 1</sub> / T <sub>p</sub> = p بالتسريع الخطي المثالي. [ 9 ] يُقال إن الخوارزمية التي تُظهر تسريعًا خطيًا قابلة للتوسع . [ 6 ] تُعرض في هذا الكتاب تعابير تحليلية لتسريع العديد من الخوارزميات المتوازية المهمة. [ 10 ]
  • الكفاءة هي زيادة السرعة لكل معالج، S p / p . [ 6 ]
  • التوازي هو النسبة T 1 / T ∞ . وهو يمثل أقصى تسارع ممكن على أي عدد من المعالجات. وبحسب قانون المدى، فإن التوازي يحد من التسارع: إذا كان p > T 1 / T ∞ ، فإن: [ 9 ]تي1تيص≤تي1تي∞<ص.{\displaystyle {\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p.}
  • التباطؤ هو T 1 / ( pT ∞ ) . التباطؤ الأقل من واحد يعني (بحسب قانون المدى) أن التسريع الخطي المثالي مستحيل على p معالج. [ 9 ]

التنفيذ على عدد محدود من المعالجات

عادةً ما يُجرى تحليل الخوارزميات المتوازية بافتراض توفر عدد غير محدود من المعالجات. هذا افتراض غير واقعي، ولكنه ليس مشكلة، إذ يمكن تنفيذ أي عملية حسابية قابلة للتنفيذ بالتوازي على N معالجًا على p < N معالجًا، وذلك بجعل كل معالج يُنفذ وحدات عمل متعددة. تنص نتيجة تُعرف بقانون برنت على أنه يمكن إجراء مثل هذه "المحاكاة" في زمن T p ، وهو زمن محدود بالمعادلة [ 11 ].

تيص≤تيشمال+تي1-تيشمالص،{\displaystyle T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},}

أو، بشكل أقل دقة، [ 6 ]

تيص=يا(تيشمال+تي1ص).{\displaystyle T_{p}=O\left(T_{N}+{\frac {T_{1}}{p}}\right).}

بيان بديل للقانون يحدد حدود T p من الأعلى والأسفل بواسطة

تي1ص≤تيص≤تي1ص+تي∞{\displaystyle {\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }}.

[ 2 ] يوضح أن الامتداد (العمق) T∞ والعمل T1 معًا يوفران حدودًا معقولة لوقت الحساب.

مراجع

  1. ↑ شيلواخ، يوسي؛ فيشكين، أوزي (1982). " خوارزمية تدفق أقصى متوازية من رتبة O(n²log n ) " . مجلة الخوارزميات . 3 ( 2): 128-146 . doi : 10.1016/0196-6774(82)90013-X .  
  2. 1 2 برنت، ريتشارد ب. (1974-04-01). "التقييم المتوازي للتعبيرات الحسابية العامة". مجلة ACM . 21 (2): 201-206 . CiteSeerX 10.1.1.100.9361 . doi : 10.1145/321812.321815 . ISSN 0004-5411 . S2CID 16416106 .   
  3. ↑ جاجا، جوزيف (1992). مقدمة في الخوارزميات المتوازية . أديسون-ويسلي. ISBN 978-0-201-54856-3.
  4. ^ كيلر ، يورج. كيسلر، كريستوف دبليو. تراف، جيسبر إل. (2001). برمجة PRAM العملية . وايلي إنترساينس. رقم ISBN 978-0-471-35351-5.
  5. ↑ فيشكين، أوزي (2009). التفكير بالتوازي: بعض الخوارزميات والتقنيات الأساسية للتوازي في البيانات، 104 صفحات (ملف PDF) . ملاحظات صفية لمقررات دراسية حول الخوارزميات المتوازية تُدرَّس منذ عام 1992 في جامعة ميريلاند، كوليدج بارك، وجامعة تل أبيب، ومعهد التخنيون.
  6. 1 2 3 4 5 6 كازانوفا، هنري؛ ليجراند، أرنو؛ روبرت، إيف (2008). الخوارزميات المتوازية . مطبعة سي آر سي. ص 10. CiteSeerX 10.1.1.466.8142 .  
  7. ↑ بليلوخ، جاي (1996). "برمجة الخوارزميات المتوازية" (ملف PDF) . مجلة اتصالات رابطة مكائن ​​الحوسبة . 39 (3): 85-97 . CiteSeerX 10.1.1.141.5884 . doi : 10.1145/227234.227246 . S2CID 12118850 .  
  8. ↑ مايكل ماكول؛ جيمس رايندرز؛ آرتش روبيسون (2013). البرمجة المتوازية المهيكلة: أنماط للحوسبة الفعالة . إلسيفير. ص 4-5 . 
  9. 1 2 3 4 5 6 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 779 – 784. ISBN   0-262-03384-4.
  10. ↑ كورغالين، سيرجي؛ بورزونوف، سيرجي (2020). كتاب تمارين الرياضيات المتقطعة: دليل مصاحب باستخدام بايثون . نصوص في علوم الحاسوب ( الطبعة الثانية). تشام، سويسرا: سبرينغر ناتشوريل. ISBN  978-3-030-42220-2.
  11. ↑ غوستافسون، جون ل. (2011). "نظرية برنت". موسوعة الحوسبة المتوازية . ص 182-185 . doi : 10.1007/978-0-387-09766-4_80 . ISBN  978-0-387-09765-7.