عنوان الإطروحه |
A Horizontal Partitioning Non-Contiguous Processor Allocation Strategy for 2D Mesh-Connected Multicomputers
|
تاريخ مناقشة الاطروحه |
2017-12-30 |
اسم الطالب |
نبيل خالد مبارك ابوعليم
|
المشرف |
سعد عقله محمود بني محمد |
|
المشرف المشارك |
|
اعضاء لجنة المناقشة |
| اسماعيل محمد علي عبابنة |
| اكرم عارف نايف حمارشة |
| وائل مارديني |
|
الكلية |
كلية الامير الحسين بن عبدالله لتكنولوجيا المعلومات |
القسم |
علم الحاسوب |
الملخص بالعربية |
تصنف استراتيجيات تخصيص المعالجات في متعددات الحواسيب الشبكية ثنائية الابعاد إلى نوعين رئيسيين: المتجاور والغير متجاور. يشترط في استراتيجيات التخصيص المتجاور أن تكون المعالجات التي يتم تخصيصها للطلب متجاورة فيزيائيا، كما يجب ان يكون شكل شبكة المعالجات المخصصة لطلب ما مشابه لشكل الشبكة الاصلي، ونتيجة لذلك تعاني هذه الاستراتيجيات من مشاكل الكسيرات الخارجية والداخلية.، بينما في استراتيجيات التخصيص الغير متجاور، فيمكن تقسيم الطلب الى اجزاء اصغر وتخصيصه في شبكات منفصله عن بعضها البعض، وذلك بدلا من الانتظار حتى يتوفر شبكة معالجات لها نفس الحجم والشكل للطلب الاصلي.
هناك العديد من الاستراتيجيات المقترحة للتخصيص غير المتجاور، حيث تختلف هذه الطرق عن بعضها البعض في طريقة التخصيص للمعالجات في الشبكة، وبنسب متفاوتة لدرجة التجاور بين المعالجات المخصصة.
تم في هذا البحث اقتراح استراتيجية جديدة للتخصيص غير المتجاور للمعالجات في متعددات الحواسيب الشبكية ثنائية الابعاد، والتي يشار إليها باستراتيجية التقسيم الأفقي (HPS)، حيث يتم في هذه الطريقة تقسيم طلب التخصيص للمعالجات على أساس المعالجات الأفقية المتاحة للتخصيص في النظام، وذلك للحفاظ على درجة عالية من التجاور فيما بين المعالجات المخصصة للمهمة الواحدة، وتسمى هذه المعالجات الأفقية بالكتل الحرة، وكل منها يمثل صف من المعالجات الحرة التي يساوي حجمها عرض الشبكة. تقوم استراتيجية التقسيم الافقي على تغيير شكل طلب التخصيص بحيث يمكن احتوائه في الكتل الحرة، كما تحاول دائما تخصيص الطلب بشكل متجاور في الكتل الحرة من أجل تقليل المسافة التي تحتاجها الرسائل للانتقال بين المعالجات في النظام، وبالتالي تقليل التزاحم داخل الشبكة، مما يسهم في تحسين الأداء من حيث معدل مكوث المهام في النظام.
تم مقارنة أداء استراتيجية التقسيم الافقي مع استراتيجيات التخصيص غير المتجاور المعروفة باستخدام المحاكاة، وتبين النتائج أن أداء استراتيجية التقسيم الافقي أفضل بكثير من استراتيجيات التخصيص غير المتجاور الأخرى التي تم دراستها في هذا البحث، وعلاوة على ذلك، فإن استراتيجية التقسيم الافقي تعطي اشغالا عاليا للنظام لقدرتها على التخلص من الكسيرات الداخلية والخارجية كما هو الحال في استراتيجيات التخصيص غير المتجاور الأخرى التي تم دراستها.
|
الملخص بالانجليزي |
Processor allocation strategies that had been devised for mesh-connected multicomputers are classified into two types, contiguous and non-contiguous. In contiguous strategies, the allocated processors must be physically adjacent, and form a contiguous shape similar to the original topology. Contiguous allocation suffers from both external and internal fragmentation problems. In non-contiguous allocation strategies, the job request can execute on multiple separated smaller sub-meshes rather than waiting until a single sub-mesh of the requested size and shape is available.
There are many proposed strategies for non-contiguous allocation that have different levels in working to balance between distributing the requested job among the processors in the mesh, and keeping a good level of contiguity between the allocated processors.
In this research, we have proposed a new non-contiguous processor allocation strategy for 2D mesh-connected multicomputers, referred to as Horizontal Partitioning Strategy (HPS) that partitions the job request based on the sub-meshes available for allocation in the system so as to maintain some degree of contiguity. These sub-meshes are called Free-rows, and each of them represents a row of free processors that is equal to the width of the mesh. HPS strategy rebuilds the job request to accommodate in Free-rows and it always tries to allocate a job request contiguously in Free-rows in order to decrease the distance traversed by a message, and hence reduce the message contention inside the network.
Using simulation, we compared the performance of HPS with the existing well-known non-contiguous allocation strategies Paging(0), MBS, and GABL. The results show that the performance of HPS allocation strategy is much better than that of other non-contiguous allocation strategies for both job size distributions considered when the all-to-all communication pattern is used, and it is close to that of the non-contiguous allocation strategies considered when the one-to-all and random communication patterns are used. Moreover, HPS exhibits high system utilization as it manages to eliminate both internal and external fragmentation
|
رقم ISN |
44 |
|
للحصول على الرسالة كملف يرجى تزويد المكتبة برقم ISN
|
|