Efficient Online Scheduling for Coflow-aware Machine Learning Clusters

• Published in: IEEE Transactions on Cloud Computing
• Main Authors: Li, Wenxin, Chen, Sheng, Li, Keqiu, Qi, Heng, Xu, Renhai, Zhang, Song
• Format: Article in Journal/Newspaper
• Language: English
• Published: Ieee-inst Electrical Electronics Engineers Inc 2022
• Subjects: Coflow Scheduling; Dependent Coflows; Distributed Machine Learning; Multi-Stage Job; DML
• Online Access: https://repository.hkust.edu.hk/ir/Record/1783.1-109354; https://doi.org/10.1109/TCC.2020.3040312; http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=2168-7161&rft.volume=&rft.issue=&rft.date=2020&rft.spage=&rft.aulast=Li&rft.aufirst=&rft.atitle=Efficient+Online+Scheduling+for+Coflow-aware+Machine+Learning+Clusters&rft.title=IEEE+Transactions+on+Cloud+Computing; http://www.scopus.com/record/display.url?eid=2-s2.0-85097150313&origin=inward; http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000894810300024

Distributed machine learning (DML) is an increasingly important workload. In a DML job, each communication stage can comprise a coflow, and there are dependencies among its coflows. Thus, efficient coflow scheduling becomes critical for DML jobs. However, the majority of existing solutions focus on scheduling single-stage coflows with no dependencies. While there are a few studies schedule dependent coflows of multi-stage jobs, they suffer from either practical or theoretical issues. In this paper, we study how to schedule dependent coflows of multiple DML jobs to minimize the total job completion time (JCT) in a shared cluster. To solve this problem without any prior knowledge of job information, we present an online coflow-aware optimization framework called Parrot. The core idea in Parrot is to infer the job with the shortest remaining processing time (SRPT) each time and dynamically control the inferred job's bandwidth based on how confident it is an SRPT job while being mindful of not starving any other job. We have proved that Parrot algorithm has an approximation ratio of $O(M)$ , where M is the number of jobs. The results from large-scale trace-driven simulations further demonstrate that our Parrot can reduce the total JCT by up to 58.4%, compared to the state-of-the-art solution Aalo. IEEE