Title:
One-Dimensional
Partitioning for Heterogeneous Systems: Theory and Practice
Authors:
A.
Pinar, E.K. Tabak and C. Aykanat
Status:
Published in Journal
of Parallel and Distributed Computing
, vol.
68, pp. 1473–1486, 2008.
Abstract:
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.