دانلود مقاله ISI انگلیسی شماره 79240
عنوان فارسی مقاله

الگوریتم زمان بندی کار با استفاده از تکرار به حداقل رسیده در سیستم های همگن

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79240 2008 11 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Task scheduling algorithm using minimized duplications in homogeneous systems
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Parallel and Distributed Computing, Volume 68, Issue 8, August 2008, Pages 1146–1156

کلمات کلیدی
تعادل بار و وظیفه تخصیص؛ پردازنده های موازی؛ برنامه ریزی و پارتیشن بندی کار؛ معماری های توزیع
پیش نمایش مقاله
پیش نمایش مقاله الگوریتم زمان بندی کار با استفاده از تکرار به حداقل رسیده در سیستم های همگن

چکیده انگلیسی

For fine grain task graphs, duplication-based scheduling algorithms are generally more efficient than list and cluster-based algorithms. However, most duplication-based heuristics try to duplicate all possible ancestor nodes of a given join node, in order to reduce the earliest start time (EST) of the join node, even though these ancestor nodes have already been allocated in previous steps. Thus, these duplication heuristics inevitably induce redundant duplications, which lead to the superfluous consumption of resources and generally deteriorate the scheduling result in the case of a bounded number of processors. When scheduling algorithms are used on an unbounded number of processors, the required number of processors grows excessively with the size of the task graph, thereby limiting the practicality of these algorithms for large task graphs. In this paper, we propose a novel algorithm designed to allocate join nodes without redundant duplications. In the proposed algorithm, if the ancestor nodes of a join node are duplicated when scheduling the join node, the original allocations of these ancestor nodes are removed using a very efficient method. The performance of the proposed algorithm, in terms of its normalized schedule length and efficiency, is compared with that of some of the recently proposed algorithms. The proposed algorithm generates better or comparable schedules with minimized duplication. Specifically, the simulation results show that it is most useful on a bounded number of processors.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.