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

في علم الحاسوب ، تُعرَّف الخوارزمية المتوازية ، على عكس الخوارزمية التسلسلية التقليدية ، بأنها خوارزمية قادرة على تنفيذ عمليات متعددة في فترة زمنية محددة. وقد جرت العادة في علم الحاسوب على وصف الخوارزميات التسلسلية باستخدام نماذج الآلات المجردة ، وغالبًا ما يكون النموذج المعروف باسم آلة الوصول العشوائي . وبالمثل، استخدم العديد من باحثي علم الحاسوب ما يُسمى بآلة الوصول العشوائي المتوازية (PRAM) كآلة مجردة متوازية (ذاكرة مشتركة). ^{[ 1 ] [ 2 ]}

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

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

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

بعض المشكلات لا يمكن تقسيمها إلى أجزاء متوازية، لأنها تتطلب نتائج خطوة سابقة للمضي قدمًا بفعالية في الخطوة التالية - وتسمى هذه المشكلات بـتُعدّ المسائل التسلسلية بطبيعتها مسائل. ومن الأمثلة على ذلكالطرق العددية، مثلطريقة نيوتن، والحلول التكرارية لمسألةالأجسام الثلاثة، ومعظم الخوارزميات المتاحة لحسابباي(π).ويمكن تحويل بعض الخوارزميات التسلسلية إلى خوارزميات متوازية باستخدامالتوازي التلقائي. ^{[ 3 ]}

في كثير من الحالات، يتطلب تطوير خوارزمية متوازية فعالة لحل مهمة ما ابتكار أفكار وأساليب جديدة لا تُستخدم في تصميم خوارزمية تسلسلية لحل المشكلة نفسها. ومن أمثلة هذه الحالات، المشكلات ذات الأهمية العملية، مثل البحث عن عنصر مستهدف في بنية بيانات، وتقييم تعبير جبري. ^{[ 4 ]}

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

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

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

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

تتمتع الخوارزميات الموزعة بالعديد من التطبيقات العملية في قواعد البيانات الموزعة، وأنظمة تحمل الأعطال، والتطبيقات الشبكية واسعة النطاق.

• نظام متعدد العوامل (MAS)
• خوارزميات متوازية لضرب المصفوفات
• خوارزميات متوازية للأشجار الممتدة الدنيا
• الحوسبة المتوازية
• باراريال

• تصميم وبناء برامج متوازية ، مختبر أرغون الوطني الأمريكي