Sage Journals: Discover world-class research

Abstract

In this paper, we address the problem of dynamically scheduling independent tasks and/or application task graphs on a GridRPC environment. Resources are assumed to compute submitted jobs within the time-share model. We present a non-intrusive predictive module, the historical trace manager (HTM), which is able to give the completion date of each task in the system. Four heuristics relying on its estimations are proposed and compared to the well-known minimum completion time (MCT) algorithm. We first analyze the accuracy of the HTM. Then we show with an extensive simulation study, and with numerous scenarios of execution performed on a real-world platform, that our heuristics outperform MCT on several metrics among which are the makespan and the response time.

Keywords

Dynamic scheduling heuristics multicriteria scheduling grid computing experimental evaluation

Get full access to this article

View all access options for this article.

References

Baker, K. R. 1974. Introduction to Sequencing and Scheduling, Wiley, New York .

Bender, M. A. , Chakrabarti, S. , and Muthukrishnan, S. 1998. Flow and stretch metrics for scheduling continuous job streams . Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA),San Francisco, CA, January 25–27.

Caniou, Y. and Jeannot, E. 2002. Dynamic mapping of a metatask on the grid: historical trace, minimum perturbation and minimum length heuristics. Technical Report 4620, LORIA, Nancy , October.

Caron, A., Desprez, F., Fleury, E., Lombard, F., Nicod, J.-M., Quinson, M., and Suter, F. 2002. Calcul rÉparti à grande Échelle, chapter “Une approche hiérarchique des serveurs de calculs”, Hermès Science, Paris.

Casanova, H. 2001. Simgrid: a toolkit for the simulation of application scheduling . Proceedings of the IEEE Symposium on Cluster Computing and the Grid (CCGrid’01), Brisbane, Australia, May 15–18, IEEE Computer Society Press, Los Alamitos, CA, pp. 430–437 .

Casanova, H. and Dongarra, J. 1996. Netsolve: A network server for solving computational science problems . Proceedings of Supercomputing, Pittsburg, PA.

Galassi, M. and Theiler, J. 1996. The Gnu Standard Library. Available at http://www.gnu.org/software/gsl/gsl.html.

Grimshaw, A. S. and Wulf, W. A. 1997. The legion vision of a worldwide virtual computer . Communications of the ACM 40(1): 39–45 .

Maheswaran, M. , Ali, S. , Siegel, H. J. , Hengsen, D. , and Freund, R. F. 1999. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems . Journal of Parallel and Distributed Computing 59(2): 107–131 .

10.

Nakada, H. , Matsuoka, S. , Seymour, K. , Dongarra, J. , Lee, C. , and Casanova, H. 2003. A gridRPC model and API for enduser applications, December. Available at https://forge.gridforum.org/projects/gridrpc-wg/document/GridRPC_EndUser_16dec03/en/1.

11.

Nakada, H. , Sato, M. , and Sekiguchi, S. 1999. Design and implementations of Ninf: towards a global computing infrastructure . Future Generation Computing Systems 15: 649–658 .

12.

Quinson, M. 2002. Dynamic performance forecasting for network-enabled servers in a metacomputing environment . Proceedings of the International Workshop on Performance Modeling, Evaluation and Optimization of Parallel and Distributed Systems (PMEO-PDS’02),Fort Lauderdale, FL, April 15–19.

13.

Weissman, J. B. 1996 The interference paradigm for network job scheduling . Proceedings of the 10th International International Parallel Processing Symposium, Heterogeneous-Computing Workshop, Honolulu, HI, April

14.

Wolski, R. , Spring, N. T. , and Hayes, J. 1999. The network service: a distributed resource performance forecasting service for metacomputing . Journal of Future Generation Computing Systems 15(5–6): 757–768. 15–19 .

Multicriteria Scheduling Heuristics for Gridrpc Systems

Abstract

Keywords

Get full access to this article

References