{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:24Z","timestamp":1750307304964,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,7,18]],"date-time":"2011-07-18T00:00:00Z","timestamp":1310947200000},"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":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2011,7,18]]},"abstract":"<jats:p>With the advent of many-core architectures and strong need for Petascale (and Exascale) performance in scientific domains and industry analytics, efficient scheduling of parallel computations for higher productivity and performance has become very important. Further, movement of massive amounts (Terabytes to Petabytes) of data is very expensive, which necessitates affinity driven computations. Therefore, distributed scheduling of parallel computations on multiple places 1 needs to optimize multiple performance objectives: follow affinity maximally and ensure efficient space, time and message complexity. Simultaneous consideration of these objectives makes distributed scheduling a particularly challenging problem. In addition, parallel computations have data dependent execution patterns which requires online scheduling to effectively optimize the computation orchestration as it unfolds.<\/jats:p>\n          <jats:p>This paper presents an online algorithm for affinity driven distributed scheduling of multi-place 2 parallel computations. To optimize multiple performance objectives simultaneously, our algorithm uses a low time and message complexity mechanism for ensuring affinity and a randomized work-stealing mechanism within places for load balancing. Theoretical analysis of the expected and probabilistic lower and upper bounds on time and message complexity of this algorithm has been provided. On multi-core clusters such as Blue Gene\/P (MPP architecture) and Intel multicore cluster, we demonstrate performance close to the custom MPI+Pthreads code. Further, strong, weak and data (increasing input data size) scalability have been demonstrated on multi-core clusters. Using well known benchmarks, we demonstrate 16% to 30% performance gain as compared to Cilk [6] on multi-core Intel Xeon 5570 (NUMA) architecture. Detailed experimental analysis illustrates efficient space (main memory) utilization as well. To the best of our knowledge, this is the first time multi-objective affinity driven distributed scheduling algorithm has been designed, theoretically analyzed and experimentally evaluated in a multi-place setup for multi-core cluster architectures.<\/jats:p>","DOI":"10.1145\/2007183.2007186","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"14-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Performance driven multi-objective distributed scheduling for parallel computations"],"prefix":"10.1145","volume":"45","author":[{"given":"Ankur","family":"Narang","sequence":"first","affiliation":[{"name":"IBM Research - India, New Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhinav","family":"Srivastava","sequence":"additional","affiliation":[{"name":"IBM Research - India, New Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naga Praveen Kumar","family":"Katta","sequence":"additional","affiliation":[{"name":"IBM Research - India, New Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudrapatna K.","family":"Shyamasundar","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/341800.341801"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248416"},{"key":"e_1_2_1_3_1","volume-title":"Sun Microsystems, apr","author":"Allan Eric","year":"2005","unstructured":"Eric Allan , David Chase , Victor Luchangco , Jan-Willem Maessen , Sukyoung Ryu , Guy L. Steele Jr ., and Sam Tobin-Hochstadt . The Fortress language specification version 0.618. Technical report , Sun Microsystems, apr 2005 . Eric Allan, David Chase, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L. Steele Jr., and Sam Tobin-Hochstadt. The Fortress language specification version 0.618. Technical report, Sun Microsystems, apr 2005."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277678"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875608"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_7_1","volume-title":"USENIX Annual Technical Conference","author":"Robert","year":"1997","unstructured":"Robert D. Blumofe and Philip A. Lisiecki. Adaptive and reliable parallel computing on networks of workstations . In USENIX Annual Technical Conference , Anaheim, California , 1997 . Robert D. Blumofe and Philip A. Lisiecki. Adaptive and reliable parallel computing on networks of workstations. In USENIX Annual Technical Conference, Anaheim, California, 1997."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342007078442"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_2_1_10_1","volume-title":"Sep","author":"Exascale Study Group and Peter Kogge et.al.","year":"2008","unstructured":"Exascale Study Group and Peter Kogge et.al. Exascale computing study: Technology challenges in achieving exascale systems. Technical report , Sep 2008 . Exascale Study Group and Peter Kogge et.al. Exascale computing study: Technology challenges in achieving exascale systems. Technical report, Sep 2008."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1946143.1946158"},{"key":"e_1_2_1_12_1","first-page":"291","volume-title":"ISAAC (2)","author":"Tchiboukdjian Marc","year":"2010","unstructured":"Marc Tchiboukdjian , Nicolas Gast , Denis Trystram , Jean-Louis Roch , and Julien Bernard . A tighter analysis of work stealing . In ISAAC (2) , pages 291 -- 302 , 2010 . Marc Tchiboukdjian, Nicolas Gast, Denis Trystram, Jean-Louis Roch, and Julien Bernard. A tighter analysis of work stealing. In ISAAC (2), pages 291--302, 2010."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278177.1278183"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2007183.2007186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2007183.2007186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:58Z","timestamp":1750244398000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2007183.2007186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,18]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,7,18]]}},"alternative-id":["10.1145\/2007183.2007186"],"URL":"https:\/\/doi.org\/10.1145\/2007183.2007186","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2011,7,18]]},"assertion":[{"value":"2011-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}