کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
477647 1446174 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Competitive online scheduling of perfectly malleable jobs with setup times
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Competitive online scheduling of perfectly malleable jobs with setup times
چکیده انگلیسی

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ⩾ 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length pj running on kj processors to be pj/kj + (kj − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns kj so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ⩾ 2 and 4m/(m + 1) for odd m ⩾ 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 187, Issue 3, 16 June 2008, Pages 1126–1142
نویسندگان
, ,