Meaningful measurement

What is a meaningful measurement of performance of a scheduler?  I am embarking on the next paper which is due in two weeks, and unsure about what I am actually going to write.  Well, I know what I want to write, but not sure about its presentation mechanism.

This is the status of where I am right now…

Alea + GridSim have now successfully been morphed into a new framework called dSim.  Why dSim?  not really sure, but it had a good ring to it, and potentially a commercially viable name.  Anyhow, dSim is capable of creating a dynamic load, creating dynamic set of resources, schedule appropriately, and measure results.  All of this can be done via configuration files and parameters.

One of the results that I am collecting is the makespan for the tasks, and as a result the entire job.  I dont really care about the job itself, but the makespan of a given task.

I am collecting data that is like the following:

Client Name task ID Submission time Finished Time Makespan
Client 1 1034 3000 11000 8000

For a given run, I have 1000’s of these rows.  I have one row entry per task; which makes sense.  The question is then what to do with this data?

Statistical analysis of the data would give me the mean, median, and the STD.  But is that enough?  For example, i may have following:

Client 1:
mean: 33000
STD: 18500

Client 2:
mean: 44000
STD: 9000

Obviously, that’s good info, but is it enough?

The work can potentially be extended to a cloud environment, but for now, the focus is HPC environments.

Alea and GridSim

GridSim is a message passing toolkit.  Messages are passed around to different components that are either instructions of what to do, or data (or task).

Typical messages/commands are:

– Data: task or gridlet sent to the scheduler

– Control messages: schedule tasks, done with scheduling, tasks pending, task started, …

There are a number of control messages – many I added to the Alea framework, but on a couple of data messages.  The concept doesn’t change, however.  Message of a given type is sent to a destination, and there is logic on the receiving side that knows how to decode that message.

Alea framework is for the most part incomplete and very difficult to work with.  Data is hard-coded, the configuration is rigid and the code is not structured well (not proper OOD practices/patterns were followed).  I did made changes to the base code, but started to refactor and create “new” classes that are better designed and manageable.

There is now a submission strategy/policy via which you can change your submission policy.  The policy is API controlled, but I am hoping to make everything be file-based/controlled.  Alea would read job information from a file; that’s very limiting.  We change that to be all automated.  Based on the policy and the number of jobs/tasks, you can publish any which way you want, simulating as many clients as you want.

There is now a proper Fair-share scheduler.  It is not efficient b/c it uses too many locks, but it implements the scheduler pattern that I outlined in an earlier post

Control messages:  added a number of control messages to signal the state of the queues.  Are they empty? should we do another round of scheduling? etc, etc.

Lot more to go…  I am working on my second paper which is due the end of December 2014.  Once that paper is completed, I will move on to phase 2, which is better measurement of the grid resources/tasks.

Art Sedighi

Published paper in SCPE

Hi everyone,

As promissed, I am attaching my first published paper:

FAIRNESS OF TASK SCHEDULING IN HIGH PERFORMANCE COMPUTING ENVIRONMENTS

You can download it here: Fairness-sedighi

 

Abstract:

We claim that the current scheduling systems for high performance computing environments are unable to fairly distribute resources among the users, and as such, are unable to maximize the overall user satisfaction. We demonstrate that a user can game the system to cause a temporal starvation to the other users of the system, even though all users will eventually finish their job in the shared-computing environment. Undesired and unfair delays in the current fair-shared schedulers impede these schedulers from wide deployments to users with diverse usage profiles.

 

Source:

http://www.scpe.org/index.php/scpe/article/view/1020

 

Art Sedighi

Hot-Potato pricing and utility algorithm

This is a place holder for my paper

Protected: Draft – Paper

This content is password protected. To view it please enter your password below:

Not Fair

We can assume, as mentioned before, that the users of a Grid are playing a zero-sum game against each other.  In that one’s gain is another one’s loss.  Or more explicitly, if one user gets more CPU’s, the other[s] get less as a result.

This is fairly easy to prove as we have a set of CPU’s that does not change.  In a zero-sum game, there always exists a Nash’s Equilibrium.  Finding Nash’s Equilibrium is not easy; in-fact it falls under a calls of problems call PPAD, but we know that one does exist.

Two comments can therefore be made:

1. If we assume that Nash’s Equilibrium is in-fact the standard fairness point, then if the scheduler deviates from NE, it is not a fairshare scheduler.  Proving that fairshare is in-fact, not fair.

2. If a user by changing its strategy is able to increase its utility (i.e. get a higher portion of the available resources), then the system is not in Nash’s Equilibrium and the scheduler is not dividing up resources in a fair manner.

and 2.1. The user is inclined to change its strategy so it can get a larger portion of the system.  This is where we see “Price of Anarchy” developing.

Assumption:

One assumption we have made throughout is that Nash’s Equilibrium point presents the only fair point at which point all participants are treated fairly.

 

Art Sedighi