{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:20:12Z","timestamp":1736572812021,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540649526"},{"type":"electronic","value":"9783540499206"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0057870","type":"book-chapter","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T15:01:27Z","timestamp":1154444487000},"page":"328-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On optimal k-iinear scheduling of tree-like task graphs for LogP-machines"],"prefix":"10.1007","author":[{"given":"Wolf","family":"Zimmermann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Middendorf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weif","family":"L\u00f6we","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,6,30]]},"reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0743-7315(90)90116-7","volume":"9","author":"F.D. Anger","year":"1990","unstructured":"F.D. Anger, J. Hwang, and Y. Chow. Scheduling with sufficient loosely coupled processors. Journal of Parallel and Distributed Computing, 9:87\u201392, 1990.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0377-2217(89)90216-6","volume":"2","author":"P. Chretienne","year":"1989","unstructured":"P. Chretienne. A polynomial algorithm to optimally schedule tasks over an ideal distributed system under tree-like precedence constraints. European Journal of Operations Research, 2:225\u2013230, 1989.","journal-title":"European Journal of Operations Research"},{"doi-asserted-by":"crossref","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: Towards a realistic model of parallel computation. In 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 93), pp. 1\u201312, 1993. published in: SIGPLAN Notices (28) 7.","key":"36_CR3","DOI":"10.1145\/173284.155333"},{"issue":"11","key":"36_CR4","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/240455.240477","volume":"39","author":"D. Culler","year":"1996","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: A practical model of parallel computation. Communications of the ACM, 39(11):78\u201385, 1996.","journal-title":"Communications of the ACM"},{"unstructured":"S. Darbha and D.P. Agrawal. SBDS: A task duplication based optimal algorithm. In Scalable High Performance Conference, 1994.","key":"36_CR5"},{"doi-asserted-by":"crossref","unstructured":"B. Di Martino and G. Ianello. Parallelization of non-simultaneous iterative methods for systems of linear equations. In Parallel Processing: CONPAR 94 \u2014 VAPP VI, volume 854 of Lecture Notes in Computer Science, pp. 253\u2013264. Springer, 1994.","key":"36_CR6","DOI":"10.1007\/3-540-58430-7_23"},{"doi-asserted-by":"crossref","unstructured":"J. Eisenbiegler, W. L\u00f6we, and W. Zimmermann. Optimizing parallel programs on machines with expensive communication. In Europar\u2019 96 Parallel Processing Vol. 2, volume 1124 of Lecture Notes in Computer Science, pp. 602\u2013610. Springer, 1996.","key":"36_CR7","DOI":"10.1007\/BFb0024754"},{"doi-asserted-by":"crossref","unstructured":"Jrn Eisenbiegler, Welf L\u00f6we, and Andreas Wehrenpfennig. On the optimization by redundancy using an extended LogP model. In International Conference on Advances in Parallel and Distributed Computing (APDC\u201997), pp. 149\u2013155. IEEE Computer Society Press, 1997.","key":"36_CR8","DOI":"10.1109\/APDC.1997.574026"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/71.242154","volume":"4","author":"A. Gerasoulis","year":"1993","unstructured":"A. Gerasoulis and T. Yang. On the granularity and clustering of directed acyclic task graphs. IEEE Transactions on Parallel and Distributed Systems, 4:686\u2013701, June 1993.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"16","author":"J.A. Hoogreven","year":"1994","unstructured":"J.A. Hoogreven, J.K. Lenstra, and B. Veltmann. Three, four, five, six or the complexity of scheduling with communication delays. Operations Research Letters, 16:129\u2013137, 1994.","journal-title":"Operations Research Letters"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1006\/inco.1993.1041","volume":"105","author":"H. Jung","year":"1993","unstructured":"H. Jung, L. M. Kirousis, and P. Spirakis. Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays. Information and Computation, 105:94\u2013104, 1993.","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"I. Kort and D. Trystram. Scheduling fork graphs under LogP with an unbounded number of processors. Submitted to Europar \u201998, 1998.","key":"36_CR12","DOI":"10.1007\/BFb0057951"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"E.L. Lawler","year":"1973","unstructured":"E.L. Lawler. Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19:544\u2013546, 1973.","journal-title":"Management Science"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1006\/jagm.1996.0007","volume":"20","author":"J.K. Lenstra","year":"1996","unstructured":"J.K. Lenstra, M. Veldhorst, and B. Veltmann. The complexity of scheduling trees with communication delays. Journal of Algorithms, 20:157\u2013173, 1996.","journal-title":"Journal of Algorithms"},{"doi-asserted-by":"crossref","unstructured":"W. L\u00f6we and W. Zimmermann. On finding optimal clusterings in task graphs. In N. Mirenkov, editor, Parallel Algorithms\/Architecture Synthesis pAs\u201995, pp. 241\u2013247. IEEE, 1995.","key":"36_CR15","DOI":"10.1109\/AISPAS.1995.401333"},{"unstructured":"W. L\u00f6we and W. Zimmermann. Programming data-parallel \u2014 executing process parallel. In P. Fritzson and L. Finmo, editors, Parallel Programming and Applications, pp. 50\u201364. IOS Press, 1995.","key":"36_CR16"},{"doi-asserted-by":"crossref","unstructured":"W. Lwe and W. Zimmermann. Upper time bounds for executing PRAM-programs on the LogP-machine. In M. Wolfe, editor, Proceedings of the 9th ACM International Conference on Supercomputing, pp. 41\u201350. ACM, 1995.","key":"36_CR17","DOI":"10.1145\/224538.224543"},{"key":"36_CR18","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1007\/BFb0002832","volume":"1300","author":"W. L\u00f6we","year":"1997","unstructured":"Welf L\u00f6we, Wolf Zimmermann, and J\u00f6rn Eisenbiegler. On linear schedules for task graphs for generalized LogP-machines. In Europar\u201997: Parallel Processing, volume 1300 of Lecture Notes in Computer Science, pp. 895\u2013904, 1997.","journal-title":"Lecture Notes in Computer Science"},{"unstructured":"W. Lwe, J. Eisenbiegler, and W. Zimmermann. Optimizing parallel programs on machines with fast communication. In 9. International Conference on Parallel and Distributed Computing Systems, pp. 100\u2013103, 1996.","key":"36_CR19"},{"unstructured":"M. Middendorf, W. L\u00f6we, and W. Zimmermann. Scheduling inverse trees under the communication model of the LogP-machine. Accepted for publication in Theoretical Computer Science.","key":"36_CR20"},{"issue":"2","key":"36_CR21","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0219021","volume":"19","author":"C.H. Papadimitriou","year":"1990","unstructured":"C.H. Papadimitriou and M. Yannakakis. Towards an architecture-independent analysis of parallel algorithms. SIAM Journal on Computing, 19(2):322\u2013328, 1990.","journal-title":"SIAM Journal on Computing"},{"unstructured":"C. Picouleau. New complexity results on the uet-uct scheduling algorithm. In Proc. Summer School on Scheduling Theory and its Applications, pp. 187\u2013201, 1992.","key":"36_CR22"},{"key":"36_CR23","first-page":"186","volume":"II","author":"J. Siddhiwala","year":"1995","unstructured":"J. Siddhiwala and L.-F. Cha. Path-based task replication for scheduling with communication cost. In Proceedings of the International Conference on Parallel Processing, volume II, pp. 186\u2013190, 1995.","journal-title":"Proceedings of the International Conference on Parallel Processing"},{"unstructured":"J. Verriet. Scheduling tree-structured programs in the LogP-model. Technical Report UU-CS-1997-18, Dept. of Computer Science, Utrecht University, 1997.","key":"36_CR24"},{"issue":"9","key":"36_CR25","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1109\/71.308533","volume":"5","author":"T. Yang","year":"1994","unstructured":"T. Yang and A. Gerasoulis. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems, 5(9):951\u2013967, 1994.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"doi-asserted-by":"crossref","unstructured":"W. Zimmermann and W. L\u00f6we. An approach to machine-independent parallel programming. In Parallel Processing: CONPAR 94 \u2014 VAPP VI, volume 854 of Lecture Notes in Computer Science, pp. 277\u2013288. Springer, 1994.","key":"36_CR26","DOI":"10.1007\/3-540-58430-7_25"}],"container-title":["Lecture Notes in Computer Science","Euro-Par\u201998 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0057870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T08:13:23Z","timestamp":1736496803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0057870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649526","9783540499206"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0057870","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"30 June 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}