Information Technology Reference
In-Depth Information
1
Push
idl e
workers
in
worker
queue Q ;
2
Group
all
unfinished
jobs
into S i ;
// S i is a set of unfinished jobs of which ENR are i
3 i =0 ; // Select jobs from S 0 at first
4 CS = φ // CS is a set of candidate jobs for job allocation
5
6
while
( Q is
not
empty
)
do
7
while
( S i != φ )
do
8
worker w from Q ;
Pop
9
Allocate
a
spotter
job
to
worker w with
rate q ;
10
if ( No job
is
allocated
to w )
then
11
Create
a
set
of
candidate
jobs CS = S i + S i+1 + ...+ S i+R
12
Select
job j x which
ha s
a
minimum EC J in CS ;
// j x ∈ S x
13
Allocate
job j x to w ;
14
Update EC J (j x ) ;
15
S x = S x −{j x } ;
16
S x+1 = S x+1 + {j x } ;
17
end
i f
18
if
(Qis empty ) then
19
exit ;
20
end
i f
21
end
while
22
i = i +1 ;
23
end
while
Figure. 22: Expected-credibility-based job scheduling algorithm
(line 12). Note that j x is a job in S x , that is, ENR(j x )=x . Once job j x is allocated to w ,
then EC J (j x ) , S x , and S x+1 are updated immediately to reflect the allocation of job j x in
the subsequent scheduling (lines 14 - 16).
Using this scheduling method, jobs having smaller ENR are selected for candidate jobs
CS prior to jobs having larger ENR . Also, among CS , a job having the minimum EC J is
selected prior to others. That is, jobs are selected in the ascending order of ENR and EC J .
This scheduling policy arises from the careful observation that there exist many un-
necessary job allocations to satisfy a job's termination condition: i.e. C J (j) ≥ 1 − acc .
This occurs because C J changes dynamically during a computation. In fact, C J (j) changes
when the master (1) collects new results for job j , or (2) collects results for a spotter job
from the workers which have returned results for job j . Regarding the second case, when a
worker w survives spot-checking, C W (w) and C R (r) increase as in eqs. (8) - (10), which
in turn increases the job's credibility C J (j) . Because spot-checking is executed with a con-
stant rate q , C J (j) tends to continue to increase during the computation, which implies that
job j might satisfy the termination condition with no new results. Meanwhile, using a job
scheduling mechanism, the master continues to allocate the unfinished job j and collects
new results so that C J (j) satisfies the termination condition. If C J (j) exceeds the threshold
without the newly collected results, then the new results will turn out to be unnecessary for
job j . In such a case, such additional job allocations can be said to be “unnecessary job
allocations”.
The key factor to reduce the computation time T is how to save such unnecessary job
allocations. It is, however, difficult to find during a computation which results will be un-
necessary at the end of the computation because the credibility of jobs changes dynamically
depending on the unpredictable results of jobs returned for normal and spotter jobs. Note
that jobs which have lower credibility and fewer results require more results to increase
the credibility; that is, to save unnecessary job allocations, a job which has lower EC J
Search WWH ::




Custom Search