{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T02:19:53Z","timestamp":1772849993835,"version":"3.50.1"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>Scientific applications are usually described using directed acyclic graphs, where nodes represent tasks and edges represent dependencies between tasks. For some applications, this graph is a tree: each task produces a single result used solely by its parent. The temporary results of each task have to be stored between their production and their use.<\/jats:p><jats:p>We focus on the case when the data manipulated are very large. Then, during an execution, all data may not fit together in memory. In such a case, some data have to be temporarily written to disk and evicted from memory. These data are later read from disk when they are needed for computation.<\/jats:p><jats:p>These Input\/Output operations are very expensive; hence, our goal is to minimize their total volume. The order in which the tasks are processed considerably influences the amount of such Input\/Output operations. Finding the schedule which minimizes this amount is an open problem that we revisit in this paper.<\/jats:p><jats:p>We first formalize and generalize known results, and prove that existing solutions can be arbitrarily worse than the optimal. We then present an Integer Linear Program to solve it optimally. Finally, we propose a novel heuristic algorithm. We demonstrate its good performance through simulations on both synthetic and realistic trees built from actual scientific applications.<\/jats:p>","DOI":"10.1142\/s0129054122500186","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T08:40:55Z","timestamp":1658738455000},"page":"51-80","source":"Crossref","is-referenced-by-count":2,"title":["Minimizing I\/Os in Out-of-Core Task Tree Scheduling"],"prefix":"10.1142","volume":"34","author":[{"given":"Loris","family":"Marchal","sequence":"first","affiliation":[{"name":"CNRS, INRIA, ENS Lyon and University of Lyon, LIP, ENS Lyon, 46 all\u00e9e d\u2019Italie, Lyon, 69007, France"}]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[{"name":"Williams College, 880 Main St., Williamstown MA 01267 USA"}]},{"given":"Bertrand","family":"Simon","sequence":"additional","affiliation":[{"name":"IN2P3 Computing Center\/CNRS, 21 Av. Pierre de Coubertin, 69100, Villeurbanne, France"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Vivien","sequence":"additional","affiliation":[{"name":"CNRS, INRIA, ENS Lyon and University of Lyon, LIP, ENS Lyon, 46 all\u00e9e d\u2019Italie, Lyon, 69007, France"}]}],"member":"219","published-online":{"date-parts":[[2022,7,22]]},"reference":[{"issue":"3","key":"S0129054122500186BIB001","doi-asserted-by":"crossref","first-page":"C256","DOI":"10.1137\/130938505","volume":"38","author":"Agullo E.","year":"2016","journal-title":"SIAM J. Scientific Comput."},{"key":"S0129054122500186BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"issue":"2","key":"S0129054122500186BIB004","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.parco.2005.07.004","volume":"32","author":"Amestoy P. R.","year":"2006","journal-title":"Parallel Comput."},{"issue":"2","key":"S0129054122500186BIB006","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"Belady L. A.","year":"1966","journal-title":"IBM Syst. J."},{"issue":"4","key":"S0129054122500186BIB007","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"Correa J. R.","year":"2005","journal-title":"Math. Operat. Res."},{"key":"S0129054122500186BIB008","series-title":"Fundamentals of Algorithms","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718881","volume-title":"Direct Methods for Sparse Linear Systems","volume":"2","author":"Davis T. A.","year":"2006"},{"key":"S0129054122500186BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"issue":"2","key":"S0129054122500186BIB010","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2779052","volume":"2","author":"Eyraud-Dubois L.","year":"2015","journal-title":"TOPC"},{"key":"S0129054122500186BIB011","series-title":"IEEE","first-page":"285","volume-title":"Foundations of Computer Science, 1999. 40th Annual Symposium on","author":"Frigo M.","year":"1999"},{"key":"S0129054122500186BIB012","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.34.5390"},{"key":"S0129054122500186BIB013","first-page":"556","volume-title":"Proc. 25th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS\u201911)","author":"Jacquelin M.","year":"2011"},{"key":"S0129054122500186BIB014","first-page":"326","volume-title":"Proc. 13th Ann. ACM Symp. Theory of Computing, STOC \u201981","author":"Jia-Wei H.","year":"1981"},{"key":"S0129054122500186BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.cl.2010.09.003"},{"issue":"2","key":"S0129054122500186BIB016","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.ipl.2015.09.004","volume":"116","author":"Lee M.","year":"2016","journal-title":"Inf. Process. Lett."},{"key":"S0129054122500186BIB017","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-94-011-0193-6_2","volume-title":"Quantum Mechanical Electronic Structure Calculations with Chemical Accuracy","author":"Lee T. J.","year":"1995"},{"issue":"3","key":"S0129054122500186BIB018","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1145\/7921.11325","volume":"12","author":"Liu J. W.","year":"1986","journal-title":"ACM Trans. Mathematical Software (TOMS)"},{"issue":"3","key":"S0129054122500186BIB019","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0608031","volume":"8","author":"Liu J. W. H.","year":"1987","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"S0129054122500186BIB020","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/0611010","volume":"11","author":"Liu J. W. H.","year":"1990","journal-title":"SIAM J. Matrix Analysis and Applications"},{"issue":"1","key":"S0129054122500186BIB021","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0020-0255(98)10080-4","volume":"115","author":"M\u00e4kinen E.","year":"1999","journal-title":"Inform. Sci."},{"key":"S0129054122500186BIB022","doi-asserted-by":"crossref","unstructured":"J. M. L. Martin, Benchmark Studies on Small Molecules, Encyclopedia of Computational Chemistry, Vol. 1 (Wiley, New York, NY, 1998), pp. 115\u2013128.","DOI":"10.1002\/0470845015.cba001"},{"key":"S0129054122500186BIB023","first-page":"419","volume-title":"Proc. 32nd ACM Symp. Parallelism in Algorithms and Architectures","author":"Papp P. A.","year":"2020"},{"key":"S0129054122500186BIB024","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/978-1-4939-2092-1_22","volume-title":"Handbook on Data Centers","author":"Saule E.","year":"2015"},{"issue":"4","key":"S0129054122500186BIB025","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1145\/321607.321620","volume":"17","author":"Sethi R.","year":"1970","journal-title":"J. ACM"},{"key":"S0129054122500186BIB026","first-page":"161","volume-title":"External Memory Algorithms, Proceedings of a DIMACS Workshop","author":"Toledo S.","year":"1998"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122500186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T22:53:51Z","timestamp":1700866431000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122500186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,22]]},"references-count":24,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1142\/S0129054122500186"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122500186","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,22]]}}}