Grid computing has emerged as a new paradigm for distributed systems, which promotes sharing of distributed resources. To maximize its benefits, it is essential to discover the resources available on the grid, and then effectively map the jobs to the resources for maximizing a given objective function. This paper focuses on the problem of matching of jobs to resources in a computing grid. Jobs are classified based on their service demands. Matching policies that use only the knowledge of job classes are introduced in this paper; simulation experiments demonstrate the effectiveness of these policies. Under a variety of different workload parameters the proposed matching policies demonstrate a performance comparable to, or better than, the well-known Minimum Completion Time matching policy, which is based on detailed a priori knowledge of jobs and resource characteristics.
Moore, J.2005. Grid Computing. Federal Computer Week , http://www.fcw.com/article89311-06-20-05-Print
2.
Foster, I., and C. Kesselman.1999. The Grid: Blueprint for a New Computing Infrastructure. San Francisco, CA: Morgan Kaufmann Publishers Inc.
3.
Braun, T.D. , H.J. Siegel, N. Beck, L. Boloni, M. Maheswaran, A.I. Rerther, J.P. Robertson, M.D. Theys, and B. Yao .1998. Taxonomy for Describing Matching and Scheduling Heuristics for Mixed-Machine Heterogeneous Computing Systems. In Proceedings of the Symposium on Reliable Distributed Systems (SRDS 1998), West Lafayette, IN, pp 330-335.
4.
Fernández, B.D.1989. Allocating Modules to Processors in a Distributed System. IEEE Transactions on Software Engineering, 15(11):1427-1436.
5.
Maheswaran, M. , S. Ali , H.J. Siegel, D. Hensgen, and R.F. Freund.1999. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems . In Proceedings of the 8th Heterogeneous Computing Workshop (HCW’99), Washington, DC, pp 30-44.
6.
Maheswaran, M., S. Ali , H. Siegel, D. Hensgen, and R.F. Freund.1999. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 59(2):107-131.
7.
Kapoor, N., S. Majumdar, and B. Nandy.2007. Matching of Independent Jobs on a Computing Grid. In Proceedings of International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2007), San Diego, CA, pp 537-546.
8.
Farooq, U., S. Majumdar, and E. Parsons.2006. A Framework to Achieve Guaranteed QoS for Applications and High System Performance in Multi-Institutional Grid Computing . In Proceedings of the 35th International Conference on Parallel Processing (ICPP 2006), Columbus , Ohio, pp 373-380.
9.
Foster I., C. Kesselman, C. Lee, R. Lindell, K. Nahrstedt, and A. Roy.1999. A Distributed Resource Management Architecture that Supports Advance Reservations and Co-Allocation. In Proceedings of the 7th International Workshop on Quality of Service, London, UK, pp 27-36.
10.
Buyya, R., D. Abramson, J. and Giddy.2000. Nimrod/G: An Architecture of a Resource Management and Scheduling System in a Global Computational Grid. In Proceedings of the 4th International Conference on High Performance Computing in the Asia Pacific Region, (HPC ASIA’2000), Volume 1, Beijing, China, pp 283-289.
11.
Albers, S. , and B. Schröder.2002. An experimental study of online scheduling algorithms. Journal of Experimental Algorithmics7 pp 1-14.
12.
Casanova, H. , G. Obertelli, F. Bermand, and R. Wolski.2000. The AppLeS Parameter Sweep Template: User-Level Middleware for the Grid. In Proceedings of the Super Computing Conference (SC’2000), Dallas, TX, pp 75-76.
13.
Edmonds, J.1999. Scheduling in the dark . In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp 179-188.
14.
Paranhos, D. , W. Cirne, and F. Brasileiro.2003. Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids. In Proceedings of the 9th International Euro-Par Conference on Parallel Processing (Euro-Par 2003), Klagenfurt, Austria, pp 169-180.
15.
Fujimoto, N. , and H. Kenichi.2004. A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks. In Proceedings of the Symposium on Applications and the Internet-Workshops (SAINT 2004 Workshops) , Tokyo, Japan, pp 674-680.
16.
Buyya, R., and M. Murshed.2002. GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Journal of Concurrency and Computation: Practice and Experience (CCPE), 14(13-15):1175-1220.
17.
Jain, R.1991. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling . New York: Wiley-Interscience .
18.
Iamnitchi, A. , I. Foster, and D.C. Nurmi.2002. A Peer-to-Peer Approach to Resource Location in Grid Environments. In Proceedings of the 11th Symposium on High Performance Distributed Computing , Edinburgh, UK, p 419.
19.
Howes, T.A.1995. The Lightweight Directory Access Protocol: X.500 Lite. Technical Report CITI TR-95-8, Center for Information Technology Integration , University of Michigan, Ann Arbor, MI.
20.
Smith, D.2005. A Whirlwind Introduction to the Internet. Department of Computer Science, University of North Carolina, http://www.cs.unc.edu/Courses/comp123-s05/
21.
Buyya, R., D. Abramson, and J. Giddy.2000. An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications . In Proceedings of the 2nd Workshop on Active Middleware Services (AMS 2000) held in conjunction with 9th IEEE International Symposium on High Performance Distributed Computing (HPDC 2000), Pittsburgh, PA, pp 221-228.
22.
McLaughlin, M.P.2005. Compendium of Common Probability Distributions. http://www.causascientia.org/math_stat/Dists/Compendium.pdf
23.
Wang, Q., C.H. Lung, and S. Majumdar.2005. Effective Fair Share Resource Management Algorithms in Support of Quality-of-Service. In Proceedings of International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’05), Philadelphia , pp 368-377.
24.
Silberschatz, A., P. Galvin, and G. Gagne.2004. Operating System Concepts . New York: John Wiley & Sons .
25.
Gomoluch, J., and M. Schroeder.2004. Performance evaluation of market-based resource allocation for Grid computing. Journal of Concurrency and Computation: Practice and Experience, 16(5):469-475.
26.
Ranjan, R., A. Harwood, and R. Buyya.2004. Grid Federation: An Economy Based, Scalable Distributed Resource Management System for Large-Scale Resource Coupling . Technical Report, Grid Computing and Distributed systems Laboratory , University of Melbourne, Australia.
27.
Christodoulopoulos, K.2007. Job Demand Models for Optical Grid Research. In Proceedings of the 11th Conference on Optical Network Design and Modeling (ONDM 2007), Athens , Greece, pp. 127-136.
