Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

P. Kling, A. Mäcker, S. Riechers, A. Skopalik, in: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132.

Download
Restricted 59-progress.pdf 784.87 KB
Conference Paper | English
Author
Abstract
We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).
Publishing Year
Proceedings Title
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Page
123--132
LibreCat-ID

Cite this

Kling P, Mäcker A, Riechers S, Skopalik A. Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ; 2017:123--132. doi:10.1145/3087556.3087578
Kling, P., Mäcker, A., Riechers, S., & Skopalik, A. (2017). Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (pp. 123--132). https://doi.org/10.1145/3087556.3087578
@inproceedings{Kling_Mäcker_Riechers_Skopalik_2017, title={Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource}, DOI={10.1145/3087556.3087578}, booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Kling, Peter and Mäcker, Alexander and Riechers, Sören and Skopalik, Alexander}, year={2017}, pages={123--132} }
Kling, Peter, Alexander Mäcker, Sören Riechers, and Alexander Skopalik. “Sharing Is Caring: Multiprocessor Scheduling with a Sharable Resource.” In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 123--132, 2017. https://doi.org/10.1145/3087556.3087578.
P. Kling, A. Mäcker, S. Riechers, and A. Skopalik, “Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource,” in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132.
Kling, Peter, et al. “Sharing Is Caring: Multiprocessor Scheduling with a Sharable Resource.” Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132, doi:10.1145/3087556.3087578.
Main File(s)
File Name
59-progress.pdf 784.87 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T13:17:33Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar