الخصخصة (برمجة الحاسوب)

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
الموسوعة الحرة

التخصيص هو أسلوب يُستخدم في برمجة الذاكرة المشتركة لتمكين التوازي ، وذلك بإزالة التبعيات التي تحدث بين الخيوط المختلفة في البرنامج المتوازي . تنشأ التبعيات بين الخيوط عندما يقوم خيطان أو أكثر بقراءة أو كتابة متغير في الوقت نفسه. يمنح التخصيص كل خيط نسخة خاصة، بحيث يمكنه قراءتها وكتابتها بشكل مستقل، وبالتالي في آن واحد. [ 1 ]

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

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

وصف

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

تتمثل الخطوة التالية في تحديد نطاق المتغيرات المستخدمة في برنامج متوازٍ، وهو أحد الخطوات الرئيسية والاهتمامات الأساسية ضمن هذا النموذج.

نطاق متغير

تتمثل الخطوة التالية في النموذج في تجميع المهام في مهام أكبر، حيث يكون عدد المهام عادةً أكبر من عدد المعالجات المتاحة. وعادةً ما يتم اختيار عدد سلاسل التنفيذ التي تُخصص لها المهام بحيث يكون أقل من أو يساوي عدد المعالجات، مع تخصيص كل سلسلة لمعالج فريد. [ 1 ]

مباشرةً بعد هذه الخطوة، يجب تحليل استخدام المتغيرات داخل المهام. تحدد هذه الخطوة ما إذا كان ينبغي مشاركة كل متغير بين جميع العمليات أم أن يكون خاصًا بكل عملية. [ 1 ] هذه الخطوة خاصة ببرمجة الذاكرة المشتركة. (يُعدّ تمرير الرسائل بديلاً ، حيث تكون جميع المتغيرات خاصة). [ 1 ]

وبناءً على سلوكها، يتم تصنيف المتغيرات على النحو التالي:

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

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

الخصخصة

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

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

هناك حالتان يمكن فيهما وصف متغير ما بأنه قابل للخصخصة :

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

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

القيود

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

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

المصفوفات

يمكن أن تكون المتغيرات المتضاربة في القراءة والكتابة من النوع القياسي أو المركب، مثل المصفوفات والأنواع المهيكلة وما إلى ذلك. ويمكن تطبيق مبدأ الخصوصية على كلا النوعين من المتغيرات.

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

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

أمثلة

المثال 1

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

//الرمز التسلسلي: x = a; أ = ب؛ ب = س؛ x = c; ج = د؛ د = س؛ x = e; e = f; ب = س؛

لا يمكن تشغيل هذا الكود بالتوازي دون تخصيصه x. بعد xالتخصيص، يمكن تشغيله على ثلاثة خيوط مختلفة، لكل منها خيط خاص به x.

//كود متوازي: //الخيط 1: x[1] = a; أ = ب؛ ب = س[1]؛ // الخيط 2: x[2] = c; ج = د؛ د = س[2]؛ // الخيط 3: x[3]= e; e = f; ب = س[3]؛

المثال 2

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

//الرمز التسلسلي: x = 1; ص = س * 3؛ x = 4؛ z = y/x; أ = س * 9؛ x = 3؛ ب = أ/س؛ ج = س * 1؛ x = 11؛ د = ج/س؛

لجعل الكود التسلسلي أعلاه متوازياً، يجب إضافة بضعة أسطر من الكود بحيث xيمكن جعله خاصاً:

//كود متوازي //الخيط 0: x[0] = 1; y = x[0] * 3; x[0] = 4; z = y/x[0]; //الخيط 1: x[1] = 4; أ = س[1] * 9؛ x[1] = 3; ب = أ/س[1]؛ //الخيط 2: x[2] = 3; ج = س[2] * 1؛ x[2] = 11; د = ج/س[2]؛

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

المثال 3

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

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

//الرمز التسلسلي: المجموع = 0؛ for (i = 0; i < 100; i++) sum += a[i];

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

// الخيط 0: sum[0] = 0; for (i[0] = 0; i[0] < 100; i[0] += 3) sum[0] += a[i[0]]; // الخيط 1: sum[1] = 0; for (i[1] = 1; i[1] < 100; i[1] += 3) sum[1] += a[i[1]]; // الخيط 2: sum[2] = 0; for (i[2] = 2; i[2] < 100; i[2] += 3) sum[2] += a[i[2]]; // الخيط "الرئيسي": wait_for_all(thread[0], thread[1], thread[2]); المجموع = المجموع[0] + المجموع[1] + المجموع[2]؛

OpenMP

OpenMP هي لغة برمجة تدعم البرمجة متعددة المعالجات مع الذاكرة المشتركة. ولهذا السبب، من المؤكد حدوث تعارضات في عمليات القراءة والكتابة للمتغيرات. في هذه الحالات، يمكن أحيانًا استخدام التخصيص للسماح بتنفيذ التعليمات البرمجية بالتوازي.

