عنوان الإطروحه |
Irregular Shape Strategy for Non-contiguous Sub-mesh Allocation in 2D Mesh-Connected Multicomputers
|
تاريخ مناقشة الاطروحه |
2016-05-22 |
اسم الطالب |
رائد ذياب عواد الحرافشة
|
المشرف |
سعد عقلة بني محمد |
|
المشرف المشارك |
اسماعيل عبابنة
|
اعضاء لجنة المناقشة |
| يوسف كيلاني |
| عمر شطناوي |
| خالد بطيحة |
|
الكلية |
كلية الامير الحسين بن عبدالله لتكنولوجيا المعلومات |
القسم |
علم الحاسوب |
الملخص بالعربية |
تصنف استراتيجيات تخصيص المعالجات في الحواسيب المتوازية الى صنفين: استراتيجيات التخصيص المتجاور واستراتيجيات التخصيص غير المتجاور. تشترط إستراتيجيات التخصيص المتجاور التجاور في ما بين المعالجات المخصصة لمهمة معينة وان تكون المعالجات المخصصه بنفس شكل الشبكة التي تربط ما بين المعالجات في النظام، وهذا يؤدي بدوره الى حدوث ما يسمى بمشكلة الكسيرات، والتي تؤثر سلباً على اداء النظام مما يؤدي الى زيادة الوقت الذي تقضيه المهام في النظام وكذلك تقليل نسبة استغلال المعالجات في النظام. جاءت استرتيجيات التخصيص غير المتجاور لحل مشلكة الكسيرات، حيث انها لا تشترط التجاور ما بين المعالجات المخصصة لمهمة معينه مما يؤدي بالتالي الى تحسين اداء النظام فيما يتعلق بمعدل وقت مكوت المهام في النظام وكذلك معدل استغلال المعالجات في النظام، وعلى الرغم من الزيادة في التزاحم ما بين رسائل المعالجات المخصصة في النظام نتيجة استخدام التخصيص غير المتجاور، الا ان هذا النوع من الاستراتيجيات يؤدي الى التخلص من مشكلة الكسيرات وبالتالي زيادة استغلال معالجات النظام.
معظم استراتيجيات التخصيص غير المتجاور في متعددات الحواسيب الشبكية الموجودة حالياً تعاني من مشكلة الكسيرات والتداخل بين الرسائل ضمن المهام المختلفة داخل النظام بالإضافة إلى حاجتها إلى الشكل المنتظم (المستطيل) في التخصيص اذا كان هناك اي تجاور ما بين المعالجات، لذلك فقد اقترحنا في هذه الرسالة إستراتيجية تخصيص غير متجاور جديدة تسمى إستراتيجية الشكل الغير منتظم (Irregular Shape Allocation Strategy) (ISA) والتي تحد من مشكلة الكسيرات وتخفف من التداخل بين الرسائل ضمن الشبكة، حيث كانت الفكرة الرئيسية من الاستراتيجية الجديدة أنه للحصول على درجة من التجاور ما بين المعالجات المخصصة لمهمة معينه، فإن ذلك لا يشترط ان يكون شكل شبكة المعالجات المخصصة للمهمة منتظماً (على شكل مستطيل) كما هو في الاستراتيجيات السابقة الأخرى, حيث أن الشبكة الفرعية المخصصة يمكن أن تكون على أي شكل (منتظم أو غير منتظم) وهذا يؤدي بدوره إلى تحسين اداء النظام من حيث معدل مكوث المهام في النظام وكذلك معدل استغلال المعالجات في النظام.
تمت مقارنة اداء الخوارزمية الجديدة (ISA) مع اداء استراتيجيات التخصيص المتجاور ممثلة باستراتيجية الـ (First Fit) والغير متجاور ممثلة بالاستراتيجيات التالية (Random, Paging(0), Multiple Buddy Strategy) باستخدام المحاكاة، وقد أظهرت النتائج بإن اداء الاستراتيجية المقترحة (ISA) هو قريب جداً من اداء خوارزميات التخصيص غير المتجاور السابقة (Paging(0) and Multiple Buddy Strategy)، وذلك عند استخدام نمط التراسل (One to All)، في حين انها افضل من استراتيجية التخصيص غير المتجاور (Random) وكذلك افضل من اداء استراتيجية التخصيص المتجاور (First Fit)، كما أظهرت النتائج أن اداء الاستراتيجية المقترحة (ISA) افضل من اداء الاستراتيجيات الاخرى المتجاورة والغير متجاورة عند استخدام نمطي التراسل (Random and All to All)، في حين أظهرت النتائج أن اداء استراتيجيات التخصيص المتجاور ممثلة بالـ (First Fit) افضل من اداء استراتيجيات التخصيص غير المتجاور عند استخدام نمط التراسل (Near Neighbor).
|
الملخص بالانجليزي |
Contiguous and non-contiguous processor allocation strategies are two categories of the processor allocation strategies used to allocate an incoming job request in the mesh-connected multicomputer. Contiguous allocation suffers from high processor fragmentations as the processors allocated to a job are physically contiguous and have the same topology as that of the interconnection network of the multicomputer. This leads to a degradation in system performance in terms of average turnaround time of jobs and mean system utilization. In non-contiguous allocation, a job can execute on separate smaller sub-meshes rather than waiting until a single sub-mesh of the requested size and rectangular shape is available. Although non-contiguous allocation increases message contention inside the network, lifting the contiguity condition can reduce processor fragmentation and increase system utilization. Most existing non-contiguous allocation strategies that have been suggested for the mesh suffer from processor fragmentation and message contention inside the network. In addition, the allocated sub-meshes should be in regular shapes. In this thesis, we present a new non-contiguous allocation strategy, referred to as irregular shape allocation (ISA) strategy that eliminates processor fragmentation and alleviates the contention inside the network. The main idea of ISA is that it does not depend on rectangular shape as other previous allocation strategies, where the allocated sub-meshes in ISA can be in any shape (regular or irregular), in order to improve the system performance in terms of job turnaround time and system utilization. We compare the performance of ISA with that of the well-known contiguous and non-contiguous allocation strategies. The simulation results have shown that the ISA allocation strategy has the same performance in terms of both job turnaround time and system utilization as Paging(0) and MBS when the communication pattern used is one to all, and better performance in terms of both job turnaround time and system utilization than that of the previous allocation strategies considered in this thesis when the communication patterns used are all to all and random. While the result show that the contiguous allocation strategy perform better than non contiguous allocation strategy in terms of job turnaround time when communication pattern used is near neighbor |
رقم ISN |
4883 |
|
للحصول على الرسالة كملف يرجى تزويد المكتبة برقم ISN
|
|