The Performance of a Parallel TSP Program and Byte Sequential Benchmarks Executing on a Shared Cluster

Abstract

Although individual PCs of a cluster are used by their owners to run sequential applications (local jobs), the cluster as a whole or its subset can also be employed to run parallel applications (cluster jobs) even during working hours. This implies that these computers have to be shared by parallel and sequential applications, which could lead to the improvement of the execution performance and resource utilization. However, there is a lack of experimental study showing the behavior and performance of executing parallel and sequential applications concurrently on a non-dedicated cluster. The result of such research would be beneficial for the development of new global scheduling algorithms. We present the result of an experimental study into scheduling of a mixture of parallel and sequential applications on a non-dedicated cluster. The aim of this study is to learn how the concurrent execution of a communication intensive parallel application and sequential applications influences their execution performance and utilization of the cluster.

Keywords

non-dedicated clusters load-balancing scheduling performance evalution

Get full access to this article

View all access options for this article.

References

Acharya, A. , Edjlali, G. , and Saltz, J. (1997). The utility of exploiting idle workstations for parallel computation , in Proceedings of 1997 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems, pp. 225—236, Seattle, Washington, May.

Anglano, C. (2000). A comparative evaluation of implicit coscheduling strategies for networks of workstations , in Proceedings of 9th International Symposium on High Performance Distributed Computing (HPDC9) , pp. 221—228, Pittsburgh, PA, August.

Arpaci, R.H. , Dusseau, A.C. , Vahdat, A.M. , Liu, L.T. , Anderson, T.E. , and Patterson, D.A. (1995). The interaction of parallel and sequential workloads on a network of workstations , in Proceedings of 1995 ACM Joint International Conference on Measurement and Modeling of Computing Systems, pp. 267—278, Ottawa, Canada, May.

Barak, A. , Guday, S. , and Wheeler, R.G. (1993). The MOSIX Distributed Operating System, Load Balancing for UNIX, Springer-Verlag, Berlin , Germany.

Becker, W. (1995). Dynamic balancing complex workload in workstation networks — challenge, concepts and experience , in Proceedings High Performance Computing and Networking (HPCN) Europe Lecture Notes on Computer Science (LNCS), pp. 407—412.

Burns, G. , Daoud, R. , and Vaigl, J. (1994). LAM: An open cluster environment for MPI , in Proceedings of Supercomputing Symposium, University of Toronto, pp. 379—386.

Byte (n.d.). BYTE's UnixBench, The BYTE's Unix Benchmark Suite. URL: http://www.tux.org/pub/tux/niemi/unixbench , last access: June 2004.

Chuang, P.J. and Tzeng, N.F. (1992). A fast recognition-complete processor allocation strategy for hypercube computers , IEEE Transactions on Computers , 41(4): 467—479 .

Colwell, B. (2003). Benchmarketing competition , Computer , 36(12): 9—11 .

10.

Epema, D.H.J. , Livny, M. , van Dantzig, R. , Evers, X. , and Pruyne, J. (1996). A worldwide flock of Condors: Load sharing among workstation clusters , Future Generations of Computer Systems , 12: 53—65 .

11.

Feitelson, D.G. and Rudolph, L. (1992). Gang scheduling performance benefits for fine-grained synchronization , Journal of Parallel and Distributed Computing , 16(4): 306— 318 ,

12.

Goscinski, A.M. (1991). Distributed Operating Systems, The Logical Design , Sydney: Addison-Wesley .

13.

Lai, T.H. and Sahni, S. (1984). Anomalies in parallel branch-and-bound algorithms . Communications of the ACM, 27(6): 594—602 .

14.

Lo, S.P. and Gligor, V.D. (1987). A comparative analysis of multiprocessor scheduling algorithms , in Proceedings of the 7th International Conference on Distributed Computing Systems, pp. 205—222, Berlin, Germany, September.

15.

openMosix (n.d.). The openMosix Homepage. URL: http://openmosix.sourceforge.net, last access: June 2004.

16.

Ryu, K.D. and Hollingsworth, J.K. (1998). Linger longer: fine-grain cycle stealing for networks of workstations , in Proceedings of the 1998 ACM/IEEE Conference on Supercomputing (CDROM), pp. 1—12, San Jose, CA.

17.

Tandiary, F. , Kothari, S.C. , Dixit, A. , and Anderson, E.W. (1996). Batrun: Utilizing idle workstations for large-scale computing , IEEE Parallel and Distributed Technology, 4(2): 41—48 .

18.

The MPI Forum (1993). MPI: a message passing interface , In Proceedings of the 1993 Conference on Supercomputing, pp. 878—883, Portland, OR.

19.

Wong, F.C. , Arpaci-Dusseau, A.C. , and Culler, D.E. (1999). Building MPI for multi-programming systems using implicit information , in Proceedings of the 6th European PVM/MPI User's Group Meeting, pp. 215—222, Barcelona , Spain.

20.

Zhou, B.B. , Qu, X. , and Brent, R.P. (1998). Effective scheduling in a mixed parallel and sequential computing environment , in Proceedings of the 6th Euromicro Workshop of Parallel and Distributed Processing, pp. 32—37, Madrid, Spain, January.

21.

Zhu, Y. ( 1992). Efficient processor allocation strategies for mesh-connected parallel computers , Journal of Parallel and Distributed Computing , 16(4): 328—337 .