عنوان الإطروحه |
An Efficient Processor Allocation Algorithm for 2D Mesh Connected Multicomputers
|
تاريخ مناقشة الاطروحه |
2019-01-07 |
اسم الطالب |
عبير بسام عبدالكريم الشديفات
|
المشرف |
سعد بني محمد |
|
المشرف المشارك |
اسماعيل عبابنة
|
اعضاء لجنة المناقشة |
| عمر شطناوي |
| اكرم حمارشة |
| شادي عبد الرحمن الجوارنة |
|
الكلية |
كلية الامير الحسين بن عبدالله لتكنولوجيا المعلومات |
القسم |
علم الحاسوب |
الملخص بالعربية |
تقسم استراتيجيات التخصيص للمعالجات في الحواسيب المتوازية الى نوعين: استراتيجيات التخصيص المتجاور واستراتيجيات التخصيص غير المتجاور. في التخصيص المتجاور يكون التجاور بين المعالجات المخصصة لمهمة معينة شرطا اساسيا، كما تشترط بعض الاستراتيجيات ان يكون الشكل المخصص نفس شكل الشبكة التي تربط بين المعالجات في النظام، وهذا بدوره يؤدي الى ظهور ما يعرف باسم مشكلة الكسيرات، والتي تؤثر سلبيا على اداء النظام من حيث تقليل نسبة استغلال المعالجات في النظام وزيادة الوقت الذي تقضيه المهام في النظام.
جاءت استراتيجيات التخصيص غير المتجاور لحل مشكلة الكسيرات، حيث انها لا تشترط التجاور ما بين المعالجات المخصصة لمهمة معينة مما يؤدي الى تحسين اداء النظام بما يتعلق بوقت المكوث للمهام في النظام وكذلك معدل استغلال المعالجات في النظام، بالرغم من ان هذا النوع من التخصيص قد يؤدي الى زيادة التزاحم ما بين الرسائل بين المعالجات المخصصة للمهمة، الا انه يساعد على التخلص من مشكلة الكسيرات وبالتالي يزيد من نسبة استغلال معالجات النظام. وتعاني معظم استراتيجيات التخصيص غير المتجاور من مشكلة الكسيرات بالإضافة الى حاجتها الى الشكل المنتظم المشابه لشكل شبكة النظام، لذلك فقد اقترحنا في هذه الرسالة استراتيجية تخصيص غير متجاور جديدة تسمى استراتيجية الجار للتخصيص (Neighbor Allocation Strategy) والتي تقلل مشكلة الكسيرات في النظام، حيث تعمل الاستراتيجية المقترحة على تخصيص مجموعة فرعية من الاشكال المخصصة بحيث تحافظ على درجة من التجاور بين المعالجات المخصصة للمهمة وهذا بدوره يؤدي الى تحسين في اداء النظام من حيث معدل استغلال المعالجات في النظام ومعدل مكوث المهام في النظام.
تمت مقارنة اداء الخوارزمية الجديدة (NAS) مع اداء استراتيجية التخصيص المتجاور (First Fit) والغير متجاور (L-Shape Submesh Allocation Strategy) باستخدام المحاكاة، وقد اظهرت النتائج تفوق الخوارزمية المقترحة (NAS) على باقي الاستراتيجيات بما يتعلق بمعدل استغلال المعالجات في النظام بسبب قدرتها على تقليل مشكلة الكسيرات في النظام. اما فيما يخص معدل وقت المكوث للمهام في النظام فقد تفوقت الاستراتيجية المقترحة ( (NASعند استخدام نمط التراسل (One to All) ، في حين تفوقت استراتيجية التخصيص المتجاور عند استخدام (All to All) و (Near Neighbor) على استراتيجيات التخصيص الغير متجاور، بينما تفوقت الاستراتيجية المقترحة (NAS) على استراتيجية (L-Shape Submesh Allocation Strategy) عند استخدام انماط التراسل (All to All) و (Near Neighbor)
|
الملخص بالانجليزي |
In the 2D mesh connected multicomputers, two types of strategies for processor allocation were proposed: the contiguous and Non-Contiguous. In contiguous strategies, the processors allocated have to be physically adjacent, and in some strategies must have the same shape as the mesh topology. Contiguous allocation schemes suffer from fragmentation problem, which has direct influence on the performance of the system when, average response time and system utilization are considered. In Non-Contiguous allocation schemes the request of the job can be executed on some separated smaller sub-meshes rather than waiting for a submesh of the requested sub-mesh, shape and size is available on the system. There are many devised Non-Contiguous allocation strategies that vary on the rate of contiguity kept among the allocated small sub-meshes to the job request in the mesh-system.
In this research, we have proposed a new Non-Contiguous processor allocation strategy for 2D-mesh-connected multicomputers, referred to as Neighbor Allocation Strategy (for short NAS). The NAS allocates a number of smaller sub-meshes, which have a rate of contiguity among them, the requests from jobs. NAS rebuilds the job request to be accommodated in to the possible free sub-meshes in the system and always allocates the job request contiguously to remove internal and external fragmentation, and hence maximize system utilization and minimize average response time.
Using simulation, performance of NAS, the contiguous allocation scheme FF, and the Non-Contiguous allocation scheme LSSA were compared. The outcomes show that the performance of NAS in term of average response time is encouraging than that of all other allocation schemes when the one_to_all communication pattern is used for the 2 distributions considered in this work considering job size. On the other hand, when All-to-All and near neighbor communication patterns are used the FF has the superior performance over all other schemes because it allocates rectangular sub-mesh to the job request, which minimize interference between massages so it minimize communication overhead, while NAS results are improved than LSSA. Furthermore, results show that NAS maximize system utilization more than the other two strategies FF and LSSA, this is because of its ability to remove both of internal as well as external fragmentation
|
رقم ISN |
4366 |
|
للحصول على الرسالة كملف يرجى تزويد المكتبة برقم ISN
|
|