1- خوارزمية الإجراء : (510145)6,3 51501721171
2- خوارزمية الإجراء : (51714505 آم اتختتذط
4-4-3 تحليل خوارزمية المجاميع البادئة على شجرة
1- خوارزمية المعالج الورقة
2- تحليل خوارزمية المعالج الورقة
5-4-3 المجاميع البادئة على الشبكة :188
6-4-3 تحليل خوارزمية المجاميع البادئة على الشبكة
7-4-3 مسألة الأعمال المتسلسلة وفق فترات انتهائها
1- خوارزمية الإجراء (:1,20516) 5501712110110 11655
2- تحليل خوارزمية الإجراء 5150178701116 1782515
8-4-3 مسألة حقيبة الظهر 7160131514 101738016 7135
1- خوارزمية الإجراء 10187584016 11825185
2- تحليل خوارزمية حقيبة الظهر
3- حلول مسألة حقيبة الظهر على الشبكة
5-3 5-3 خوارزميات متوازية لأجهزة متعددة المعالجات ذات ذاكرة مشتركة
1-5-3 مسألة الاختيار
1-1-5-3 الخوارزمية التسلسلية لمسألة الاختيار
1- خوارزمية الإجراء (ا ,5) 5151507 515911217711
2- تحليل خوارزمية الإجراء 5851507 لظ 515017151771
4- خوارزمية الاختيار المتوازي
2-5-3 مسألة الدمج
1-2-5-3 شبكة الدمج 1/186146116 101 112711771701
2-2-5-3 خواص شبكة الدمج (زوج + فرد)
3-2-5-3 الدمج على النموذج 0185177
1- إجراء الدمج التسلسلي 10561116 8150111217711

3- الدمج المتوازي 151401116 انآ اماتخ
7- تحليل خوارزمية © , 13 , ه) 11515615 0152177
4-2-5-3 الدمج على النموذج 151815187
2- الخوارزمية الأفضل للنموذج 15185177
3- خوارزمية إيجاد العنصر الأوسط لمتسلسلتين مرتبتين
4- خوارزمية الإجراء ((, ,)1150131 520151012 _(701
5- تحليل خوارزمية الإجراء 11801437 5501751105 _7017
النتائج والمقترحات
المصطلحات المستخدمة
قائمة الأشكال والجداول
المراجع العلمية
ملخص باللغة العربية
ملخص باللغة الانكليزية 455170621/
ملحق لبرنامج دمج مصفوة

مقدمة
تطور علم المعلوماتية منذ بدايته في منتصف القرن العشرين حتى بداية هذا القرن بشكل
متسارع وكبير وتشعبت فروعه وتعددت مجالاته واختصاصاته. وأصبح دخول هذا العلم
ضرورياً في مختلف مجالات الحياة وكافة فروع العلوم الأخرى واقتضى ذلك تصميم
الخوارزميات الملائمة لحل المسائل والمشكلات المطروحة إلى تطوير كبير في علم
الخوارزميات. واقتضت بنية الحواسيب التي رافق ظهورها ولادة علم المعلوماتية إلى
وضع خوارزميات تنفذ تتابعياً بحيث تكون تعليمات البرامج مرتبة ترتيباً دقيقاً ويتم تنفيذ
الواحدة تلو الأخرىء إلا أنه مع زيادة حجم المسائل الواجب حلها وتشعب المشكلات
الواقعية المطروحة وصعوبتها أصبح من العسير على مثل هذه الخوارزميات الوصول
لحل دقيق لتلك المسائل والمشكلات إما لتجاوز قدرات الذاكرات اللازمة لتخزين
المعلومات والنتائج المرحلية أو بسبب المدد الزمنية الكبيرة اللازمة للوصول للحل الأمثل
وعلاوة على ذلك ازداد إلحاح مستخدمي الحواسيب في طلب قدرات حسابية متنامية وذلك
بشكل مستمر الأمر الذي حدا بالعلماء والباحثين للتفكير في إيجاد أساليب جديدة تساعد
على تلبية تلك الرغبات سواء في تسريع عملية البحث عن حلول للمسائل المطروحة أو
زيادة حجم تلك المسائل.
ومن هنا ولدت مسألة التوازي في البرمجة إلا أنه تبين استحالة تطبيقها على الأجهزة
التقليدية التي تعتمد تقنية الكترونية ثابتة ؛ الأمر الذي استدعى التدخل في بنية الجهاز
نفسه والبحث عن بنية جديدة وقد تم في مطلع الثمائينات من القرن العشرين تصميم أول
حاسوب متعدد المعالجات دعي 0/8171 الذي احتوى على معالجين يسلان في آن
معاً وتوالى بعد ذلك ظهور حواسيب جديدة تعتمد بنى مختلفة مثل ,385 ,2/45
... ,205 :07/06 ,1111:2617 وكان القاسم المشترك بين مختلف هذه البنى هو استخدام
الأجهزة سواء في قدرتها الكبيرة في الحساب أو في حجم الذاكرات الكبير جداء إلا أن
ظهورها قد طرح مشكلة أساسية هي عدم المحافظة على التسلسل الزمني لتنفيذ التعليمات

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

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

الفصل الأول
دراسة مفهوم الأنظمة متعددة
أسلوب التواصل فيما بينها

1-1 مفهوم البرمجة متعددة المهام:
1-1-1 تعريف النظم المعتمدة على الحاسوب:
تعرف النظم المعتمدة على الحاسوب بأنها مجموعة أو ترتيب عناصر نُظمت بغية إنجاز هدف محدد
بمعالجة المعلومات. ويستخدم النظام المعتمد على الحاسوب عدداً من العناصر وهي: البرمجيسات
والعتاديات والأشخاص وقاعدة المعطيات والوثائق والإجراءات. وتُضم هذه العناصر بأشكال مختلفة
لتحويل المعلومات.
ولإنشاء نماذج لهذه النظم نقوم بما يلي:
» تعريف الإجرائيات التي تخدم احتياجات الرؤية المعينة
يف الدخل الخارجي والدخل الداخلي للنموذج بشكل واضح
* تمثيل جميع الروابط (بما فيها الخرج) التي تساعد المهندس على فهم الرؤية فهماً أفضل.
ولبناء نموذج نظام يجب على المهندس التقيد بالعوامل التالية:
1- الافتراضات: التي تخفض عدد التبادلات والاختلافات الممكنة والتي تسمح من ثم للنموذج أن
يعكس المشكلة على وجه مقبول+
2- التبسيطات: التي تسمح بإنشاء النموذج بالوقت المناسب.
3- الحدود: التي تساعد في وضع حدود للنظام. :
4- القيود: التي توجه الطريقة التي يُنشأً بها النموذج والمنهج المتبع في تنجيزه.
5- التفضيلات التي تدل على البنيانات المفضلة لجميع المعطيات والوظائف والتقانة.
قد يترتب على نموذج النظام الناتج حل تام الأتمتة أو نصف مؤتمت أو يدوي. ويمكن وصف نماذج
لكل نمط يحقق حلا بديلاً للمسألة المطروحة وببساطة يتم تعديل التأثير النسبي لعناصر النظام المختلفة
(الأشخاص والعتاديات والبرمجيات) بغية استنتاج نماذج من كل نمط.

2-1-1 تعريف تعددية المهام:
تعرف تعددية المهام (21018516:08)على أنها قدرة نظام التشغيل على تنفيذ أكثر من مهمة واحدة
في الوقت نفسه وتتيح تعددية المهام مثلاً تنفيذ عدة برامج مختلفة والطباعة على الطابعة والتخزين
على القرص في الوقت نفسه ودون انتظار انتهاء كل مهمة من هذه المهمات قبل تنفيذ الأخرى.
وتبنى الخوارزمية في الأجهزة المتعددة المعالجات على أساس تعددية المهام والتنفيذ المتزامن حيث
تتولى كل وحدة معالجة مسألة جزئية فتقوم بمعالجتها بشكل متزامن مع الوحدات الأخرى ونحصل في
المتعددة المهام على فهم طريقة تنفيذ التعليمات على البيانات حيث إن هناك سلسلة من التعليمات تأمر
الحاسب بوظيفته في كل خطوة وهناك سلسلة من البيانات (دخل الخوارزمية) ستتأثر بتلك التعليمات.
ويتم تصنيف الحواسيب تبعاً لطريقة تنفيذ التعليمات على البيانات وتتم برمجة كل نوع من أنواع
من الضروري وجود اتصال بين وحدات المعالجة بعضها مع بعض خلال الحساب وذلك من أجل
تغيير البيانات أو النتائج ويتحقق هذا الاتصال عن طريق الذاكرة المشتركة للنظام أو عن طريق شبكة
الاتصالات بين وحدات المعالجة.
2-1 الأنظمة المتعددة المعالجات:
1-2-1 وصف الأنظمة المتعددة المعالجات:
لقد وجدت الأنظمة المتعددة المعالجات من أجل تحسين الفعاليات وذلك مقارنة بالكلفة والموثوقية
والتكيّف ويعتبر النظام المتعدد المعالجات (مع أو بدون تواز) رائداً بين أنظمة المعلوماتية حيث ينا
نظام المعالج الوحيد وينافس أيضاً الأنظمة الموزعة وغيرهاء
وفي النظام المتعدد المعالجات المتوازي يوجد العديد من وحدات المعالجة المستقلة والتي تتصف
بذاكرات محلية وتشترك معاً بذاكرة رئيسية وتكون هذه المعالجات متزامنة. حيث يحوي الحاسب
المتوازي عدة معالجات ويقوم بإعطاء مسألة جزئية من المسألة الكلية لكل منها وتحل المسائل الجزئية
بشكل متزامن كل واحدة في معالج مختلف ومن ثمّ تجمع النتائج لإعطاء حل المسألة الأصلية.