{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:58:50Z","timestamp":1760597930567,"version":"3.41.0"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2019,12,4]]},"abstract":"<jats:p>Jobs in large-scale machine learning platforms are expressed using a computational graph of tasks with precedence constraints. To handle such precedence-constrained tasks that have machine-dependent communication demands in settings with heterogeneous service rates and communication times, we propose a new scheduling framework, Generalized Earliest Time First (GETF), that improves upon stateof- the-art results in the area. Specifically, we provide the first provable, worst-case approximation guarantee for the goal of minimizing the makespan of tasks with precedence constraints on related machines with machine-dependent communication times.<\/jats:p>","DOI":"10.1145\/3374888.3374897","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T14:07:24Z","timestamp":1575554844000},"page":"21-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Communication-Aware Scheduling of Precedence-Constrained Tasks"],"prefix":"10.1145","volume":"47","author":[{"given":"Yu","family":"Su","sequence":"first","affiliation":[{"name":"Caltech, Pasadena, CA, USA"}]},{"given":"Xiaoqi","family":"Ren","sequence":"additional","affiliation":[{"name":"Google, Mountain View, CA, USA"}]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"Caltech, Pasadena, CA, USA"}]},{"given":"Yuxiong","family":"He","sequence":"additional","affiliation":[{"name":"Microsoft, Redmond, WA, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0987"},{"key":"e_1_2_1_2_1","volume-title":"Computers and intractability: a guide to np-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and intractability: a guide to np-completeness , 1979 . M. R. Garey and D. S. Johnson. Computers and intractability: a guide to np-completeness, 1979."},{"key":"e_1_2_1_3_1","series-title":"SIAM journal on Applied Mathematics, 17(2):416--429","volume-title":"Bounds on multiprocessing timing anomalies","author":"Graham R. L.","year":"1969","unstructured":"R. L. Graham . Bounds on multiprocessing timing anomalies . SIAM journal on Applied Mathematics, 17(2):416--429 , 1969 . R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM journal on Applied Mathematics, 17(2):416--429, 1969."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218016"},{"key":"e_1_2_1_5_1","volume-title":"Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys (CSUR), 31(4):406--471","author":"Kwok Y.-K.","year":"1999","unstructured":"Y.-K. Kwok and I. Ahmad . Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys (CSUR), 31(4):406--471 , 1999 . Y.-K. Kwok and I. Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys (CSUR), 31(4):406--471, 1999."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.34"},{"key":"e_1_2_1_7_1","volume-title":"ACM","author":"Mayer R.","year":"2017","unstructured":"R. Mayer , C. Mayer , and L. Laich . The tensorflow partitioning and scheduling problem: it's the critical path! In Proceedings of the 1st Workshop on Distributed Infrastructures for Deep Learning, pages 1--6 . ACM , 2017 . R. Mayer, C. Mayer, and L. Laich. The tensorflow partitioning and scheduling problem: it's the critical path! In Proceedings of the 1st Workshop on Distributed Infrastructures for Deep Learning, pages 1--6. ACM, 2017."}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3374888.3374897","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3374888.3374897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:08Z","timestamp":1750199588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3374888.3374897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,12,4]]}},"alternative-id":["10.1145\/3374888.3374897"],"URL":"https:\/\/doi.org\/10.1145\/3374888.3374897","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"2019-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}