Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters....
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116477 |
| _version_ | 1826193730905833472 |
|---|---|
| author | Murray, Riley Khuller, Samir Chao, Megan C. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Murray, Riley Khuller, Samir Chao, Megan C. |
| author_sort | Murray, Riley |
| collection | MIT |
| description | The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem. |
| first_indexed | 2024-09-23T09:44:01Z |
| format | Article |
| id | mit-1721.1/116477 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:44:01Z |
| publishDate | 2018 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1164772022-09-26T13:26:33Z Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms Murray, Riley Khuller, Samir Chao, Megan C. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chao, Megan C. The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem. National Science Foundation (U.S.) National Science Foundation (U.S.). Research Experience for Undergraduates (Program) (Grant CCF 1262805) Winkler Foundation 2018-06-21T17:00:22Z 2018-06-21T17:00:22Z 2017-07 2016-09 2018-05-31T05:10:36Z Article http://purl.org/eprint/type/JournalArticle 0178-4617 1432-0541 http://hdl.handle.net/1721.1/116477 Murray, Riley, Samir Khuller, and Megan Chao. “Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-Based Approximation Algorithms.” Algorithmica 80, no. 10 (July 19, 2017): 2777–2798. en https://doi.org/10.1007/s00453-017-0345-x Algorithmica Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media, LLC application/pdf Springer-Verlag Springer US |
| spellingShingle | Murray, Riley Khuller, Samir Chao, Megan C. Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title | Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title_full | Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title_fullStr | Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title_full_unstemmed | Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title_short | Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms |
| title_sort | scheduling distributed clusters of parallel machines primal dual and lp based approximation algorithms |
| url | http://hdl.handle.net/1721.1/116477 |
| work_keys_str_mv | AT murrayriley schedulingdistributedclustersofparallelmachinesprimaldualandlpbasedapproximationalgorithms AT khullersamir schedulingdistributedclustersofparallelmachinesprimaldualandlpbasedapproximationalgorithms AT chaomeganc schedulingdistributedclustersofparallelmachinesprimaldualandlpbasedapproximationalgorithms |