Inter-operating grids through delegated matchmaking

ABSTRACT

The grid vision of a single computing utility has yet to materíalize: while many grids with thousands of processors each exist, most work in isolation. An important obstacle for the effective and efficient inter-operation of grids is the problem of resource selection. In this paper we propose a solution to this problem that combines the hierarchical and decentralized approaches for interconnecting grids. In our solution, a hierarchy of grid sites is augmented with peer-to-peer connections between sites under the same administrative control. To operate this architecture, we employ the key concept of delegated matchmaking, which temporarily binds resources from remote sites to the local environment. With trace-based simulations we evaluate our solution under various infrastructural and load conditions, and we show that it outperforms other approaches to inter-operating grids. Specifically, we show that delegated matchmaking achieves up to 60% more goodput and completes 26% more jobs than its best alternative.

REFERENCES

• 1: The Grid Workloads Archive. {Online} http://gwa.ewi.tudelft.nl., Jul 2007.
• 2: The Parallel Workloads Archive. {Online} http://www.cs.huji.ac.il/labs/parallel/workload/., Jul 2007.
• 3: Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999 [doi>10.1145/333580.333583]
• 4: N. Andrade et al. OurGrid: An approach to easily assemble grids with equitable resource sharing. In JSSPP, volume 2862 of LNCS, pages 61--86, 2003.
• 5: Jim Basney , Miron Livny, Improving Goodput by Coscheduling CPU and Network Capacity, International Journal of High Performance Computing Applications, v.13 n.3, p.220-230, August 1999 [doi>10.1177/109434209901300305]
• 6: N. Capit , G. Da Costa , Y. Georgiou , G. Huard , C. Martin , G. Mounie , P. Neyron , O. Richard, A batch scheduler with high level components, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.776-783, May 09-12, 2005
• 7: Raphaël Bolze , Franck Cappello , Eddy Caron , Michel Daydé , Frédéric Desprez , Emmanuel Jeannot , Yvon Jégou , Stephane Lanteri , Julien Leduc , Noredine Melab , Guillaume Mornet , Raymond Namyst , Pascale Primet , Benjamin Quetier , Olivier Richard , El-Ghazali Talbi , Iréa Touche, Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed, International Journal of High Performance Computing Applications, v.20 n.4, p.481-494, November 2006 [doi>10.1177/1094342006070078]
• 8: Cluster Resources Inc. Moab workload manager administrator's guide. Tech. Doc. v.5.0, Jan 2007.
• 9: Karl Czajkowski , Ian T. Foster , Nicholas T. Karonis , Carl Kesselman , Stuart Martin , Warren Smith , Steven Tuecke, A Resource Management Architecture for Metacomputing Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.62-82, March 30, 1998
• 10: Dutch University Backbone. The distributed ASCI supercomputer 2 (DAS-2), 2006.
• 11: M. Ellert , M. Grønager , A. Konstantinov , B. Kónya , J. Lindemann , I. Livenson , J. L. Nielsen , M. Niinimäki , O. Smirnova , A. Wäänänen, Advanced resource connector middleware for lightweight computational Grids, Future Generation Computer Systems, v.23 n.2, p.219-240, February 2007 [doi>10.1016/j.cam.2006.05.008]
• 12: D. H. J. Epema , M. Livny , R. van Dantzig , X. Evers , J. Pruyne, A worldwide flock of Condors: load sharing among workstation clusters, Future Generation Computer Systems, v.12 n.1, p.53-65, May 1996 [doi>10.1016/0167-739X(95)00035-Q]
• 13: Dror G. Feitelson , Larry Rudolph, Metrics and Benchmarking for Parallel Job Scheduling, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-24, March 30, 1998
• 14: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: H. Franke , J. Jann , J. E. Moreira , P. Pattnaik , M. A. Jette, An evaluation of parallel job scheduling for ASCI Blue-Pacific, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.45-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331577]
• 16: A. Iosup, C. Dumitrescu, D. H. Epema, H. Li, and L. Wolters. How are real grids used? The analysis of four grid traces and its implications. In GRID, pages 262--270. IEEE CS, 2006.
• 17: A. Iosup, M. Jan, O. Sonmez, and D. Epema. The characteristics and performance of groups of jobs in grids. In Euro-Par, LNCS, 2007.
• 18: James Patton Jones , Bill Nitzberg, Scheduling for Parallel Supercomputing: A Historical Perspective of Achievable Utilization, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-16, April 16, 1999
• 19: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 20: Uri Lublin , Dror G. Feitelson, The workload on parallel supercomputers: modeling the characteristics of rigid jobs, Journal of Parallel and Distributed Computing, v.63 n.11, p.1105-1122, November 2003 [doi>10.1016/S0743-7315(03)00108-4]
• 21: H. H. Mohamed , D. H. J. Epema, Experiences with the KOALA co-allocating scheduler in multiclusters, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.784-791, May 09-12, 2005
• 22: A. Reinefeld et al. Managing clusters of geographically distributed high-performance computers. CP&E, 11(15):887--911, 1999.
• 23: P. Saiz, P. Buncic, and A. J. Peters. AliEn resource brokers. In Computing in High Energy and Nuclear Physics, 2003. Also available as CoRR, cs.DC/0306068.
• 24: Uwe Schwiegelshohn , Ramin Yahyapour, Resource Allocation and Scheduling in Metasystems, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.851-860, April 12-14, 1999
• 25: Mumtaz Siddiqui , Alex Villazón , Thomas Fahringer, Grid capacity planning with negotiation-based advance reservation for optimized QoS, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188563]
• 26: Douglas Thain , Todd Tannenbaum , Miron Livny, Distributed computing in practice: the Condor experience: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.323-356, February 2005 [doi>10.1002/cpe.v17:2/4]
• 27: Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]