Task scheduling is a key element in achieving high performance from multicomputer systems. Efficient scheduling algorithms reduce the interprocessor communication and improve processor utilization. To do so effectively, such algorithms must be based on a communication cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a range of differing scheduling conditions (graph types, granularities and cost or architectural models). Unfortunately, due both to the variety of systems available and the rate at which these systems evolve, an appropriate representative cost model has yet to be established. In this paper we study the problem of task scheduling under a LogP-type model and we present both theoretical and experimental results for a cluster-based, task duplication methodology. The model is not only representative of parallel systems but also incorporates the traditional model used by the scheduling community. Results show that, for this model, an algorithm based on this LogP scheduling methodology can generate good makespans.
Get full access to this article
View all access options for this article.
References
1.
Aggarwal, A., Chandra, A., and Snir, M. 1989. On communication latency in PRAM computations. Technical Report RE RC 14973, IBM T.J. Watson Research Center, Yorktown Heights, NY, USA.
2.
Al-Maasarani, A. 1993. Priority-based scheduling and evaluation of precedence graphs with communication times. Master's thesis, King Fahd University of Petroleum and Minerals, Saudi Arabia.
3.
Al-Mouhammed, M. 1990. Lower bound on the number of processors and time for scheduling precedence graphs with communication costs. IEEE Transactions on Software Engineering,16(12): 1390-1301 .
4.
Alexandrov, A., Ionescu, M., Schauser, K., and Scheiman, C. 1995. LogGP: Incorporating long messages into the LogP model - One step closer towards a realistic model for parallel computation . In Proceedings of the 7th Annual Symposium on Parallel Algorithms and Architectures (SPAA '95).
5.
Allcock, B., Foster, I., Nefedova, V., Chervenak, A., Kesselman, E. D. C., Lee, J., Sim, A., Shoshani, A., Drach, B., and Williams, D. 2001. High performance remote access to climate simulation data: A challenge problem for data grid technologies . In Proceedings of the IEEE Supercomputing Conference, Denver, USA.
6.
Anderson, D. P., Cobb, J., Korpela, E., Lebofsky, M., and Werthimer, D. 2002. SETI@home: An experiment in public-resource computing. Communications of the ACM,45(11): 56-61 .
7.
Anderson, T., Culler, D., and Patterson, D. 1995. A case for NOW (Networks of Workstations). IEEE Micro,15(1): 23-39 .
8.
Baker, M. and Buyya, R. 1999. Cluster Computing at a Glance. In Buyya, R., editor, High Performance Cluster Computing: Architectures and Systems, Prentice Hall, USA . chap. 1, pp. 3-47.
9.
Basney, J., Livny, M., and Mazzanti, P. 2000. Harnessing the capacity of computational grids for high energy physics . In Proceedings of the Conference on Computing in High Energy and Nuclear Physics.
10.
Blazewicz, J., Bouvry, P., Guinand, F., and Trystram, D. 1996. Scheduling complete intrees on two uniform processors with communication delays. Information Processing Letters,5(58): 255-263 .
11.
Boeres, C. 1997. Versatile Communication Cost Modelling for Multicomputer Task Scheduling Heuristics. PhD thesis, Department of Computer Science, University of Edinburgh.
12.
Boeres, C., Cunha, G., and Rebello, V. 2001. On minimising the processor requirements of LogP schedules . In Sakellariou, R., Keane, J., Gurd, J., and Freeman, L., editors, The Proceedings of the 7th International Euro-Par Conference on Parallel Computing (EuroPar 2001), LNCS 2150, Manchester, UK. Springer. pp. 156-165 .
13.
Boeres, C., Nascimento, A., and Rebello, V. 1999a. Scheduling arbitrary task graphs on LogP machines . In Amestoy, P., Berger, P., Daydé, M., Duff, I., Frayssé, V., Giraud, L., and Ruiz, D., editors, Proceedings of the 5th International Euro-Par Conference on Parallel Processing (Euro-Par'99), LNCS 1685, Toulouse, France. Springer. pp. 340-349 .
14.
Boeres, C., Nascimento, A. P., and Rebello, V. E. F. 1999b. Cluster-based task scheduling for LogP model. International Journal of Foundations of Computer Science,10(4): 405-424 .
15.
Boeres, C. and Rebello, V. 1997. Versatile task scheduling of binary trees for realistic machines . In Lengauer, C., Griebl, M., and Gorlatch, S., editors, Proceedings of the 3rd International Euro-Par Conference on Parallel Processing (Euro-Par'97), LNCS 1300, Passau, Germany. Springer-Verlag. pp. 913-921 .
16.
Boeres, C. and Rebello, V. 2001. On the design of clustering-based scheduling algorithms for realistic machine models . In Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS'01), San Francisco, USA. IEEE Computer Society Press.
17.
Boeres, C., Rebello, V., and Skillicorn, D. 1998. Static scheduling using task replication for LogP and BSP models . In Pritchard, D. and Reeve, J., editors, Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par'98), LNCS 1470, Southampton, UK. Springer. pp. 337-346 .
18.
Boeres, C. and Rebello, V. E. F. 1999. A versatile cost modelling approach for multicomputer task scheduling. Parallel Computing,25(1): 63-86 .
19.
Buyya, R., editor. 1999. High Performance Cluster Computing: Architectures and Systems. Vol. 1. Prentice Hall, USA .
20.
Buyya, R. 2001. The virtual laboratory project: Molecular modeling for drug design on the grid. IEEE Distributed Systems Online,2(5).
21.
Chung, Y. C. and Ranka, S. 1992. Applications and performance analysis of a compile time optimization approach for list scheduling. In Proceedings of Supercomputing '92, pp. 512-521.
22.
Colin, J. and Chrétienne, P. 1991. C.P.M. scheduling with small communication delays and task duplication. Operations Research,39(4): 680-684 .
23.
Cosnard, M. and Jeannot, E. 2001. Automatic parallelization techniques based on compact DAG extraction and symbolic scheduling. Parallel Processing Letters,11(1): 151-168 .
24.
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K., Santos, E., Subramonian, R., and von Eicken, T. 1993. LogP: Towards a realistic model of parallel computation . In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, USA.
25.
Darbha, S. and Agrawal, D. 1994. A task duplication based optimal scheduling algorithm for variable execution time tasks . In Tai, K., editor, International Conference on Parallel Processing, vol. 2, pp. 52-56 .
26.
Di Martino, B. and Ianello, G. 1994. Parallelization on non-simultaneous iterative methods for systems of linear equations. In Parallel Processing (CONPAR'94-VAPP VI), LNCS 854, Springer-Verlag . pp. 254-264.
Eisenbiergler, J., Lowe, W., and Wehrenpfennig, A. 1997. On the optimization by redundancy using an extended LogP model . In Proceedings of the International Conference on Advances in Parallel and Distributed Computing (APDC'97), IEEE Computer Society Press. pp. 149-155 .
29.
Fortune, S. and Wyllie, J. 1978. Parallelism in random access machines . In Proceedings of 10th Annual ACM Symposium on Theory of Computing, ACM Press. pp. 114-118
30.
Foster, I. and Kesselman, C., editors. 1999. The GRID: Blueprint for a New Computing Infrastructure. Morgan Kaufmann .
31.
Gao, L., Rosenberg, A. L., and Sitaraman, R. 1995. Optimal architecture-independent scheduling of fine-grain tree-sweep computations . In Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing, pp. 620-629 .
32.
Gerasoulis, A. and Yang, T. 1992. A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors. Journal of Parallel and Distributed Computing,16: 276-291 .
33.
Gerasoulis, A. and Yang, T. 1993. On the granularity and clustering of directed acyclic task graphs . IEEE Transactions on Parallel and Distributed Systems,4(6): 686-701 .
34.
Gerasoulis, A. and Yang, T. 1994. DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems,5(9): 951-967 .
35.
Giest, A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R., and Sunderam, V. 1994. PVM: Parallel Virtual Machine - A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press .
Jung, H., Kirousis, L., and Spirakis, P. 1993. Lower bounds and efficient algorithms for multiprocessor scheduling of DAGs with communication delays. Information and Computaion,105: 94-104 .
38.
Kalinowski, T., Kort, I., and Trystram, D. 2000. List scheduling of general task graphs under LogP. Parallel Computing,26(9): 1109-1128 .
39.
Khan, A., McCreary, C., and Jones, M. 1994. Comparison of multiprocessor scheduling heuristics . In Tai, K., editor, Proc. of the 8th International Parallel Processing, Cancun, Mexico. IEEE Computer Society Press - ACM SIGARCH. vol. II, pp. 243-250 .
40.
Kielmann, T., Bal, H., Gorlatch, S., Verstoep, K., and Hofman, R. 2001. Network performance-aware collective communication for clustered wide area systems. Parallel Computing,27(11): 1431-1456 .
41.
Kim, S. and Browne, J. 1988. A general approach to mapping of parallel computations upon multiprocessor architectures . In Proceedings of the 3rd International Conference on Parallel Processing, pp. 1-8 .
42.
Kort, I. and Trystram, D. 1998. Scheduling fork graphs under LogP with an unbounded number of processors . In Pritchard, D. and Reeve, J., editors, The Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par'98), LNCS 1470, Southampton, UK. Springer. pp. 940-943 .
43.
Kruatrachue, B. and Lewis, T. 1988. Grain size determination for parallel programming. IEEE Software,23-32 .
44.
Kwok, Y. K. and Ahmad, I. 1998. On exploiting task duplication in parallel program scheduling. IEEE Transactions on Parallel and Distributed Systems,9(9): 872-892 .
45.
Kwok, Y.-K. and Ahmad, I. 1999a. Benchmarking and comparison of the task graph scheduling algorithms. Journal of Parallel and Distributed Computing,59(3): 381-422 .
46.
Kwok, Y.-K. and Ahmad, I. 1999b. On parallelising the multiprocessor scheduling problem. IEEE Transactions on Parallel and Distributed Systems,10(4): 414-432 .
47.
Kwok, Y.-K. and Ahmad, I. 1999c. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys,31(4).
48.
Lowe, W. and Zimmermann, W. 2000. Scheduling balanced task-graphs to LogP-machines . Parallel Computing,26(9): 1083-1108 .
49.
Martin, R., Vahdat, A., Culler, D., and Anderson, T. 1997. Effects of communication latency, overhead, and bandwidth in a cluster architecture . In Proceedings of the 24th Annual International Symposium on Computer Architecture, pp. 85-97 .
50.
McCreary, C. and Gill, H. 1989. Automatic determination of grain size for efficient parallel programming. Comm. ACM,32(9): 1073-2078 .
51.
Middendorf, M., Lowe, W., and Zimmermann, W. 1999. Scheduling inverse trees under the communication model of LogP-machine. Theoretical Computer Science,215: 137-168 .
52.
Palis, M., Liou, J.-C., and Wei, D. 1996. Task clustering and scheduling for distributed memory parallel architectures. IEEE Transactions on Parallel and Distributed Systems,7(1): 46-55 .
53.
Papadimitriou, C. and Yannakakis, M. 1990. Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput.,19: 322-328 .
54.
Quinn, M. 1994. Parallel Computing Theory and Practice. McGraw-Hill, New York .
55.
Sarkar, V. 1989. Partitioning and Scheduling Parallel Programs for Multiprocessors. Pitman, London .
Shirazi, B., Chen, H., and Marquis, J. 1995. Comparative study of task duplication static scheduling versus clustering and non-clustering techniques. Concurrency: Practice and Experience,7(5): 371-390 .
58.
Skillicorn, D. B., Hill, J. M. D., and McColl, W. F. 1997. Questions and answers about BSP. Scientific Computing.
59.
Snir, M., Otto, S., Huss-Lederman, S., Walker, D., and Dongarra, J. 1996. MPI: The Complete Reference. MIT Press .
Tam, A. and Wang, C. 1999. Realistic communication model for parallel computing on cluster . In The Proceedings of the First IEEE International Workshop on Cluster Computing, Melbourne, Australia. IEEE Computer Society Press. pp. 92-101 .
62.
Trevisan, T. S., Costa, V. S., Whately, L., and Amorim, C. L. 2002. Distributed shared memory in kernel mode . In De Souza, A., de Amorim, C., and Reis Jr., N., editors, Proceedings of the 14th Symposium on Computer Architecture and High Performance Computing, IEEE Computer Society Press. pp. 159-166 .
63.
Valiant, L. 1990. A bridging model for parallel computation . Communications of the ACM,33: 103-111 .
64.
Verriet, J. 1998. Scheduling with Communication for Multiprocessor Computation. PhD thesis, Dept. of Computer Science, Utrecht University.
65.
Wu, M. and Gajski, D. 1990. Hypertool: A programming aid for message-passing systems. IEEE Transactions on Parallel and Distributed Systems,1(3): 330-343 .
66.
Zimmermann, W., Lowe, W., and Trystram, D. 2002. On scheduling send-graphs and receive-graphs under the LogP-model. Information Processing Letters,82(2): 83-92 .
67.
Zimmermann, W., Middendorf, M., and Lowe, W. 1998. On optimal k-linear scheduling of tree-like task graph on LogP-machines . In Pritchard, D. and Reeve, J., editors, The Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par'98), LNCS 1470, Southampton, UK. Springer. pp. 328-336 .
