Home

A Solution to Improve the Efficiency of Reliability-Based Scheduling Schemes in Volunteer Computing Systems - 9


( (

Maybe you are interested!



gWorker = i;

EndIf Else

//Prioritize by calculation ability If




Endif EndFor


EndIf EndIf

Endif

gWorker = i;

If (bWorker exists)

return bWorker;

EndIf

If (gWorker exists)

return gWorker;

EndIf

Return NULL;

Next, I will validate the availability of reliability-based scheduling schemes using simulation results in section 5.


Chapter 4. EXPERIMENTAL RESULTS


This section introduces the simulation program, simulation scenarios, and discusses the simulation results.

4.1 Simulation program

In this section, I will present the simulation program used in my thesis, the VCSIM simulation program. VCSIM is built on the event-driven model. This is the model used in BOINC. VCSIM simulates the creation and distribution of tasks executed in a highly variable, heterogeneous and distributed environment. In addition, it collects and evaluates the efficiency of completed tasks. VCSIM is written in the C programming language.

VCSIM is designed with main modules: Workstation management module, job management module, simulation module. The workstation management module performs the task of creating a list of workstations with the same initial reliability, with different calculation times, creating fake machines, managing workstations such as taking workstations from the queue according to scheduling criteria, pushing workstations into the queue... The job management module performs the task of creating a list of tasks, assigning tasks to workstations, managing the job queue, calculating the reliability of tasks... The simulation module performs the task of managing a list of simulation parameters such as the number of simulations, the number of workstations performed, the number of jobs performed, the error fraction, the acceptable error rate, the number of re-execution times of tasks, the sabotage rate, the execution scheduling scheme, the point check rate, whether the parameter supports blacklisting or not, whether the parameter supports point checking by voting or not... Perform simulations, support display functions and output results.

4.2 Simulation scenario

In this section, I determine the efficiency of the proposed scheduling scheme by simulations. In my simulation, a computation consists of a list of N



independent tasks of equal size and a list P of volunteer computers (workstations). To simulate the sabotage of rogue machines, a fraction f =

0.2 of the randomly selected workstations are destructive. There are two cases regarding the number of tasks and workstations of interest.

In the first case ( N > P ), there are 1500 tasks and 500 workstations, in the second case ( N < P ), there are 500 and 1500 workstations. Assuming that the blacklist policy is not applied (i.e. a workstation can submit results even after it is detected as a saboteur), a voting-based checkpointing technique is used in the simulation. Because the performance of a reliability-based scheduling scheme is evaluated in terms of the delay parameter (i.e. the ratio of the running time of the computation with or without fault tolerance), I can assume that the execution time of a task on a workstation is a random number between 1 and 5 time units. The main purpose of this simulation is to compare the performance of the following scheduling schemes: Round Robin RR, Round Robin scheduling based on the priority of the implementation of PRR(Av), Round Robin scheduling based on the priority of reliability PRR(Cr), Round Robin scheduling based on the reliability test with the priority of reliability CRR(Cr) and the priority of the implementation of CRR(Av). To ensure the reliability of the simulation results, I will simulate each case 5 times and take the average value.

4.3 Results

Figures 4-1, 4-2, 4-3, 4-4, show the experimental results for different error rate cases when the number of jobs is larger than the number of machines and Figures 4-5, 4-6, 4-7, 4-8 show the experimental results for different error rate cases when the number of jobs is smaller than the number of workstations, obtained from simulation for concurrent scheduling schemes, I plot the value of the slowdown parameter against other parameters because it is an important performance parameter when adopting a reliability-based fault-tolerant scheme in volunteer computing systems.

Looking at the results of the comparison chart I see that the scheduling schemes I proposed significantly reduce the execution time compared to the Round Robin scheduling scheme.



respectively. In particular, in both cases N > P or N < P , the CRR scheduling scheme is reduced by 40% - 60% compared to the corresponding RR scheduling scheme. In both cases N > P or N < P ,

The CRR scheduling scheme reduces approximately 60% - 80% compared to the corresponding RR scheduling scheme. In the case of N > P, N < P , the CRR scheduling scheme is more efficient than PRR(Cr) and PRR(Av) except for the case of N < P and the error rate of the result

less than 0.001. The PRR(Cr) scheduling scheme is slightly more efficient than PRR(Av) when the error rate is less than 0.001. The rest are almost equivalent.

The reason why the schemes have such good results is because the schemes have paid attention to choosing workstations to improve the reliability of the task after each workstation calculation so that the reliability of the task quickly moves towards the reliability threshold.


Figure 4-1. Comparison chart of delays of scheduling schemes with s= 0.25,N >P


Figure 4-2. Comparison chart of delays of scheduling schemes with s= 0.5,N >P


Figure 4-3 Comparison chart of delays of scheduling schemes with s= 0.75,N >P


Figure 4-4. Comparison chart of delays of scheduling schemes with s= 1,N >P


Figure 4-5. Comparison chart of delays of scheduling schemes with s= 0.25,N< P


Figure 4-6. Comparison chart of delays of scheduling schemes with s= 0.5,N< P


Figure 4-7. Comparison chart of delays of scheduling schemes with s= 0.75,N< P


Figure 4-8. Comparison chart of delays of scheduling schemes with s= 1,N< P

Comment


Agree Privacy Policy *