Effective Resource Allocation and Job Scheduling Mechanisms for Load Sharing in a Computational Grid

Effective Resource Allocation and Job Scheduling Mechanisms for Load Sharing in a Computational Grid

Kuo-Chan Huang (National Taichung University, Taiwan), Po-Chi Shih (National Taichung University, Taiwan) and Yeh-Ching Chung (National Taichung University, Taiwan)
DOI: 10.4018/978-1-60566-184-1.ch004
OnDemand PDF Download:


Most current grid environments are established through collaboration among a group of participating sites which volunteer to provide free computing resources. Therefore, feasible load sharing policies that benefit all sites are an important incentive for attracting computing sites to join and stay in a grid environment. Moreover, a grid environment is usually heterogeneous in nature at least for different computing speeds at different participating sites. This chapter explores the feasibility and effectiveness of load sharing activities in a heterogeneous computational grid. Several issues are discussed including site selection policies as well as feasible load sharing mechanisms. Promising policies are evaluated in a series of simulations based on workloads derived from real traces. The results show that grid computing is capable of significantly improving the overall system performance in terms of average turnaround time for user jobs.
Chapter Preview


Without grid computing users can only run jobs on their local site. The owners or administrators of different sites are interested in the potential benefit of participating in a computational grid and whether such participation will result in better service for their local users by improving the job turnaround time. Therefore, it is important to ensure that grid computing can bring performance improvement and that the improvement is achieved in the sense that all participating sites benefit from the collaboration. In the other words, no participating sites’ average turnaround time of their local jobs would increase after joining the computational grid.

Heterogeneity is another important issue in a computational grid. Many previous work (Bucur and Epema, 2003; Ernemann et al., 2002; Zhang et al., 2006) have shown significant performance improvement for multi-site homogeneous grid environments. However, in the real world a grid usually consists of heterogeneous sites that differ in configuration and computing speed. Heterogeneity puts a challenge on designing effective load sharing methods. Methods developed for homogeneous grids have to be improved or even redesigned to make them effective in a heterogeneous environment. This article addresses the potential benefit of sharing jobs among different sites in a speed-heterogeneous computational grid environment. Related issues are discussed, including job scheduling for feasible load sharing and site selection for processor allocation.

Job scheduling for parallel computers has been a subject of research for a long time. As for grid computing, previous work discussed several strategies for a grid scheduler. One approach is the modification of traditional list scheduling strategies for usage on a grid (Hamscher et al., 2000; Ernemann et al,. 2002). Some economic based methods are also being discussed (Buyya et al., 2002; 2003; Zhu et al., 2005; Ernemann et al., 2002). In this article we explore non-economic scheduling and allocation policies for a speed-heterogeneous grid environment.

Key Terms in this Chapter

Processor Allocation: It is concerned with the assignment of the required number of processors for a specific job.

Grid Computing: An IT infrastructure that can dynamically integrate various resources together for use based on specific need. Those resources may be located on different places and managed by different organizations or authorities, connected through public or private networks.

Load Sharing: Jobs submitted at a local site and waiting in a queue can be migrated to remote sites for immediate execution or reduced waiting time.

Site Selection: It chooses an appropriate site among a set of candidate sites in a computational grid for allocating a job according to some specified criteria.

Computing Grid: A kind of grid computing platform that focuses on integrating computing resources at different places for solving computing-intensive problems or applications.

Job Scheduling: It determines the sequence of starting execution for the submitted jobs waiting in the queue.

Feasible Sharing: A computational grid is feasible if it can bring performance improvement and the improvement is achieved in the sense that all participating sites benefit from the collaboration. That means no participating sites’ average turnaround time for their jobs get worse after joining the computational grid.

Complete Chapter List

Search this Book: