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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 2008-11, Vol.68 (11), p.1473-1486
Main Authors: Pınar, Ali, Kartal Tabak, E., Aykanat, Cevdet
Format: Article
Language:English
Subjects:
Applied sciences
Chain-on-chain partitioning
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Dynamic programming
Exact sciences and technology
Load balancing
One-dimensional partitioning
Parallel computing
Parametric search
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0743-7315
1096-0848
DOI:10.1016/j.jpdc.2008.07.005