Sched-my-program

About

The aim of this project is to implement two schedulers, one that uses a simple shared queue and one that uses work stealing, and to compare their performance.

• Implemented
  • LIFO scheduler
  • Work stealing scheduler
  • Benchmarks

Execution

We provide two programs for testing our two schedulers.
To run them with the LIFO or WS scheduler, we propose to act as follows:

• quicksort

make quicksort_ws
./quicksort_ws      # run quicksort algorithm with work stealing

make quicksort_lifo
./quicksort_lifo    # run quicksort algorithm with lifo

make quicksort_lifo_cond
./quicksort_lifo_cond   # run quicksort algorithm with lifo using condition variables

make quicksort_naive
./quicksort_naive       # run quicksort algorithm without scheduler

• knapsack

make knapsack_ws
./knapsack_ws      # run knapsack algorithm with work stealing

make knapsack_lifo
./knapsack_lifo    # run knapsack algorithm with lifo

make knapsack_lifo_cond
./knapsack_lifo_cond  # run knapsack algorithm with lifo using condition variables

make knapsack_naive
./knapsack_naive      # run knapsack algorithm without scheduler

Benchmark

The program src/benchmark.c calculates the time taken by the different programs to run.
You can benchmark the different programs as follows:

make all
./benchmark all <n>         # run the 8 programs n times
./benchmark quicksort <n>   # run the 4 quicksort programs n times
./benchmark knapsack <n>    # run the 4 knapsack programs n times

To run only certain programs, use the option:
./benchmark <nb> <program1> ... <program_nb> <n>
where :\

• <nb>: number of programs to run\
• <program1> ... <program_nb>: programs to run\

Example :

./benchmark 2 quicksort_lifo knapsack_lifo 10

Options :\

• -t <n>: number of threads to use\
• -f <file>: write the results in the file given in argument\

Example :

./benchmark all 10 -t 8 -f benchmark.txt

This execution will run the 8 programs 10 times with 8 threads and write the results in the file benchmark.txt.

The benchmark can take a long time, depending on your machine and the number of threads required. If you run it with the -f flag, using Ctrl+c will stop the program after writing what has already been calculated in the file given as an argument (it will sometimes write it twice).

Mandelbrot

The program src/mandelbrot.c calculates the Mandelbrot set.
You can run it as follows:

make mandelbrot
./mandelbrot_lifo
./mandelbrot_lifo_cond
./mandelbrot_ws
./mandelbrot_naive

This program lets you visualize a Mandelbrot color graph, and walk around it by zooming in (left-click) and out (right-click). If you decide to use a scheduler, the number of threads will be set to the hardware maximum. The terminal displays the execution time of an action, and it will be interesting to compare this time between different programs.