ترغب بنشر مسار تعليمي؟ اضغط هنا

دراسة تأثير موازاة خوارزميات التفرع و الحد (Bound & Branch) في تحسين أدائها

The Effects Of Parallelism Of Branch and Bound Algorithms In Improving It's Performances

1743   0   39   0 ( 0 )
 تاريخ النشر 2005
والبحث باللغة العربية
 تمت اﻹضافة من قبل Shamra Editor




اسأل ChatGPT حول البحث

تستخدم خوارزميات التفرع و الحد (Bound and Branch) التي يرمز لها بـ B&B في حل مـسائل الأمثلة (الاستمثال) التوافقية التي تصنف درجة تعقيدها في الفئة hard-NP . و على الرغم من فعالية هذه الخوارزميات فقد بقي حجم المسائل التي تتمكن من حلها و البرهان على أمثلة الحـل محـدوداً بـسبب محدودية قدرات الحواسيب رغم تطورها الكبير. و مع ظهور البرمجة المتوازية و الحواسيب متعددة المعالجات فكر الباحثون بالاستفادة من قدرات هذه التقانات و الأجهزة في زيادة حجم المسائل المحلولة إلا أنه نجم عن الموازاة ثلاثة أنـواع مختلفـة مـن الشذوذ. يهدف هذا البحث إلى تقديم نموذج جديد لخوارزمية التفرع و الحد المتوازية يسمح بتحليـل فعاليـات الخوارزمية و يستند هذا النموذج إلى قواعد جديدة للاختيار بين العقد المتساوية التقويم بعد أن ثبت عجز قاعدة اختيار العقدة ذات التقويم الأفضل، كما نقوم بحساب حدود محكمة لكل قاعدة من القواعد و نبـرهن على إمكانية بلوغها، كما نقدم الشروط اللازمة و الكافية لظهور كل حالة من حالات الشذوذ النـاجم عـن موازاة الخوارزمية. درسنا و قارنا في هذا البحث النتائج الناجمة عن تجاهل بعض الفرضيات المستخدمة في خوارزميـات التفرع و الحد، و اقترحنا فضلاً عن ذلك استخدام النماذج غير المتزامنة للاستفادة القصوى من الإمكانيـات التي تقدمها البرمجة المتوازية.

المراجع المستخدمة
AKL, S. G. (1997).'' Parallel Computation Models And Methods'', Prentice Hall
Almasi, G. S., Gottlieb, A. (1994). ''Highly Parallel Computing'', The Benjamin Cummings Publishing Company, Inc
Aorts, E., Lenstra, J. K. (2003). ''Local Search In Combinatorial Optimization'', Princeton University Press
قيم البحث

اقرأ أيضاً

