Information Technology Reference
In-Depth Information
Job scheduling for parallel computers has been
subject to research for a long time. As for Grid
computing, previous works discussed several
strategies for a Grid scheduler. One approach
is the modification of traditional list scheduling
strategies for usage on Grid (Carsten, Volker,
Uwe, Ramin, & Achim, 2002; Carsten Ernemann,
Hamscher, Streit, & Yahyapour, 2002a, 2002b;
Hamscher, Schwiegelshohn, Streit, & Yahyapour,
2000). Some economic based methods are also
being discussed (Buyya, Giddy, & Abramson,
2000; Carsten, Volker, & Ramin, 2002; Rajkumar
Buyya, 2002; Yanmin et al., 2005). In this paper we
explore non economic scheduling and allocation
policies with support for a speed-heterogeneous
Grid environment.
England and Weissman in (England & Weiss-
man, 2005) analyzed the costs and benefits of load
sharing of parallel jobs in the computational Grid.
Experiments were performed for both homoge-
neous and heterogeneous Grids. However, in their
works simulations of a heterogeneous Grid only
captured the differences in capacities and workload
characteristics. The computing speeds of nodes on
different sites are assumed to be identical. In this
paper we deal with load sharing issues regarding
heterogeneous Grids in which nodes on different
sites may have different computing speeds.
For load sharing there are several methods
possible for selecting which site to allocate a
job. Earlier simulation studies in the literature
(Hamscher et al., 2000; Huang & Chang, 2006)
showed the best results for a selection policy called
best-fit
. In this policy a particular site is chosen
on which a job will leave the least number of free
processors if it is allocated to that site. However,
these simulation studies are performed based on
a computational Grid model in which nodes on
different sites all run at the same speed. In this
paper we explore possible site selection policies
for a heterogeneous computational Grid. In such
a heterogeneous environment nodes on different
sites may run at different speeds.
In the literature (Barsanti & Sodan, 2007;
John, Uwe, Joel, & Philip, 1994; Sabin, Lang, &
Sadayappan, 2007; Srividya, Vijay, Rajkumar,
Praveen, & Sadayappan, 2002; Sudha, Savitha, &
Sadayappan, 2003; Walfredo & Francine, 2000,
2002) several strategies for scheduling moldable
jobs have been introduced. Most of the previous
works either assume the job execution time is a
known function of the number of processors al-
located to it or require users to provide estimated
job execution time. In (Huang, 2006) without the
requirement of known job execution time three
adaptive processor allocation policies for mold-
able jobs were evaluated and shown to be able to
improve the overall system performance in terms
of average job turnaround time. Most of the previ-
ous work deals with scheduling moldable jobs in a
single parallel computer or in a homogeneous Grid
environment. In this paper, we explore moldable
job allocation in a heterogeneous computational
Grid environment. In addition to moldable job
allocation, multi-site co-allocation (Sonmez,
Mohamed, & Epema, 2010) is another approach
usually used to deal with the resource fragmenta-
tion issue in computational Grid environments.
We will compare the performance of these two
approaches in this paper.
COMPUTATIONAL GRID MODEL
AND EXPERIMENTAL SETTING
In this section, the computational Grid model is
introduced on which the evaluations of the pro-
posed policies are based. In the model, there are
several independent computing sites with their
own local workload and management system. This
paper examines the impact on performance results
if the computing sites participate in a computa-
tional Grid with appropriate job scheduling and
processor allocation policies. The computational
Grid integrates the sites and shares their incoming
jobs. Each participating site is a homogeneous
parallel computer system. The nodes within each
Search WWH ::
Custom Search