Speculative Scheduling of Parameter Sweep Applications Using Job Behaviour Descriptions - Cloud, Grid and High Performance Computing: Emerging Applications - page 78

The description generator must be installed on
each computer a job can run on. A later section
discusses the realities of the deployment in details.

• sub-elements: A data access pattern de-

scription contains at least one sub-element.
A sub-element specifies the file access
method of the job bound to a given seg-
ment of the file. The file access method
can be sequential or random marked by
the corresponding sub-element. Each sub-
element contains a data-block and a timing
sub-element:
◦ datablock : Characterises the file
segment that is processed sequen-
tially . It specifies the starting and
ending positions defining the current
segment in bytes and relative to the
file-size (∈[0,1]): min_pos_absolute,
max_pos_absolute, min_pos_rela-
tive, max_pos_relative. It also speci-
fies the distance between starting
positions of two successive data ac-
cess operations in bytes (step) and the
number of bytes read/written by a file
operation (size).
◦ area : Characterises the file segment
that is processed randomly . It speci-
fies the lower and upper bounds of
the segment processed in bytes and
relative to the file-size (∈[0,1]): low-
er_bound_absolute, upper_bound_
absolute, lower_bound_relative, up-
per_bound_relative. It also specifies
how many times a byte of the cur-
rent file segment has been accessed
(access_ratio), the average level of
intersection of blocks read/written
by subsequent file operations (inter-
secion_ratio ∈[0,1]), and the average
number of bytes read/written by a file
operation (avg_size).
◦ timing : Specifies the frequency of
the data access operations. In the case
of the random method it contains the
avg_op_time and avg_op_mips at-
tributes: the average system time (in
milliseconds) and CPU time (in mips)

JOB BEHAVIOUR DESCRIPTION

According to our job model the jobs are data
intensive applications which process huge files.
The behaviour description (XML) document
of a job contains relevant information for the
scheduler about the characteristics of the resource
consumption of the job. The relevant operations
influencing the length of job execution are the
file accesses and computing. Therefore the job
description characterises the file processing al-
gorithm implemented by the job.
After each execution of a job a “simple” de-
scription can be generated, which relates to a single
path in the control flow graph (CFG) of the job.
Therefore, in order to give a detailed description
of the job behaviour, the whole graph has to be
explored, which is equivalent to the exploration
of all possible paths in the CFG. The “complex”
job description reflects the complex structure of
the job: the already explored CFG.

Simple Description

The “simple” description format is presented
through an example in Algorithm 1.
The description comprises different file-bound
data access patterns of the job. Each data access
pattern is marked by the file XML element which
contains the following attributes and sub-elements:

• attributes:

type : Type of the file: in for input files, out
for output files.
name : File name.
access_ratio : The used portion of the file
(∈[0,1]).
intersection_ratio : The file usage redun-
dancy (∈[0,1]).