کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432135 688718 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
One-dimensional partitioning for heterogeneous systems: Theory and practice
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
One-dimensional partitioning for heterogeneous systems: Theory and practice
چکیده انگلیسی

We study the problem of one-dimensional partitioning of nonuniform workload arrays, with optimal load balancing for heterogeneous systems. We look at two cases: chain-on-chain partitioning, where the order of the processors is specified, and chain partitioning, where processor permutation is allowed. We present polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we prove that the chain partitioning problem is NP-complete. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics, while solution times remain comparable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 68, Issue 11, November 2008, Pages 1473–1486
نویسندگان
, , ,