Task allocation in parallel and distributed computer system

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

The allocation problem is known to be NP-Hard in the most general case where both the number of modules and the number of processors is arbitrary, and it is also Np-Complete in some of the restricted cases. Also, the general scheduling problem, where no restrictions are imposed on the interconnection structure between modules, on the modules processing time and on the number of parallel processors, is NP-Hard in the strong sense. Even under some restrictions, the scheduling problem is NP-Hard. In some other restricted cases, it is known to be NP-Complete. In this thesis, we first review fifty algorithms on both the allocation and the scheduling problem. Next we suggest a reduced layered graph and a variation of Bokhari's [4,6,7] solution to the mapping chains of m tasks onto chains of n heterogeneous processors to achieve better space complexity. We also suggest two heuristic solutions for the same problem in both cases where processors are homogenous or heterogeneous in O(m) and O(nm) running time, respectively. We also adapt Lee and Shin [24] approach, to optimal task assignment in homogenous systems having an n-dimensional array or tree interconnection structure in the presence of attached tasks, on systems having a star graph interconnection structure. We generate the neighborhood tree and solve the problem with O(Nm³) running time where m is the number of tasks to be assigned, and N is the total number of nodes processors in the star graph. We mention that the suggested solution problem can be applied in the case of group graphs on any other type of graphs that can be generated by a permutation of a set of symbols. Finally, we generalize our result for systems having an arbitrary interconnection structure with a run time complexity of O(Nm³).

روابط وملفات

التعريف والنوع

رقم الوثيقة

03e29c06-c380-4505-930e-c6d09be1ac19

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

pdf text

أسماء الملفات

2294319_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" Jean G. Mina","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"Fouad Cliedid ","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

English

المصدر والدورية

اسم المصدر

Task allocation in parallel and distributed computer system

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

NP-complete problems - stationary systems with linear time

إشراف وإعداد

الإشراف

Fouad Cliedid

الإعداد

Jean G. Mina

الاقتباسات الببليوغرافية