کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331029 | 686440 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the efficiency of localized work stealing
ترجمه فارسی عنوان
در کارآیی دزدی کار محلی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های موازی، محاسبات چند مرحله ای، کار دزدی، بومی سازی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper investigates a variant of the work-stealing algorithm that we call the localized work-stealing algorithm. The intuition behind this variant is that because of locality, processors can benefit from working on their own work. Consequently, when a processor is free, it makes a steal attempt to get back its own work. We call this type of steal a steal-back. We show that the expected running time of the algorithm is T1/P+O(TâP), and that under the “even distribution of free agents assumption”, the expected running time of the algorithm is T1/P+O(Tâlgâ¡P). In addition, we obtain another running-time bound based on ratios between the sizes of serial tasks in the computation. If M denotes the maximum ratio between the largest and the smallest serial tasks of a processor after removing a total of O(P) serial tasks across all processors from consideration, then the expected running time of the algorithm is T1/P+O(TâM).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 100-106
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 100-106
نویسندگان
Warut Suksompong, Charles E. Leiserson, Tao B. Schardl,