قانون أمدال

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 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 ]

الاشتقاق

يمكن تقسيم المهمة التي ينفذها نظام تم تحسين موارده مقارنة بنظام مماثل أولي إلى جزأين:

  • جزء لا يستفيد من تحسين موارد النظام؛
  • جزء يستفيد من تحسين موارد النظام.

مثال على ذلك برنامج حاسوبي يعالج الملفات. قد يقوم جزء من هذا البرنامج بمسح دليل القرص وإنشاء قائمة بالملفات داخليًا في الذاكرة. بعد ذلك، يمرر جزء آخر من البرنامج كل ملف إلى عملية معالجة منفصلة. لا يمكن تسريع الجزء الذي يمسح الدليل وينشئ قائمة الملفات على حاسوب متوازٍ، ولكن يمكن تسريع الجزء الذي يعالج الملفات.

يُشار إلى وقت تنفيذ المهمة بأكملها قبل تحسين موارد النظام بـتي{\displaystyle T}يشمل ذلك وقت تنفيذ الجزء الذي لن يستفيد من تحسين الموارد، ووقت تنفيذ الجزء الذي سيستفيد منه. ويُرمز إلى نسبة وقت تنفيذ المهمة التي ستستفيد من تحسين الموارد بـص{\displaystyle p}أما الجزء الذي لن يستفيد منه فهو بالتالي1-ص{\displaystyle 1-p}. ثم:

تي=(1-ص)تي+صتي.{\displaystyle T=(1-p)T+pT.}

إن تنفيذ الجزء الذي يستفيد من تحسين الموارد هو الذي يتسارع بفعل هذا العاملs{\displaystyle s}بعد تحسين الموارد. ونتيجة لذلك، يبقى وقت تنفيذ الجزء الذي لا يستفيد من ذلك كما هو، بينما يصبح وقت تنفيذ الجزء الذي يستفيد منه كما يلي:

صsتي.{\displaystyle {\frac {p}{s}}T.}

الوقت النظري للتنفيذتي(s){\displaystyle T(s)}ثم يصبح مجمل المهمة بعد تحسين الموارد كما يلي:

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

ينص قانون أمدال على التسارع النظري في زمن استجابة تنفيذ المهمة بأكملها عند ثبات حجم العملدبليو{\displaystyle W}، مما ينتج عنه

Sكمون(s)=تيدبليوتي(s)دبليو=تيتي(s)=11-ص+صs.{\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.}

البرامج المتوازية

إذا كان 30% من وقت التنفيذ قابلاً للتحسين، فإن قيمة p ستكون 0.3؛ وإذا جعل التحسين الجزء المتأثر أسرع بمرتين، فإن قيمة s ستكون  2. ينص قانون أمدال على أن التسريع الإجمالي لتطبيق التحسين سيكون:

Sكمون=11-ص+صs=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.}

على سبيل المثال، لنفترض أن لدينا مهمة متسلسلة مقسمة إلى أربعة أجزاء متتالية، بنسب زمنية للتنفيذ هي p1 = 0.11 ، وp2 = 0.18 ، و p3 = 0.23 ، و p4 = 0.48 على التوالي. علمنا أن الجزء الأول لم يتم تسريعه، أي s1 = 1 ، بينما تم تسريع الجزء الثاني 5 مرات، أي s2 = 5 ، وتم تسريع الجزء الثالث 20 مرة، أي s3 = 20 ، وتم تسريع الجزء الرابع 1.6 مرة، أي s4 = 1.6 . باستخدام قانون أمدال، يكون التسريع الإجمالي هو

Sكمون=1ص1s1+ص2s2+ص3s3+ص4s4=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 .  

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