قانون أمدال

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 37 صور
الموسوعة الحرة
يوضح قانون أمدال الحد الأقصى النظري لتسريع النظام ككل ومفهوم تناقص العوائد. يوضح الرسم البياني هنا العلاقة بين التوازي اللوغاريتمي والتسريع الخطي. إذا أمكن توازي 50% من العمل، فإن أفضل تسريع ممكن هو ضعفين. أما إذا أمكن توازي 95% من العمل، فإن أفضل تسريع ممكن هو 20 ضعفًا. ووفقًا للقانون، حتى مع عدد لا نهائي من المعالجات، يظل التسريع محدودًا بالجزء غير القابل للتوازي.

في هندسة الحاسوب ، قانون أمدال (أو حجة أمدال [ 1 ] ) هو صيغة تحد من تسريع المهمة عند إضافة موارد إلى النظام الذي ينفذ تلك المهمة.

يمكن صياغة القانون على النحو التالي :

إن التحسن العام في الأداء الذي يتم تحقيقه من خلال تحسين جزء واحد من النظام محدود بنسبة الوقت الذي يتم فيه استخدام الجزء المحسن فعليًا. [ 2 ]

وقد سميت على اسم عالم الكمبيوتر جين أمدال ، وتم تقديمها في المؤتمر المشترك الربيعي للحاسوب التابع للاتحاد الأمريكي لجمعيات معالجة المعلومات (AFIPS) في عام 1967.

يُستخدم قانون أمدال غالبًا في الحوسبة المتوازية للتنبؤ بالتسارع النظري عند استخدام معالجات متعددة.

تعريف

في سياق قانون أمدال، يمكن تعريف التسريع على النحو التالي: [ 3 ]

تسريع=أداء المهمة بأكملها عند تطبيق التحسيناتالأداء لنفس المهمة بدون تلك التحسينات{\displaystyle {\text{التحسين}}={\frac {\text{أداء المهمة بأكملها عند تطبيق التحسينات}}{\text{أداء المهمة نفسها بدون تلك التحسينات}}}}

أو

تسريع=وقت تنفيذ المهمة بأكملها بدون تحسيناتوقت تنفيذ المهمة نفسها عند تطبيق التحسينات{\displaystyle {\text{التحسين}}={\frac {\text{وقت تنفيذ المهمة بأكملها بدون تحسينات}}{\text{وقت تنفيذ نفس المهمة عند تطبيق التحسينات}}}}

يمكن صياغة قانون أمدال بالطريقة التالية: [ 4 ]

تسريعإجمالي=1(1-وقتمُحسَّن)+وقتمُحسَّنتسريعمُحسَّن{\displaystyle {\text{Speedup}}_{\text{overall}}={\frac {1}{(1-{\text{time}}_{\text{optimized}})+{\frac {{\text{time}}_{\text{optimized}}}{{\text{speedup}}_{\text{optimized}}}}}}}

أين

  • تسريعإجمالي{\displaystyle {\text{Speedup}}_{\text{overall}}}يمثل إجمالي تسريع البرنامج
  • وقتمُحسَّن{\displaystyle {\text{Time}}_{\text{optimized}}}يمثل هذا النسبة المئوية للوقت الذي يقضيه المستخدم في جزء الكود الذي يتم فيه إجراء التحسينات
  • تسريعمُحسَّن{\displaystyle {\text{Speedup}}_{\text{optimized}}}يمثل مدى التحسن

