قانون غوستافسون

في هندسة الحاسوب ، يُحدد قانون غوستافسون (أو قانون غوستافسون-بارسيس ^{[ 1 ]} ) مقدار التسارع في زمن تنفيذ مهمة ما، والذي يُفترض نظريًا أنه يتحقق من خلال الحوسبة المتوازية ، وذلك باستخدام تشغيل افتراضي للمهمة على معالج أحادي النواة كخط أساس. بعبارة أخرى، هو التباطؤ النظري لمهمة مُوازية بالفعل عند تشغيلها على معالج تسلسلي. سُمي القانون نسبةً إلى عالم الحاسوب جون إل. غوستافسون وزميله إدوين إتش. بارسيس، وعُرض في مقال " إعادة تقييم قانون أمدال" عام 1988. ^{[ 2 ]}

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

وقدّر غوستافسون التسارع${\displaystyle S}$برنامج تم الحصول عليه باستخدام الحوسبة المتوازية على النحو التالي:

$${\displaystyle {\begin{aligned}S&=s+p\times N\\&=s+(1-s)\times N\\&=N+(1-N)\times s\\&=N-(N-1)\times s\end{aligned}}}$$

أين

• ${\displaystyle S}$هو التسريع النظري للبرنامج مع التوازي (التسريع المقياس ^{[ 2 ]} )؛
• ${\displaystyle N}$هو عدد المعالجات؛
• ${\displaystyle s}$و${\displaystyle p}$تمثل هذه النسب الزمنية الوقت المستغرق في تنفيذ الأجزاء التسلسلية والأجزاء المتوازية من البرنامج، على التوالي، على النظام المتوازي ، حيث${\displaystyle s+p=1}$.

بدلاً عن ذلك،${\displaystyle S}$يمكن التعبير عنها باستخدام${\displaystyle p}$:

$${\displaystyle {\begin{aligned}S&=(1-p)+p\times N\\&=1+(N-1)\times p\end{aligned}}}$$

يعالج قانون غوستافسون أوجه القصور في قانون أمدال ، الذي يقوم على افتراض ثبات حجم المشكلة ، أي أن عبء التنفيذ لا يتغير مع ازدياد الموارد. وبدلاً من ذلك، يقترح قانون غوستافسون أن المبرمجين يميلون إلى زيادة حجم المشكلات للاستفادة الكاملة من القدرة الحاسوبية المتاحة مع ازدياد الموارد. ^{[ 2 ]}

لاحظ غوستافسون وزملاؤه أيضًا من خلال أعباء العمل الخاصة بهم أن الوقت المخصص للجزء التسلسلي لا يزداد عادةً مع حجم المشكلة وحجم النظام، ^{[ 2 ]} أي${\displaystyle s}$ثابت. وهذا يعطي نموذجًا خطيًا بين عدد المعالجات${\displaystyle N}$والتسارع${\displaystyle S}$مع ميل${\displaystyle 1-s}$كما هو موضح في الشكل أعلاه (الذي يستخدم رموزًا مختلفة):${\displaystyle P}$ل${\displaystyle N}$و${\displaystyle a}$ل${\displaystyle s}$). أيضًا،${\displaystyle S}$يتناسب خطيًا مع${\displaystyle s}$بدلاً من النمو الأسي وفقًا لقانون أمدال. ^{[ 2 ]} مع هذه الملاحظات، توقع غوستافسون "توسيع نطاق نجاحهم [في الحوسبة المتوازية] ليشمل مجموعة أوسع من التطبيقات وقيمًا أكبر لـ${\displaystyle N}$[ ^{2 ]​}

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

يمكن تقسيم وقت تنفيذ برنامج يعمل على نظام متوازٍ إلى جزأين:

• جزء لا يستفيد من العدد المتزايد للمعالجات (جزء تسلسلي)؛
• جزء يستفيد من العدد المتزايد للمعالجات (الجزء المتوازي).

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

دون الإخلال بعمومية المسألة، لنفترض أن إجمالي وقت التنفيذ على النظام المتوازي هو${\displaystyle T=1}$. لنرمز إلى الوقت التسلسلي بـ${\displaystyle s}$والزمن الموازي كـ${\displaystyle p}$، أين${\displaystyle s+p=1}$. لنرمز إلى عدد المعالجات بـ${\displaystyle N}$.

افتراضياً، عند تشغيل البرنامج على نظام تسلسلي (معالج واحد فقط)، سيظل الجزء التسلسلي يستغرق وقتاً.${\displaystyle s}$بينما يأخذ الجزء الموازي الآن${\displaystyle Np}$وقت التنفيذ على النظام التسلسلي هو:

$${\displaystyle T'=s+Np}$$ استخدام${\displaystyle T'}$كخط أساس، يكون تسارع النظام المتوازي كما يلي:

$${\displaystyle S={\frac {T'}{T}}={\frac {s+Np}{s+p}}={\frac {s+Np}{1}}=s+Np}$$

عن طريق الاستبدال${\displaystyle p=1-s}$أو${\displaystyle s=1-p}$، ويمكن اشتقاق العديد من الأشكال في القسم السابق.

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

قد تجد الخوارزميات ذات أوقات التشغيل غير الخطية صعوبة في الاستفادة من التوازي الذي يوفره قانون غوستافسون. يشير سنايدر ^{[ 3 ]} إلى${\displaystyle O(N^{3})}$تعني الخوارزمية أن مضاعفة التزامن لا تؤدي إلا إلى زيادة حجم المشكلة بنسبة 26% تقريبًا. وبالتالي، فبينما قد يكون من الممكن تحقيق تزامن هائل، إلا أن ذلك قد لا يُحقق فائدة تُذكر مقارنةً بالحل الأصلي الأقل تزامنًا، ومع ذلك، فقد شهدنا في الواقع تحسينات كبيرة.

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

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

• التوازي القابل للتوسع
• قانون باركنسون
• مفارقة جيفونز