Information Technology Reference
In-Depth Information
“closest” member description. The absolute
weight of the newly inserted member de-
scription will be the absolute weight of the
description that was just replaced plus 1.
3. If at least one of the complex description
members is closer to the new job description
than the threshold and the diversity of the
composed description would not increase
with the insertion of the new individual de-
scription, than the
old composed description
is used
, and the absolute weight of the “clos-
est” member job description is increased by
1.
Let
C
(
c
,
d
i
) denote the estimated execution
time of the job running on cluster
c
behaving ac-
cording to description
d
i
. Note that
C
(
c
,
d
i
) can be
easily calculated using cluster profile
c
, and the
avg_op_*, datablock, area specifications of the
job description. The similarity measure of two
individual job descriptions
d
i
and
d
j
is defined by
the following sum.
∑
D d d
( ,
)
=
|
C c d
( ,
)
−
C c d
( ,
) |
i
j
i
j
c g
∈
The diversity of the job description is defined
as the cumulative similarity of its member de-
scriptions.
Many different similarity measures and thresh-
old values can be defined. The similarity measure
we have defined is based on the predicted execu-
tion time of jobs. The predicted job execution
time is defined by the description of the job and
the characterization of the Grid.
The Grid is characterised by its clusters, for-
mally
grid profile g
={
c
1
,
c
2
,…,
c
n
}, where
c
i
is a
cluster profile
. Cluster profile
c
i
=(
mips
,
disk
,
net
,
k
)
describes the “typical” resource characteristics of
a member cluster:
∑
D d
( )
=
D d d
( ,
)
i
j
d d
,
∈
d
i
j
We have defined the similarity threshold as
the half of the minimum distance of the member
descriptions (the initial threshold is 0).
min
( ,
) /
2
threshold
=
D d d
d d
,
∈ ≠
d i
,
j
i
j
i
j
•
mips
: speed of a typical CPU in the cluster,
•
disk
: I/O bandwidth (CPU ⟷ HDD
communication),
•
net
: network bandwidth,
•
Compared to the usage of individual job
descriptions the complex job description gives a
more precise characterization of the behavior of
the job. The complex job description offers there-
fore better job completion time estimates, which
eventually result in better scheduling decisions.
κ∈(0,1]: weight of the given cluster in the
Grid calculated as the number of hosts in
the cluster divided by the total number of
hosts in the Grid. Note that
∑
=1.
Complex Descriptions with Mutation
c g
c
∈
The composed job description
d
is described
as the collection of its
d
i
member job descriptions:
d
={
d
1
,
d
2
,…,
d
m
}. The (
d
,
i
) weight of a
d
i
member
job description is defined as the absolute weight
of
d
i
divided by the sum of all
absolute
weights
According to the
multiple descriptions
approach,
if the newly generated individual description is
closer to an already existing description than a
certain threshold, but adding the new description
would increase the diversity, then the new descrip-
tion would replace the other one. However, this
method unwillingly indicates that the new descrip-
tion is ”better” than the description it replaces.
n
∑
of description
d.
Note that
( , )
d i
=
1
.
i
=
1
Search WWH ::
Custom Search