Since 1987 - Covering the Fastest Computers in the World and the People Who Run Them

June 27, 2013

Testing a New Algorithm for Cloud Computing

Ian Armas Foster

Computing in the cloud brings about certain challenges as a result of having to deal with probability of network delays. As such, optimized job scheduling and related job completion estimation times take on a new importance. Researchers from the University of York took on a couple of algorithms designed to schedule cloud tasks and compared and contrasted them.

“It is almost inevitable for grids and clouds to experience significant variations in demand, which can lead to transient periods of overload where some jobs have to wait,” the researchers noted in an introduction to the problem. “Industrial users indicated their desire for response times of jobs to be proportionate to the jobs’ execution times.”

As such, this research was meant to investigate scheduling protocols as they relate to HPC applications and tasks running in a grid or cloud environment. The researchers evaluated three scheduling algorithms: Projected Schedule Length Ratio (P-SLR), which they developed in a previous article, along with Shortest Remaining Time First (SRTF), and Longest Remaining Time First (LRTF), a baseline just to show ineffectiveness considering the desire of users for wait time to approximate runtime.

The team was interested in ‘worst-case scenarios,’ or jobs whose runtimes were severely misestimated. As was the case with all the tests they ran, the LRTF model did not perform particularly well in this regard, as not only did it subject certain tasks to starvation, but also gave little allowance to initially small jobs that possessed runtime variation.

“The LRTF orderer, as expected, shows poorer worst-case responsiveness than any of the policies that do not consider execution time,” the researchers noted. “This is because it makes the smallest tasks starve, and these tasks are the ones whose SLR is most sensitive to waiting time.”

What that essentially means is users place a somewhat higher value on smaller tasks with regard to computations done in an environment that could be subject to network delays, such as the virtualized environments found in clouds or grids. That makes sense, as the cloud is used for experimental applications that expect to run multiple exploratory simulations in a relatively short amount of time.

 “In a realistic system, it is assumed that an estimate of execution time, albeit inaccurate, will be available from the user or from an automated job profiler. In simulation, however, the exact execution times are known in advance, so inaccuracies need to be introduced into the model.”

In this case, the job schedulers rely on an estimated job completion time. Those estimates are inaccurate enough that they any algorithm would need to take into account at least a baseline amount of intolerance. The hypothesis was that one of the algorithms between P-SLR and STRF would carry the day until a certain variation threshold was reached.

As it turned out, that threshold took hold at ten times the original estimated execution time. “The responsiveness performance of P-SLR was found to be robust below a certain threshold of execution time inaccuracy,” the researchers found. “This threshold was 10 times the original execution time of the task. Above this threshold, SRTF was able to provide better responsiveness.”

After jobs show a 1000% increase from estimated to actual response time, the SRTF ‘starved out’ some jobs. While this sounds less than ideal, those jobs were least reliant on wait time and low priority, meaning it was fine for them to be set aside. Perhaps such a starvation would have indicated a flaw in the job itself. “The divergence after 1000% is due to this guarantee because SRTF is letting the largest tasks starve. The largest tasks have SLRs which are least sensitive to waiting time, keeping the worst-case SLR fairly low.”

With that said, the SRTF starved out not just high variance jobs. P-SLR, according to the research, adds a guarantee that no job will be left behind, giving it the edge before that threshold of 1000% variance. “The difference between P-SLR and SRTF in this range is not statistically significant, which shows the strength of the P-SLR policy as it adds the guarantee of non-starvation.”

As it turns out, the important distinction between P-SLR and SRTF is that the structure of P-SLR does not allow for what the researchers called job starvation whereas SRTF will essentially forget jobs occasionally.

 “Users desire fair treatment of their jobs. An example of a particularly unfair situation is if some jobs experience starvation (unbounded waiting time) under overload.” In this respect, even though SRTF starved out some jobs, its levity was more pronounced. “P-SLR was not able to give the best fairness compared to SRTF once any significant estimation inaccuracies were present, because SRTF is better at keeping SLRs low for small tasks whose SLRs are more sensitive to longer waiting times.”

The P-SLR algorithm created by the researchers at the University of York is such that jobs won’t be put on hold indefinitely when subject to variables like network delays such as are apparent in cloud environments. However, if a proper method to estimate response time within 1000% is not found or utilized, P-SLR’s usefulness decreases.

Share This