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.

ResourceInfo

Going thru my next iteration of the code and focusing on the resource side of things. A resource is a cluster, a VO, a bunch of nodes, etc.
Currently, in Alea, you can create a virtual resource of say 500 cores. All arbitrary, and the system doesn’t care. For all intensive purposes, I am creating a super computer of 500 cored to run my simulation.  That’s not realistic and not feasible.
One can add resources in the resource file. Just like the job input file, you can create a file with 500 entries of one core nodes.  Or 125 4-core nodes.  You get the idea.  That is very limiting. I am all for files as configuration files, but for a simulation, you need to be able to automate much of this.  The next task for me is to automate resource generation just like job generation. 
The question is if resources require the rigorous type variance that jobs have?  I now can create a job profile that resembles a sine wave, do I need to do the same thing for resources?  Do resources need to vary like Grids, or be homogeneous like Clusters?  How about a cloud environment? 
Art Sedighi

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

Scheduling Simulator

My next task is to create a scheduling simulator – and a scheduler to further test my hypothesis.

I have been playing with Alea and GridSim.  I will upload the papers here to this post, but you can google for both of these research projects.

1.GridSim is an established project, and used in the community.  The creator is Rajkumar Buyya, who is very well known researcher and author in this field (http://www.buyya.com/gridsim).

2.Alea though not well known or an established project, presented a great idea in how to simulate a scheduler and large grid environments.  (http://www.fi.muni.cz/~xklusac/alea/)

Alea, however, was not complete and I ended up rewriting the scheduler module, a fair-share scheduler and a job loader.  I am not sure if I would like to open source the project – or my portions of the project as they present a great tool for simulating large grid environments and may be commercialized.

The greatest challenge was to create a job loader that can create a task profile similar to max{0, a*sin(bx)}.  This pattern of task submission is very common in HPC environments.  In a typical scenario, a client submits a certain number of tasks; waits for some responses to come back or creates another set of tasks, and repeats.  This start-stop fashion of task submission is where the greatest ability to game the system comes from.  For example, for one sets of submits a = 1000 (or 1000 tasks are submitted), but for a subsequent set, a = 5000.  This fluctuation, although not modeled in this version of the scheduling simulator, can present a great challenge to a scheduler aiming to fairly distribute resources.

 

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

Scheduling Architecture

As I am working my way thru the Alea framework to continue my research.  I realized the Alea does not actually implement a scheduling algo, at least not a fairshare one.

Schedulers are difficult to write, but I have had the fortune to develop a few over the years.  Wanted to document the internal architecture of a “good” scheduler.  Frankly, it does not matter what type of scheduling algorithm you implement.  As long at you follow the following approach, you will be ok.

Schedulers need to have 3 distinct stages:
– Pre-processing of tasks

– Scheduling of tasks

– Dispatching of tasks

most people lump the first two together.  That’s a mistake!

– Step 1: preprocessing:

This is where you apply the desired policy to the incoming tasks.  If you are interested in a FCFS policy, well, then you make sure that you queue up your tasks in a FCFS manner, but putting all the tasks in the order of arrival in a queue.  If you are interested in SJF (shortest job first), well, then you sort the incoming tasks in a manner that the shortest jobs are first in the queue.  Maybe you have more than one queue; it does not matter.  The point here is that in the preprocessing, you are not actually scheduling anything, but rather enforcing a policy or set of desired policies to the incoming tasks.

– Step 2: scheduling:

After your tasks are sorted based on some policy, you are ready to schedule these tasks.  Scheduling is supply vs. demand.
The most common scheduling policy is fairshare.  I have many posts about fairshare, but the gist of it is that you are given a set of resources based on your “fair share”, which is determined by “you deserve more because you need more” mentality.  If A has 10x as many tasks as B, it will get 10x more resources.
There are other policies, like highest priority first, etc.

– Step 3: dispatching:

After you have decided which tasks should get executed first, you now need to dispatch the tasks.  Most scheduling systems use gang-bang scheduling in that a number of tasks are scheduled.  The reason here is efficiency and practicality.  You dont make a scheduling decision on one task, but rather a set of tasks.  I am classifying gang-bang in the dispatching of the tasks, as it does not make a scheduling decision.  Many papers (ref needed) simply claim that gang-bang is a scheduling policy of its own.  The dispatcher essentially goes thru the set of tasks assigned to be executed, and sends those tasks to the nodes.  Once the set is dispatched, it goes to the next set.

There are optimization that can be done at every step, but that’s where the innovation comes in.  Also, the steps are not discrete as they depend on each other.  You *can* and should make them as decoupled as possible, but that’s just a general software development rule of thumb!

Art Sedighi

Update on my progress

Hi everyone…

It has been a while since I posted on this site.  I wanted to post an update, and hopefully a more regular checking in will follow.

I have recently been accepted to the TTU (http://www.ttu.edu)  PhD program in the Industrial Engineering department.  I am very excited about the opportunity, and looking forward to continuing my education at TTU IE department.

To that effect, I am taking two classes at TTU towards my PhD:

IE-5311-Principles-Optimization:Instructor:Ismael De Farias;
IE-5345-Reliability Theory. Instructor: Timothy Matis;

I have also been working on  my paper, and I am happy to say that it is finished and has been submitted for publication.  I will be posting the PDF and the full version of the paper once it has been officially accepted for publication.

I am working on my second paper.  And you will see posting in regards to that in the coming weeks/months.

 

Great to be back!

Art Sedighi

Policy as it pertains to high-performance systems

I was recently asked to think about how high performance systems deal with policies?

Two clarifications are required here:

  1. What are high-performance systems in the context of Grid, HPC and scheduling?
  2. What are the policies that a typical high-performance system deals with or in other words, sets?

In the context of high-performance schedulers, a high-performance system is the scenario where we are dealing with a large number of tasks (potentially millions of tasks) that are fairy short in duration, and the total job is only complete once all the tasks have been completed.

What is “short” in our context?  I can easily say that short is in the order of milliseconds or even seconds, but more quantitatively, I will assume that a task is short in duration iff:

  1. Scheduling overhead directly impacts the speedup factor (i.e. the time that it takes to schedule that task cannot be neglected)
  2. The runtime of a give task is significantly shorter (two-orders of magnitude) than the overall runtime of given job.

The bigger question becomes what these policies actually are and why would they be of importance?

The following is a subset of policies that we could be referring to:

  1. Sharing policy
  2. Fair-share policy pertaining to scheduling
  3. (others – TBD)

In a sharing policy, a client can allow some or all if its resources to be shared (given out) to other client[s] that may need them.  This obviously has a risk that the resources are not immediately available when the original owner needs them back.  At the same time, if one waits before lending out resources, there could a high degree of unutilized resources.

 

The fair-share policy is scheduling is probably the most implicitly set policy in shared environments.  The users get their “fair-share” of the available resources based on some preset fair-share policy.  A user may assist or hint the policy with priorities, for example, but generally speaking, the policy is set and agreed to by all the users.

My research focuses on Fair-share policy and how it affects users – and to an extend resources.  Users agree to the fair-share policy with the assumption that what the scheduler does is “fair”.

Furthermore, users interact with the system unbeknownst to how the fair-share scheduling policy is affecting their runtime.  The side effect of a fair-share scheduler is that timing is severely affects the outcome.  Since there is no historical perspective kept to aid the scheduler to better aid the enforcement of such policy, and some users end up keep temporarily starved.

 

Art Sedighi

Hot-Potato pricing and utility algorithm

This is a place holder for my paper

Game Theory Building Blocks

Just a recap today…

A game is composed of players or the interacting parties, rules or “who can do what”, and results or outcomes.  Game theory is build atop of other theories, with each representing the three components of a game:

– decision theory

– representation theory

– solution theory

 

Decision Theory – is an extension of the von Neumann-Morgenstern decision theory that relate to making a decision under uncertainty.  Decision theory relates to game theory in that it provides a way to represent preferences.  Games are all about preferences and as such utility of the chosen preference.

Representation Theory – allows a formal way of representing rules of a give game.  Two representation theories pertain to our discussion: normal form and extensive form.

Normal form: complete plan that considers all contingencies are presented at the start of the game.  It has a static view of the game in how it is played.

Extensive form: it is like a decision tree or a flow chart in that each level of the tree is build only when the node has been reached.  Players have choices and those choices are made in real-time

Solution Theory – it deals with how to assign solutions to games.  It works based on the premise that each player is looking out for itself.  One of the main solution concepts that we will talk about is Nash’s Equilibrium which basically states that no one player can change its strategy and improve its utility.

Game theory puts these three theories together to try and explain a social interaction.  A solution prescribes how rational players should behave and not how they would actually behave in the real-world. 

 

Hi everyone

As I am working toward a PhD is applied Mathematics at Stony Brook, I decided to create this web site to keep track of my progress. Drop me a note and check back often as I will try to update as often as I can.

thanks
Art Sedighi