Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation

Zhenhua Han, Haisheng Tan, Shaofeng H.C. Jiang, Xiaoming Fu, Wanli Cao, Francis C.M. Lau

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationINFOCOM 2020 - IEEE Conference on Computer Communications
Number of pages10
ISBN (Electronic)9781728164120
Publication statusPublished - Jul 2020
MoE publication typeA4 Article in a conference publication
EventIEEE Conference on Computer Communications - Online, Toronto, Canada
Duration: 6 Jul 20209 Jul 2020
Conference number: 38

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


ConferenceIEEE Conference on Computer Communications
Abbreviated titleINFOCOM


Dive into the research topics of 'Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation'. Together they form a unique fingerprint.

Cite this