RM4ES Practicals

This repository contains the material for the practical session of course RM4ES given in the Spring semester of 2024.

• RM4ES Practicals
  • Session 1: getting started
    • Install
    • Introduction to Batsim
    • Exercise 1: workload
    • Exercise 2: run your first simulation
    • Exercise 3: understand and visualize Batsim outputs
    • Exercise 4: FCFS monomachine
  • Session 2: monomachine schedulers
    • Exercise 1: EDF monomachine
    • Exercise 2: compare FCFS and EDF
      • 2.1 Gantt chart
      • 2.2 Scheduling metrics
  • Session 3: multimachine schedulers
    • Exercise 1: create a multimachine platform
    • Exercise 2: FCFS and EDF multimachine
    • Exercise 3: back to the course exercise
    • Exercise 4: bigger workload input
  • Mini-projects
    • Presentation
    • Topics

Session 1: getting started

Objective for this session:

• setting up all the simulation environment
• understanding the workload representation in Batsim
• having a first scheduling algorithm running

Install

Ensure that you are in your home directory (run cd).

Clone this repository:

git clone https://gitlab.irit.fr/sepia-pub/mael/RM4ES-practicals.git

Install Nix, that will manage for you all the dependencies you need for the course:

# download and install nix-user-chroot, a hack to install nix without root privilege
curl -L  https://github.com/nix-community/nix-user-chroot/releases/download/1.2.2/nix-user-chroot-bin-1.2.2-x86_64-unknown-linux-musl --output nix-user-chroot
# give exec rights
chmod u+x nix-user-chroot
# download and install nix
mkdir -p ~/.nix && ./nix-user-chroot ~/.nix bash -c "curl -L https://nixos.org/nix/install | bash"
# enable cachix
mkdir -p ~/.config/nix && cp ~/RM4ES-practicals/util/nix.conf ~/.config/nix
# add a line to your bashrc
echo 'source ~/.nix-profile/etc/profile.d/nix.sh' >> ~/.bashrc

IMPORTANT: Now, each time you want to test your schedulers, you need to run, from the repository RM4ES-practicals:

# enter the nix-user-chroot shell
~/nix-user-chroot ~/.nix bash
# enter the nix shell defined in file default.nix, with all dependencies managed.
# can take a few minute the first time you run it, to download everything. 
nix-shell -A expe

Introduction to Batsim

The resource and job management simulator Batsim, that we are going to use during these practicals, needs three inputs:

• a platform: description of the IT infrastructure;
• a workload: list of jobs that are going to arrive and their characteristics;
• a scheduling algorithm: the "brain" of the system, taking decision on when and where to execute the jobs.

The platform is represented by an XML file. You have a simple example (monomachine platform) in the file expe/1machine.xml. This is enough for now! We will come back to it in more detail in session 3.

The workload is represented by a JSON file (see expe/2jobs.json):

{
    "jobs": [
        {"id": "1", "profile": "3UT", "res": 1, "walltime":10, "subtime": 0},
        {"id": "2", "profile": "4UT", "res": 1, "walltime":6, "subtime": 0},
    ],
    "profiles": {
        "3UT": {"delay": 3,"type": "delay"},
        "4UT": {"delay": 4,"type": "delay"}
    }
}

The meaning of each field in the JSON is explained in Batsim workload documentation.

The scheduling algorithm has to be developed separately, and communicates with Batsim through the messages defined in Batsim protocol. In this tutorial, we will develop our schedulers in Python thanks to pybatsim (version 3.2.0). The scheduler implementations will be located in the folder sched/.

Exercise 1: workload

Represent the workload used previously in this course (exercise 1 from the exercise document) in Batsim JSON format. You will put it in a new file named expe/ex1.json. We will use the field "walltime" to store the "deadline".

Exercise 2: run your first simulation

We will see if the installation from step Install worked, by running a first simulation.

For this, you will need two processes, launched in two separate terminal: one for the infrastructure simulator (batsim), managing the workload and the platform, and one for the scheduler.

On one Nix shell, launch batsim with platform input expe/1machine.xml, workload input expe/2jobs.json and export prefix out/:

batsim -p expe/1machine.xml -w expe/2jobs.json -e out/

The simulation should start, and wait for the scheduler to be started as well. Try to understand the output from batsim in the terminal.

On another Nix shell, run a scheduler. You are given a very simple scheduler, sched/rejector.py, that rejects all the jobs:

pybatsim sched/rejector.py

Try to understand the output of the scheduler in the terminal as well.

That's it, you have run your first simulation!

Exercise 3: understand and visualize Batsim outputs

Simulation outputs are stored in the out directory. You have schedule-centric outputs (schedule.csv) and job-centric outputs. Open them, read the doc, and make sure you understand most of the fields.

Have a look also at the file out/example_jobs.csv to see how the job output looks like when the jobs are not rejected.

Finally, to get a visual representation of the outputs, we will use the visualization software evalys. We provide a wrapper of evalys with the main functions that you need in the file util/plot.py. The jobs.csv output that was produced before is not suitable for visualization since it has no jobs that executed. Visualize the jobs on the example instead:

python util/plot.py out/example_jobs.csv

NB: the script has an option to store the output in a PDF file. Check available options with python util/plot.py -h.

Exercise 4: FCFS monomachine

Now, it's time to develop your own scheduler. We will start with a FCFS monomachine: it schedules the jobs by order of arrival.

Create a file fcfsMono.py in the sched directory. Draw inspiration from the template in sched/template.py to create your scheduler.

Warning: the file name and class name must match (for example, fcfsMono.py for the file name and FcfsMono for the class name).

You can use the following functions:

• job.id, job.submit_time, job.profile.name, job.requested_resources, etc. to retrieve information about the job
• self.bs.reject_jobs(list_of_jobs): to reject all the jobs in the list list_of_jobs (message REJECT_JOB in Batsim protocol)
• self.bs.execute_jobs(list_of_jobs): to execute all the jobs in the list list_of_jobs (message EXECUTE_JOB in Batsim protocol). Warning: this function expects the jobs to have been allocated to one or several machines first. Use job.allocation = 0 in the monocore context.

Test your algorithm on 2jobs.json and ex1.json inputs, and other inputs that you will create. Visualize the outputs with the visualization script to see if it worked correctly.

Session 2: monomachine schedulers

Objective for this session:

• implement another monomachine scheduler: EDF
• compare FCFS and EDF in terms of waiting time and lateness

Exercise 1: EDF monomachine

Implement an EDF scheduler monomachine. The file name will be called edfMono.py and the class EdfMono.

Hints: remember that we use Batsim walltime field to store the deadline. In pybatsim, this information is stored in job.requested_time.

Test your scheduler by running it on different workload inputs. Do not hesitate to create your own inputs to see how it behaves in different situations!

Upload your file edfMono.py on Moodle.

Exercise 2: compare FCFS and EDF

2.1 Gantt chart

Produce the Gatt-chart visualization of the simulation with the workload of session1-exercise1, for both FCFS and EDF schedulers. Save the image as a PDF file (we remind that we can use the option -o of the visualization script, for example: python util/plot.py out/edf_jobs.csv --noDisplay -o out/edf_ex1.pdf).

Upload the 2 PDFs on Moodle.

2.2 Scheduling metrics

Batsim output schedule.csv (see documentation) provides us with some scheduling metrics. For example, we can read the mean and max waiting time, which is the time that elapsed between the submission of the job and the beginning of its execution.

Unfortunately, Batsim do not compute the lateness for us. We will have to calculate this information form the jobs.csv.

Create a script that computes the mean and max lateness from a jobs.csv given as input. You can use any programming language that you like, for example python with the library pandas. Ask for help from your lab's teacher if you don't know where to start.

Fill in the file expe/metrics.txt for your two schedulers, and upload it on Moodle. Do you find the same results as when you did it in class? Which algorithm is better in terms of waiting time on this input? In terms of lateness?

Session 3: multimachine schedulers

Objective for this session:

• implement multimachine schedulers
• run the schedulers with different input

Exercise 1: create a multimachine platform

Until now we've only been running our experiments on a monomachine platform. Batsim (and more precisely the underlying simulator SimGrid) enables to simulate quite elaborate computing platforms, including compute and storage nodes interconnected with complex network topologies. Our example expe/1machine.xml is the simplest platform file one can write. It defines one zone, in which there is one computing node, computing at a speed of 10 Gflops (floating-point operations per second):

<host id="node_0" speed="10Gf"/>

You can also see a second node, master_host, which is a dummy host needed for Batsim to function correctly (see Batsim platform documentation).

Copy this platform file and add a new host with the same speed as node_0. You will call this new platform file 2machines.xml.

Similarly, create the file 3machines.xml.

Exercise 2: FCFS and EDF multimachine

Extend the schedulers fcfsMono and edfMono previously written to the multimachine case. You will call the new schedulers simply fcfs and edf.

Hints:

• remember: the platform file is read by Batsim, which forwards information to the scheduler in its message SIMULATION_BEGINS. From the scheduler, you can access the number of machines in the variable self.bs.nb_compute_resources.
• you will have to indicate on which precise machines your jobs have to execute every time you send an EXECUTE_JOB to Batsim. You can do that by setting correctly the job.allocation field before sending the job. This field must be of the type ProcSet, a useful class representing sets of closed intervals. Read carefully the (short) ProcSet documentation to learn more about ProcSets and how to use them.

Test your schedulers with the platform 2machines.xml and workload ex1.json.

Exercise 3: back to the course exercise

Run FCFS and EDF schedulers with the 2-machine and 3-machine platforms. Produce and save the gantt charts. Do you obtain the same as in the exercise?

Complete the file expe/metrics.txt from the previous session to also save the max waiting time, mean waiting time, max lateness and mean lateness for each algorithm and each platform. You can use different Batsim export prefixes (option -e) to keep several simulation outputs.

Upload the new file metrics.txt on Moodle.

Exercise 4: bigger workload input

Create the workload input 20jobs.csv fulfilling all the criteria below:

1. it contains 20 jobs
2. at least 1 job requests 2 resources
3. it leads to a max lateness > 0 with FCFS and EDF scheduling policies on a single machine
4. on 2 machines, it leads to a positive max lateness with FCFS, and negative max lateness with EDF

Upload your file 20jobs.csv along with the 4 gantt charts and (FCFS and EDF, mono and 2-machine) and a text file stating the values for max lateness obtained in all cases.

Mini-projects

Objective for this session:

• strengthens your understanding of scheduling and simulation
• solving an open question
• carry an experimental approach by proposing suitable inputs for validation

Presentation

Your presentation should:

• explain your scheduling algorithm,
• show how it is implemented (the main points)
• make a demonstration of your scheduler, including everything you deem relevant: gantt charts, scheduling metrics, energy metrics, comparison with FCFS/EDF...
• use complex examples (many machines, many jobs, ...)

The presentation should last around 10 minutes per group

Topics

Heterogeneous machines with deadlines. Until now, all the machines in our platform were identical (same computing speed). Create a platform with heterogeneous machines (for example one very fast machine, many slow) and a scheduling algorithm that take into account this heterogeneity.
You will have to use parallel_homogeneous_total job profiles in your workload instead of the simple delay profile that ignores the speed of machines.

Energy & machine on/off. Implement a heuristic to switch off idle machines in order to save energy.
You will need to adapt

• the platform file to give an energy consumption value to your machines in computing, sleep, switching on and switching off state (see Millian Poquet PhD thesis parts 2.3 and 4.5 where the energy model is explained, you can draw inspiration from this platform file).
• the workload file to use parallel_homogeneous_total job profiles instead of delay that do not take into account energy
• the batsim call to get energy-specific output files (add the option --energy)

Energy & powercap. Implement a scheduler with instantaneous power constraint.
You will have as input a power envelope defining the maximum power available at time t. The consumed power curve (epower in the energy consumption trace) should be at all points under your power envelope. You will need to adapt to the energy model (see the 3 bullet points in the topic above).

Multimachine jobs. When a job requests many resources, it sometimes "blocks the queue" because there are currently not enough machines available to execute it. To solve this problem, we can use a technique called "backfilling". It consists in looking for jobs that are situated after the blocking job in the queue and execute them now, under certain conditions.
Implement your version of backfilling and demonstrate that it improves the scheduling (on simple cases and on big cases by looking at scheduling metrics).

Preemption. Implement EDF with preemption.
To simulate preemption, you can kill and resubmit a job. For example, imagine job1 needs to execute for 5UT. It runs for 2UT and then job2 arrives with a shorter deadline. To simulate preemption you need to kill job1 and dynamically resubmit a job with the same deadline, and 5-2=3UT to execute.
Look at messages KILL_JOB, REGISTER_JOB and REGISTER_PROFILE in batsim protocol (respectively self.bs.kill_jobs(jobs), self.bs.register_profiles(workload_name, profiles) and self.bs.register_job(id,res,walltime,profile_name) in pybatsim). You will also need to clean the duplicated jobs in the batsim output.