في المشكلة التي نعالجها, تحتاج شركة اتصالات إلى بناء مجموعة من الأبراج الخلوية لتوفير خدمة الاتصالات الخليوية للسكان في منطقة جغرافية. تم تحديد عدد من المواقع المحتملة لبناء الأبراج. يعتم اختيار هذه المواقع على عدة عوامل ، بما في ذلك مدى اتساق البرج مع البيئة المحيطة وارتفاع التضاريس, تتمتع الأبراج بمدى تغطية ثابت ، وبسبب قيود الميزانية ، لا يمكن بناء سوى عدد محدود منها . بالنظر إلى هذه القيود ، ترغب الشركة في توفير تغطية لأكبر قدر ممكن من السكان, والهدف هو اختيار في أي من المواقع المحتملة يجب أن تقوم الشركة ببناء الأبراج. إن المشكلة التي شرحناها يمكن نمذجتها لتصبح أحد أمثلة مشكلة 0/1 knapsack الشهيرة لذلك شرحنا في الحلقة مفهوم مشكلة 0/1 Knapsack والطرق المستخدمة في الحل, وتوسعنا في الشرح عن خوارزمية Branch and Bound كونها تعتبر أفضلها.
تطورت شبكات الحاسوب كثيراً خلال السنوات القليلة الماضية من ناحية التزايد الكبير في كميات البيانات المتبادلة عبر الشبكة بسبب تزايد عدد الأجهزة المترابطة، و التي يمكن ان تتبادل البيانات في اطار الشبكة و هذا ما ادى الى ظهور ما يُعرف بمشكلات الازدحام Con gestion و أظهرت دراسات حول بعض هذه المشاكل أن السبب الأكبر يقع في تنفيذ قواعد الإرسال، و هذا ادى الى ظهور أنواع متعددة من البروتوكولات في أنظمة الاتصالات و شبكات الحواسيب لضرورة التعامل مع الأنظمة الحاسوبية المختلفة, و بذلك ظهرت أيضاً الحاجة إلى ضرورة وجود آليات للتمييز بين الحواسيب العديدة في الشبكة الواحدة , و العديد من التطبيقات ضمن النظام الواحد : و العديد من نسخ هذه التطبيقات , حيث يسبب ذلك في كثير من الأحيان أخطاء على مستوى البت الخانة (bit) و مستوى الرزم ((packet ,رزم مفقودة ,رزم مكررة , رزم وردت بشكل عشوائي, و الأهم ظهور الازدحام في الشبكة. يهدف هذا البحث الى تحديد كيفية تحسين أداء الشبكة بالتخلص من الازدحام و ذلك بالاستفادة من الخوارزميات المستخدمة في تجنب الازدحام الذي قد يحصل في الشبكات التي تعتمد بروتوكول TCP حيث أن الهدف من هذه الخوارزميات هو الوصول الى الاستقرار في الشبكة من خلال العمل على تحقيق مبدأ حفظ الرزمة. و لذلك و ضمن هذا الاطار أيضاً تم دراسة، و مقارنة بعض الخوارزميات المستخدمة في تجنب الازدحام بشكل عام دون الاعتماد على بروتوكول معين او صنف خدمة محدد .
يقدم البحث نمذجة و تحليل أداء عدد من خوارزميات الجدولة في أنظمة الزمن الحقيقي متعددة المعالجات. حيث تم تحليل أداء كل من الخوارزميات الثلاث: خوارزمية الجدولة بالزمن الحرج الأقصر أولاً EDF ، و خوارزمية الجدولة بالزمن الأقل خمولاً أولاً LLF ، و خوارزمية الجدولة بالزمن الحرج أولاً عند الخمول الصفري EDZL . شملت هذه الدراسة جدولة مهام دورية ذات قيود زمنية مساوية لدورها ، و مستقلة، و قابلة للمقاطعة على عدة معالجات متطابقة . تمت مقارنة الخوارزميات الثلاث من ناحية الحمل على المعالج (مشغولية المعالجات)، و من ناحية عدد الهجرات، و عدد المقاطعات، و عدد المرات التي لم تنجح فيها هذه الخوارزميات في تحقيق الحدود الزمنية للمهام، حيث يعتبر الأخير أهم معيار من معايير عملية الجدولة في الزمن الحقيقي. كما تضمنت الدراسة جدولة مجموعات متزايدة من المهام الدورية تبدأ من 4 مهام لتصل حتى 64 مهمة ، و ذلك لدراسة تأثير ازدياد عدد المهام و المعالجات على أداء خوارزميات الجدولة، و كنتيجة يقدم البحث نقاط القوة و الضعف في أداء هذه الخوارزميات و يقترح لكل خوارزمية - حسب نقاط القوة في أدائها- نوع منظومة الزمن الحقيقي التي من الأفضل تطبيقها فيها.
يعد الصوت عنصراً أساسياً من عناصر الأوساط المتعددة، و نتيجة الحاجة إلى استخدامه في كثير من التطبيقات الحياتية كالبث التلفزيوني و برامج التواصل، لذا كانت الضرورة لوجود تقنيات لمعالجة إشارة الصوت من ضغط و تحسين و تقليل ضجيج. تكمن أهمية عملية ضغط البيا نات في تخفيض معدل البتات المستخدمة، و ذلك عن طريق ترميز المعلومات باستخدام عدد أقل من البتات من التمثيل الأصلي من أجل الإرسال و التخزين. حيث تقوم بتحديد المعلومات غير الضرورية و إزالتها، أي تعطي المعلومات التي ضُغطت ضغط الاستخدام ما نحتاجه كشكل أساسي و ليس أدق التفاصيل. يهدف البحث إلى دراسة كيفية معالجة الصوت و الإشارة الموسيقية، و هي عملية تضم بعض التطبيقات كالترميز و الضغط الرقمي بهدف النقل الفعال و التخزين على الهواتف النقالة و مشغلات الموسيقا المحمولة، و نمذجة واستنساخ صوت الآلات الموسيقية و قاعات الموسيقا و توافقيات الموسيقا الرقمية، و تحرير الموسيقا الرقمية، و تصنيف محتوى الموسيقا بالإضافة إلى أمور أخرى.
تم في هذه الورقة عرض لبنى المعالجات المتوازية و التركيز على بنيتين أساسيتين من هذه البنى و هي بنية المعالج فائق التدرج (Superscalar Processor) و بنية المعالج الشعاعي (Vector Processor)، و بالإعتماد على الخصائص الأساسية لكل منها تم بناء محاكي لهذه الب نى يحاكي آلية عملها برمجياً بهدف المقارنة بين أدائها فيما يخص التوازي على مستوى البيانات (Data Level Parallelism DLP) و التوازي على مستوى التعليمات (Instruction Level Parallelism ILP). تبين النتائج أن فعالية تنفيذ التعليمات على التوازي تعتمد بشكل كبير و أساسي على اختيار بنية المعالج المناسبة للتنفيذ وفق نوع التوازي الممكن تطبيقه على التعليمات، و أن ميزات الشعاع في البنية الشعاعية تحقق تحسين ملحوظ في الأداء لايمكن إغفاله في تنفيذ عمليات DLP و تبسيط للكود البرمجي و تقليل لعدد التعليمات، و يشكل المحاكي المقدم نواة جيدة يمكن تطويرها و الإضافة عليها خاصة فيما يخص المجال التعليمي لطلاب علوم و هندسة الحاسب و المجال البحثي.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا