On optimal k-iinear scheduling of tree-like task graphs for LogP-machines

1. F.D. Anger, J. Hwang, and Y. Chow. Scheduling with sufficient loosely coupled processors. Journal of Parallel and Distributed Computing, 9:87–92, 1990.

   Article  Google Scholar 

2. 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–230, 1989.

   Article  MATH  MathSciNet  Google Scholar 

3. 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–12, 1993. published in: SIGPLAN Notices (28) 7.

   Google Scholar 

4. 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–85, 1996.

   Article  Google Scholar 

5. S. Darbha and D.P. Agrawal. SBDS: A task duplication based optimal algorithm. In Scalable High Performance Conference, 1994.

   Google Scholar 

6. B. Di Martino and G. Ianello. Parallelization of non-simultaneous iterative methods for systems of linear equations. In Parallel Processing: CONPAR 94 — VAPP VI, volume 854 of Lecture Notes in Computer Science, pp. 253–264. Springer, 1994.

   Google Scholar 

7. J. Eisenbiegler, W. Löwe, and W. Zimmermann. Optimizing parallel programs on machines with expensive communication. In Europar’ 96 Parallel Processing Vol. 2, volume 1124 of Lecture Notes in Computer Science, pp. 602–610. Springer, 1996.

   Google Scholar 

8. Jrn Eisenbiegler, Welf Löwe, and Andreas Wehrenpfennig. On the optimization by redundancy using an extended LogP model. In International Conference on Advances in Parallel and Distributed Computing (APDC’97), pp. 149–155. IEEE Computer Society Press, 1997.

   Google Scholar 

9. A. Gerasoulis and T. Yang. On the granularity and clustering of directed acyclic task graphs. IEEE Transactions on Parallel and Distributed Systems, 4:686–701, June 1993.

   Article  Google Scholar 

10. 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–137, 1994.

    Article  MathSciNet  Google Scholar 

11. 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–104, 1993.

    Article  MATH  MathSciNet  Google Scholar 

12. I. Kort and D. Trystram. Scheduling fork graphs under LogP with an unbounded number of processors. Submitted to Europar ’98, 1998.

    Google Scholar 

13. E.L. Lawler. Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19:544–546, 1973.

    Article  MATH  Google Scholar 

14. J.K. Lenstra, M. Veldhorst, and B. Veltmann. The complexity of scheduling trees with communication delays. Journal of Algorithms, 20:157–173, 1996.

    Article  MATH  MathSciNet  Google Scholar 

15. W. Löwe and W. Zimmermann. On finding optimal clusterings in task graphs. In N. Mirenkov, editor, Parallel Algorithms/Architecture Synthesis pAs’95, pp. 241–247. IEEE, 1995.

    Google Scholar 

16. W. Löwe and W. Zimmermann. Programming data-parallel — executing process parallel. In P. Fritzson and L. Finmo, editors, Parallel Programming and Applications, pp. 50–64. IOS Press, 1995.

    Google Scholar 

17. 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–50. ACM, 1995.

    Google Scholar 

18. Welf Löwe, Wolf Zimmermann, and Jörn Eisenbiegler. On linear schedules for task graphs for generalized LogP-machines. In Europar’97: Parallel Processing, volume 1300 of Lecture Notes in Computer Science, pp. 895–904, 1997.

    MATH  Google Scholar 

19. 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–103, 1996.

    Google Scholar 

20. M. Middendorf, W. Löwe, and W. Zimmermann. Scheduling inverse trees under the communication model of the LogP-machine. Accepted for publication in Theoretical Computer Science.

    Google Scholar 

21. C.H. Papadimitriou and M. Yannakakis. Towards an architecture-independent analysis of parallel algorithms. SIAM Journal on Computing, 19(2):322–328, 1990.

    Article  MATH  MathSciNet  Google Scholar 

22. C. Picouleau. New complexity results on the uet-uct scheduling algorithm. In Proc. Summer School on Scheduling Theory and its Applications, pp. 187–201, 1992.

    Google Scholar 

23. 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–190, 1995.

    Google Scholar 

24. J. Verriet. Scheduling tree-structured programs in the LogP-model. Technical Report UU-CS-1997-18, Dept. of Computer Science, Utrecht University, 1997.

    Google Scholar 

25. 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–967, 1994.

    Article  Google Scholar 

26. W. Zimmermann and W. Löwe. An approach to machine-independent parallel programming. In Parallel Processing: CONPAR 94 — VAPP VI, volume 854 of Lecture Notes in Computer Science, pp. 277–288. Springer, 1994.

    Google Scholar 

Download references