عنوان الإطروحه |
A Row Based Non-Contiguous Processor Allocation Strategy for 2D Mesh-Connected Multicomputers
|
تاريخ مناقشة الاطروحه |
2017-05-23 |
اسم الطالب |
ضيف الله صالح عبدالله السرديه
|
المشرف |
سعد عقله محمود بني محمد |
|
المشرف المشارك |
|
اعضاء لجنة المناقشة |
| اسماعيل محمد علي عبابنه |
| عمر علي عوده شطناوي |
| شادي الجوارنة |
|
الكلية |
كلية الامير الحسين بن عبدالله لتكنولوجيا المعلومات |
القسم |
علم الحاسوب |
الملخص بالعربية |
تدعم أنظمة متعددات الحواسيب الشبكية أنواع مختلفة من التطبيقات بمختلف الأحجام والخصائص في بيئة متعددة المستخدمين، ولذلك فمن المهم استخدام استراتيجيات فعَّالة لتخصيص المعالجات لاستغلال القدرة الحسابية لهذه الأنظمة، حيث تعتمد فعالية استراتيجيات التخصيص على قدرتها على زيادة استغلال المعالجات وتقليل وقت مكوث المهام في النظام.
تقسم استراتيجيات تخصيص المعالجات في متعددات الحواسيب الشبكية الى فئتين رئيسيتين: متجاورة و غير متجاورة. تعتمد استراتيجيات التخصيص المتجاور في التخصيص على التجاور الفيزيائي بين المعالجات كما وتشترط ان يكون شكل الشبكة الجزئية المخصصة شبيه بشكل شبكة الربط في النظام، وقد يؤدي شرط التجاور هذا الي ظهور مشكلة الكسيرات الخارجية وبشكل كبير؛ وتحدث الكسيرات الخارجية عند وجود مجموعة من المعالِجات المتوفرة في النظام والتي تكفي لطلب معين ولكن لا يمكن تخصيصها لذلك الطلب بسبب عدم تجاورها، وتؤدي هذه المشكلة إلى تدني معدل استغلال المعالجات في النظام، وبالتالي زيادة وقت مكوث المهام في النظام. تم اقتراح خوارزميات التخصيص غير المتجاور كحل عملي لمشكلة الكسيرات، وقد شجع على ذلك التطور في تقنيات توجيه ونقل الرسائل داخل الشبكة مثل (Wormhole Routing) والتي قللت من تأثير المسافة التي تقطعها الرسالة على التأخير الكلي للتراسل، وعلاوة ًعلى ذلك، فقد أظهرت الأدلة التجريبية أن التحسين الإضافي على خوارزميات التخصيص المتجاور الموجودة لا يؤدي إلّا إلى تحسين طفيف على الأداء للنظام بشكل عام، لذلك فقد تم تبني التخصيص غير المتجاور للمعالجات، حيث يمكن من خلاله تقسيم طلب مهمة معينة الى إجزاء وتخصيصها في إجزاء متفرقة من الشبكة بدلا ً من انتظارها لجزء من الشبكة يحتوي على معالجات متجاورة ليصبح متاحاً، ومن المتوقع أن يؤدي ذلك إلى تحسين في معدل استغلال المعالجات في النظام وبالتالي تقليل معدل أوقات مكوث المهام في النظام. ومع ذلك التحسين المتوقع لإداء النظام بسبب استخدام التخصيص غير المتجاور، الا ان استراتيجيات التخصيص غير المتجاور تعاني من مشكلة التزاحم بين رسائل المهام المختلفة، مما قد يؤدي إلى زيادة التأخير في الوقت المستغرق في التراسل.
تستخدم خوارزميات التخصيص غير المتجاور الحالية تقنيات مختلفة لإيجاد وتخصيص الشبكات الجزئية المتاحة، إلّا أنها في الغالب تركز على الحفاظ على درجة عالية من التجاور بين المعالجات المخصصة لمهمة معينة في شبكة جزئية معينة عن طريق تحشير المهام المخصصة بجانب بعضها للحفاظ على أكبر قدر ممكن من المعالجات المتجاورة المتاحة لطلبات المهام القادمة. تم في هذه الرسالة اقتراح استراتيجية تخصيص غير متجاور جديدة، يشار اليها بخوارزمية التخصيص غير المتجاور المُعتَمِدة على الصفوف في متعددات الحواسيب الشبكية ثنائية الأبعاد. تمتلك الخوارزمية المُقتَرَحة القدرة على منع حدوث الكسيرات الداخلية والخارجية، كما وتقلل من تزاحم الرسائل بين المهام المختلفة في الشبكة. تُصنِّف الخوارزمية المُقتَرَحة طلبات المهام الواردة حسب حجمها الى نوعين: كبيرة وصغيرة؛ وذلك بهدف التقليل من تزاحم رسائل المهام المختلفة.
أظهرت نتائج المحاكاة أنَّ أداء الخوارزمية المُقتَرَحة يفوق أداء استراتيجيات التخصيص المتجاور وغير المتجاور الأخرى من حيث معدل أوقات مكوث المهام في النظام، وذلك عند استخدام نمط التراسل (الكل ? للكل)؛ وهذا بسبب قدرة الخوارزمية المقترحة على تقليل تزاحم الرسائل في الشبكة، كما أظهرت النتائج أيضاً أنَّ أداء الخوارزمية المقترحة أفضل نسبياً من أداء خوارزميات التخصيص غير المتجاور الأخرى عند استخدام نمطي التراسل (الواحد - للكل) و (العشوائي)، وذلك في معظم الحالات، بينما تفوقت استراتيجيات التخصيص الأخرى على الخوارزمية المقترحة عند استخدام نمط الاتصال (المجاور القريب).
|
الملخص بالانجليزي |
Multicomputer systems typically support diverse types of applications with various sizes and characteristics in a multiuser environment. Therefore, it is critical to use efficient processor allocation strategies to exploit the computation power of such systems. An efficient processor allocation strategy is that which maximizes system utilization and minimizes the jobs' turnaround time. In mesh-connected multicomputers, the processor allocation strategies can be classified into two main categories: contiguous and non-contiguous. In contiguous allocation, a job is allocated a submesh only if its processors are contiguous and form a shape the same as the connecting network. This allocation condition could lead to high processor fragmentation which could decrease the system performance in terms of system utilization and turnaround times of jobs. Non-contiguous processor allocation has been adopted as a feasible solution to the processor fragmentation problem. This adoption has encouraged by the emergence of the wormhole routing and advances in switching techniques which have made the communication latency less sensitive to the distance between the communicating nodes. Moreover, the experimental evidence has shown that only a slight improvement can be gained from further improving the existing contiguous allocation strategies. In non-contiguous allocation, a job request can be partitioned and allocated multiple disjoint submeshes instead of being queued waiting for a one to be available. This is expected to improve the system utilization and hence the average turnaround times of jobs. However, an extra communication overhead is expected due to the contention among messages of different jobs. The existing non-contiguous allocation strategies use various techniques to capture and allocate the available submeshes, however, in general, they focus on maintaining a high degree of contiguity among the processors of the allocated submeshes by compacting submeshes allocated to different jobs next to each other. In this thesis, a new non-contiguous allocation strategy, referred to as Row Based Strategy (RBS), has been suggested for 2D mesh-connected multicomputers, which alleviates the message contention inside the network. RBS classifies the incoming job requests according to their sizes into large and small in order to allocate them in a way that minimizes the contention among different jobs' messages. The simulation results have revealed that the proposed strategy is superior to that of the existing non-contiguous and contiguous allocation strategies in terms of job turnaround time when the all-to-all communication pattern is used, and this is due to its ability to alleviate message contention inside the network. Also, in most cases, it is relatively better than other allocation strategies for the one-to-all and random communication patterns |
رقم ISN |
43 |
|
للحصول على الرسالة كملف يرجى تزويد المكتبة برقم ISN
|
|