التسريعإجمالي{\displaystyle {\text{Speedup}}_{\text{overall}}}غالباً ما يكون وقت التنفيذ أقل بكثير مما قد يتوقعه المرء. على سبيل المثال، إذا قام مبرمج بتحسين جزء من الكود الذي يمثل 10% من إجمالي وقت التنفيذ (أيوقتمُحسَّن{\displaystyle {\text{Time}}_{\text{optimized}}}(0.10) ويحقق تسريعمُحسَّن{\displaystyle {\text{Speedup}}_{\text{optimized}}}من أصل 10000، ثم تسريعإجمالي{\displaystyle {\text{Speedup}}_{\text{overall}}}يصبح 1.11، مما يعني تحسنًا بنسبة 11% فقط في سرعة البرنامج الإجمالية. لذا، على الرغم من التحسن الكبير في قسم واحد، فإن الفائدة الإجمالية ضئيلة للغاية. في مثال آخر، إذا قام المبرمج بتحسين قسم يمثل 99% من وقت التنفيذ (أيوقتمُحسَّن{\displaystyle {\text{Time}}_{\text{optimized}}}(0.99) مع عامل تسريع قدره 100 (أيتسريعمُحسَّن{\displaystyle {\text{Speedup}}_{\text{optimized}}}من أصل 100)، الـتسريعإجمالي{\displaystyle {\text{Speedup}}_{\text{overall}}}لا تتجاوز النسبة 50. وهذا يشير إلى أن نصف الزيادة المحتملة في الأداء (تسريعإجمالي{\displaystyle {\text{Speedup}}_{\text{overall}}}سيصل إلى 100 إذا تم تغطية 100% من وقت التنفيذ) ويُفقد بسبب نسبة الـ 1% المتبقية من وقت التنفيذ التي لم يتم تحسينها. [ 4 ]

الاشتقاق

A task executed by a system whose resources are improved compared to an initial similar system can be split up into two parts:

  • a part that does not benefit from the improvement of the resources of the system;
  • a part that benefits from the improvement of the resources of the system.

An example is a computer program that processes files. A part of that program may scan the directory of the disk and create a list of files internally in memory. After that, another part of the program passes each file to a separate thread for processing. The part that scans the directory and creates the file list cannot be sped up on a parallel computer, but the part that processes the files can.

The execution time of the whole task before the improvement of the resources of the system is denoted as T{\displaystyle T}. It includes the execution time of the part that would not benefit from the improvement of the resources and the execution time of the one that would benefit from it. The fraction of the execution time of the task that would benefit from the improvement of the resources is denoted by p{\displaystyle p}. The one concerning the part that would not benefit from it is therefore 1−p{\displaystyle 1-p}. Then:

T=(1−p)T+pT.{\displaystyle T=(1-p)T+pT.}

It is the execution of the part that benefits from the improvement of the resources that is accelerated by the factor s{\displaystyle s} after the improvement of the resources. Consequently, the execution time of the part that does not benefit from it remains the same, while the part that benefits from it becomes:

psT.{\displaystyle {\frac {p}{s}}T.}

The theoretical execution time T(s){\displaystyle T(s)} of the whole task after the improvement of the resources is then:

T(s)=(1−p)T+psT.{\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}

Amdahl's law gives the theoretical speedup in latency of the execution of the whole task at fixed workload W{\displaystyle W}, which yields

Slatency(s)=TWT(s)W=TT(s)=11−p+ps.{\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.}

Parallel programs

If 30% of the execution time may be the subject of a speedup, p will be 0.3; if the improvement makes the affected part twice as fast, s will be 2. Amdahl's law states that the overall speedup of applying the improvement will be:

Slatency=11−p+ps=11−0.3+0.32=1.18.{\displaystyle S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac {0.3}{2}}}}=1.18.}

For example, assume that we are given a serial task which is split into four consecutive parts, whose percentages of execution time are p1 = 0.11, p2 = 0.18, p3 = 0.23, and p4 = 0.48 respectively. Then we are told that the 1st part is not sped up, so s1 = 1, while the 2nd part is sped up 5 times, so s2 = 5, the 3rd part is sped up 20 times, so s3 = 20, and the 4th part is sped up 1.6 times, so s4 = 1.6. By using Amdahl's law, the overall speedup is

Slatency=1p1s1+p2s2+p3s3+p4s4=10.111+0.185+0.2320+0.481.6=2.19.{\displaystyle S_{\text{latency}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}}}=2.19.}

لاحظ كيف أن التسريع بمقدار 5 مرات و 20 مرة في الجزأين الثاني والثالث على التوالي ليس له تأثير كبير على التسريع الإجمالي عندما يتم تسريع الجزء الرابع (48٪ من وقت التنفيذ) بمقدار 1.6 مرة فقط.

البرامج المتسلسلة

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

على سبيل المثال، مع برنامج تسلسلي مكون من جزأين A و B حيث T A = 3 ثوانٍ و T B = 1 ثانية ،

  • إذا تم تشغيل الجزء B بسرعة أكبر بخمس مرات، أي s = 5 و p = T B /( T A + T B ) = 0.25 ، فإنSكمون=11-0.25+0.255=1.25؛{\displaystyle S_{\text{latency}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;}
  • إذا تم تشغيل الجزء أ بسرعة مضاعفة، أي s = 2 و p = T A /( T A + T B ) = 0.75 ، فإنSكمون=11-0.75+0.752=1.60.{\displaystyle S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.}

لذا، فإن جعل الجزء (أ) يعمل بسرعة مضاعفة أفضل من جعل الجزء (ب) يعمل بسرعة مضاعفة خمس مرات. ويمكن حساب النسبة المئوية للتحسن في السرعة على النحو التالي:

نسبة التحسن=100(1-1Sكمون).{\displaystyle {\text{percentage improvement}}=100\left(1-{\frac {1}{S_{\text{latency}}}}\right).}
  • سيؤدي تحسين الجزء أ بمعامل 2 إلى زيادة سرعة البرنامج الإجمالية بمعامل 1.60، مما يجعله أسرع بنسبة 37.5٪ من الحساب الأصلي.
  • ومع ذلك، فإن تحسين الجزء ب بمقدار 5 أضعاف، والذي من المفترض أن يتطلب المزيد من الجهد، سيحقق عامل تسريع إجمالي قدره 1.25 فقط، مما يجعله أسرع بنسبة 20٪.

تحسين الجزء التسلسلي من البرامج المتوازية

إذا تم تحسين الجزء غير القابل للتوازي بمعامل منيا{\displaystyle O}، ثم

تي(يا،s)=(1-ص)تييا+صsتي.{\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}

يستنتج من قانون أمدال أن التسارع الناتج عن التوازي يُعطى بالصيغة التالية:

Sكمون(يا،s)=تي(يا)تي(يا،s)=(1-ص)1يا+ص1-صيا+صs.{\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}

متىs=1{\displaystyle s=1}لديناSكمون(يا،s)=1{\displaystyle S_{\text{latency}}(O,s)=1}، مما يعني أن التسارع يتم قياسه بالنسبة لوقت التنفيذ بعد تحسين الجزء غير القابل للتوازي.

متى s=∞{\displaystyle s=\infty }،

Sكمون(يا،∞)=تي(يا)تي(يا،s)=(1-ص)1يا+ص1-صيا+صs=1+ص1-صيا.{\displaystyle S_{\text{latency}}(O,\infty )={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p}}O.}

لو 1-ص=0.4{\displaystyle 1-p=0.4}،يا=2{\displaystyle O=2}وs=5{\displaystyle s=5}، ثم:

Sكمون(يا،s)=تي(يا)تي(يا،s)=0.412+0.60.42+0.65=2.5.{\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0.4}{\frac {1}{2}}+0.6}{{\frac {0.4}{2}}+{\frac {0.6}{5}}}}=2.5.}

تحويل الأجزاء المتسلسلة من البرامج المتوازية إلى أجزاء قابلة للتوازي

