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 have implemented polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we have implemented several heuristics for chain partitioning problem. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics while the solution times remain comparable.
The API documentation contains detailed information.
Library can be downloaded from hetccp.zip. To use the library, please extract the zip file to a directory. The jar files of the library as well as any dependent jar files will be extracted. To use the software, please refer to the API documentation. Source files are accessible through hetccp-src.zip.
Help requests and bug reports can be submitted to tabak@cs.bilkent.edu.tr.