بالنظر إلى الرمز التسلسلي:

 do i = 10, N - 1 س = (ب(i) + ج(i))/2 ب(i) = أ(i + 1) + س com.enddo

في كل تكرار للحلقة، xتُكتب قيمة المتغير ثم تُقرأ منه. ولأن xالمتغير عددي فقط، لا يمكن تنفيذ الحلقة بالتوازي لأنه سيتم استبدال قيمته في خيوط معالجة مختلفة، ولن b(i)تُسند إليه القيمة الصحيحة دائمًا. [ 2 ]

الكود المكافئ المتوازي باستخدام الخصخصة هو:

 !$omp parallel do shared(a, b) private(x) do i = 10, N - 1 س = (ب(i) + ج(i))/2 ب(i) = أ(i + 1) + س com.enddo

بما أن xالمتغير مُعلن عنه كمتغير خاص، فإن كل سلسلة عمليات تحصل على نسختها الخاصة ويتم إزالة التبعية. [ 2 ]

مقارنة بالتقنيات الأخرى

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

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

بالمقارنة مع الاختزال، تتطلب الخصخصة خطوة نمذجة واحدة فقط: تحليل الكود لتحديد المتغيرات القابلة للخصخصة. في المقابل، تتطلب عملية الاختزال خطوتين: تحديد متغير الاختزال، ثم تنفيذ عملية الاختزال بالتوازي. [ 7 ] من خلال ملاحظة كلتا التقنيتين، يسهل تحديد نوع العبء الإضافي الذي تضيفه كل منهما إلى البرنامج المتوازي؛ فالاختزال يزيد من عبء الحساب، بينما تزيد الخصخصة من الذاكرة التي يستهلكها البرنامج. [ 5 ]

بالمقارنة مع التوسع، تتطلب الخصخصة مساحة ذاكرة أقل. تتناسب مساحة الذاكرة المطلوبة للخصخصة طرديًا مع عدد المعالجات، بينما في التوسع، تتناسب طرديًا مع عدد التكرارات. [ 5 ] ولأن عدد المهام عادةً ما يكون أكبر من عدد المعالجات، فإن الذاكرة المطلوبة للتوسع أكبر بكثير من تلك المطلوبة للخصخصة.

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

انظر أيضاً

مراجع

  1. 1 2 3 4 5 6 7 8 9 سوليهين، يان (2015). أساسيات بنية المعالجات متعددة النوى المتوازية . تشابمان آند هول/سي آر سي. ISBN 978-1-4822-1118-4.
  2. 1 2 3 تشاندرا، روهيت (2001). بنروز، دينيس (محرر). البرمجة المتوازية في OpenMP (ملف PDF) . مورغان كوفمان . الصفحات 48، 74، 143. ISBN  978-1-55860-671-5.
  3. ↑ غوبتا، م. (1997-04-01). "حول خصخصة المتغيرات للتنفيذ المتوازي للبيانات". وقائع الندوة الدولية الحادية عشرة للمعالجة المتوازية . الصفحات 533-541 . CiteSeerX 10.1.1.50.2508 . doi : 10.1109/IPPS.1997.580952 . ISBN   978-0-8186-7793-9. S2CID 17389658 . 
  4. 1 2 سيز، لويس هـ. (2011-01-01). "المعالجات المتعددة ذات الذاكرة المشتركة". في بادوا، ديفيد (محرر). موسوعة الحوسبة المتوازية . سبرينغر الولايات المتحدة. ص 1810-1812 . doi : 10.1007/978-0-387-09766-4_142 . ISBN  978-0-387-09765-7.
  5. 1 2 3 4 بادوا، ديفيد (2011-01-01). "التوازي التلقائي". في بادوا، ديفيد (محرر). موسوعة الحوسبة المتوازية . سبرينغر الولايات المتحدة. الصفحات 1442-1450 - بتصرف بروس ليجر. doi : 10.1007/978-0-387-09766-4_197 . ISBN  978-0-387-09765-7.
  6. ↑ تو، بينغ؛ بادوا، ديفيد (12 أغسطس 1993). "التخصيص التلقائي للمصفوفات". في: بانيرجي، أوتال؛ جيلرنتر، ديفيد ؛ نيكولاو، أليكس؛ بادوا، ديفيد (محررون). لغات ومترجمات الحوسبة المتوازية . سلسلة محاضرات في علوم الحاسوب. سبرينغر برلين هايدلبرغ. الصفحات 500-521 . CiteSeerX 10.1.1.3.5746 . doi : 10.1007/3-540-57659-2_29 . ISBN   978-3-540-57659-4.
  7. ↑ يو، هاو؛ راوخويرجر، لورانس (1 يناير 2014). "تقنيات التوازي بالاختزال التكيفي". المجلد الخامس والعشرون من المؤتمر الدولي للحوسبة الفائقة التابع لجمعية آلات الحوسبة . نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 311-322 . doi : 10.1145/2591635.2667180 . ISBN  978-1-4503-2840-1. S2CID 52865514 .