بعد ذلك، سننظر في الحالة التي يتم فيها تقليل الجزء غير القابل للتوازي بمعامل قدرهيا′{\displaystyle O'}وبالتالي، يزداد الجزء القابل للتوازي تبعاً لذلك.

تي′(يا′،s)=1-صيا′تي+(1-1-صيا′)تيs.{\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}

يستنتج من قانون أمدال أن التسارع الناتج عن التوازي يُعطى بالصيغة التالية:

Sكمون′(يا′،s)=تي′(يا′)تي′(يا′،s)=11-صيا′+(1-1-صيا′)1s.{\displaystyle S'_{\text{latency}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{{\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}

العلاقة بقانون تناقص الغلة

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

يمثل قانون أمدال قانون تناقص الغلة عند النظر في العائد الناتج عن إضافة المزيد من المعالجات إلى جهاز ما، في حال تشغيل عملية حسابية ثابتة الحجم تستخدم جميع المعالجات المتاحة بكامل طاقتها. كل معالج جديد يُضاف إلى النظام يُضيف طاقة قابلة للاستخدام أقل من سابقه. ومع كل مضاعفة لعدد المعالجات، تتناقص نسبة التسريع، حيث يقترب إجمالي الإنتاجية من الحد الأقصى 1/(1  − p ). 

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

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

انظر أيضاً

مراجع

  1. ↑ رودجرز، ديفيد ب. (يونيو 1985). "تحسينات في تصميم أنظمة المعالجات المتعددة". أخبار هندسة الحاسوب الصادرة عن جمعية آلات الحوسبة (ACM) SIGARCH . 13 (3). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM : 225-231 [ص 226]. doi : 10.1145/327070.327215 . ISBN 0-8186-0634-7ISSN 0163-5964 . S2CID 7083878 .​  
  2. ↑ ريدي، مارتن (2011). تصميم واجهات برمجة التطبيقات للغة C++ . بيرلينجتون، ماساتشوستس : دار مورغان كوفمان للنشر . ص 210. doi : 10.1016/C2010-0-65832-9 . ISBN  978-0-12-385003-4. LCCN 2010039601 . OCLC 666246330 .  
  3. ↑ هندسة الحاسوب: منهج كمي . مورغان كوفمان. 2003. ISBN 978-8178672663.
  4. 1 2 باكوس، جيسون د. (2016-01-01)، "الفصل 2 - تحسين متعدد النوى ومستوى البيانات: OpenMP وSIMD" ، في باكوس، جيسون د. (محرر)، الأنظمة المدمجة ، بوسطن: مورغان كوفمان، ص 49-103 ، doi : 10.1016/b978-0-12-800342-8.00002-x ، ISBN  978-0-12-800342-8تم الاطلاع عليه بتاريخ 18 نوفمبر 2024
  5. ↑ هيل، مارك د.؛ مارتي، مايكل ر. (2008). "قانون أمدال في عصر المعالجات متعددة النوى". مجلة الكمبيوتر . 41 (7): 33-38 . رمز Bibcode : 2008Compr..41g..33H . CiteSeerX 10.1.1.221.8635 . doi : 10.1109/MC.2008.209 . 
  6. ↑ رافيف، آشور؛ الحياني، محمد أ.ن؛ شيا، فاي؛ شفيق، رشاد؛ رومانوفسكي، ألكسندر؛ ياكوفليف، أليكس (2018-07-01). "نماذج تسريع وتوسيع نطاق الطاقة لأنظمة متعددة النوى غير متجانسة". معاملات IEEE لأنظمة الحوسبة متعددة المقاييس . 4 (3): 436-449 . doi : 10.1109/TMSCS.2018.2791531 . ISSN 2332-7766 . S2CID 52287374 .  
  7. ↑ الحياني، محمد أ. نعمان؛ شيا، فاي؛ رافيف، آشور؛ رومانوفسكي، ألكسندر؛ شفيق، رشاد؛ ياكوفليف، أليكس (يوليو 2020). "قانون أمدال في سياق الأنظمة متعددة النوى غير المتجانسة - دراسة استقصائية" . مجلة IET للحاسبات والتقنيات الرقمية . 14 (4): 133-148 . doi : 10.1049/iet-cdt.2018.5220 . ISSN 1751-8601 . S2CID 214415079 .  

للمزيد من القراءة