File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/INFOCOM41043.2020.9155445
- Scopus: eid_2-s2.0-85090283333
- WOS: WOS:000620945800107
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation
Title | Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation |
---|---|
Authors | |
Keywords | approximation theory computational complexity graph theory learning (artificial intelligence) scheduling |
Issue Date | 2020 |
Publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359 |
Citation | Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, Toronto, ON, Canada, 6-9 July 2020, p. 1053-1062 How to Cite? |
Abstract | The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines. |
Persistent Identifier | http://hdl.handle.net/10722/293457 |
ISSN | 2023 SCImago Journal Rankings: 2.865 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Han, Z | - |
dc.contributor.author | Tan, H | - |
dc.contributor.author | Jiang, S | - |
dc.contributor.author | Fu, X | - |
dc.contributor.author | Cao, W | - |
dc.contributor.author | Lau, FCM | - |
dc.date.accessioned | 2020-11-23T08:17:02Z | - |
dc.date.available | 2020-11-23T08:17:02Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications, Toronto, ON, Canada, 6-9 July 2020, p. 1053-1062 | - |
dc.identifier.issn | 0743-166X | - |
dc.identifier.uri | http://hdl.handle.net/10722/293457 | - |
dc.description.abstract | The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines. | - |
dc.language | eng | - |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359 | - |
dc.relation.ispartof | IEEE INFOCOM - IEEE Conference on Computer Communications | - |
dc.rights | IEEE INFOCOM - IEEE Conference on Computer Communications. Copyright © IEEE Computer Society. | - |
dc.rights | ©2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | - |
dc.subject | approximation theory | - |
dc.subject | computational complexity | - |
dc.subject | graph theory | - |
dc.subject | learning (artificial intelligence) | - |
dc.subject | scheduling | - |
dc.title | Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Lau, FCM: fcmlau@cs.hku.hk | - |
dc.identifier.authority | Lau, FCM=rp00221 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/INFOCOM41043.2020.9155445 | - |
dc.identifier.scopus | eid_2-s2.0-85090283333 | - |
dc.identifier.hkuros | 319178 | - |
dc.identifier.spage | 1053 | - |
dc.identifier.epage | 1062 | - |
dc.identifier.isi | WOS:000620945800107 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 0743-166X | - |