In this first lab, we will use a high-level simulator to test load-aware scheduling algorithms.
To start, decompress it :
tar xzf load_balancing_sim.tgz
cd load_balancing_sim/
In this simulator, we have a list of tasks that are to be processed. Each task is represented by its load, or amount of computation required. There are also a number of identical processing elements (PEs), where tasks can be executed. The whole simulation consists in applying an algorithm (that is a scheduler) to decide where (on which PE) each task should be processed.
The program reports some metrics on the load imbalance of the achieved solution. To run a simulation, you will need to write a short code in Python. We describe below the required steps to run a simulation. You can also look at the example_*.py files in the provided folder for examples.
A simulation starts by defining a list of tasks, which you can do in one of the following ways, for different distributions:
myTasks = Tasks.range(minimum, maximum, step)
myTasks = Tasks.normal(mean, standard deviation, number of tasks, random seed)
myTasks = Tasks.lognormal(mean, sigma, number of tasks, scale, random seed)
Each number sampled from the lognormal(mean, sigma, number of tasks) distribution will be
multiplied by the scale parameter
myTasks = Tasks.uniform(minimum, maximum, number of tasks, random seed)
Or you can directly provide a list of loads to Tasks.from_loads() .
Then you'll need a list of PEs, created simply with:
myPEs = PEs(number of PEs)
Finally, to run the simulation and report the results:
simulation = Scheduler(myTasks, myPEs, "myalgorithm")
simulation.work()
simulation.stats()
simulation.plot_all()
In the code above, "myalgorithm" is to be replaced by the name of one of the algorithms available in sched/algorithms.py. Initially, only roundrobin is available.
Observe the implementation of the round-robin algorithm, in the algorithms.py file. Generate and execute some simulations with different numbers of tasks and PEs, and with different load distributions for the tasks. What is the impact of these parameters on the results from this scheduler? What would be the adversary case for this scheduler?
The provided round-robin algorithm is not load-aware, i.e. it does not consider the load of the tasks when distributing them across the PEs. Add a basic list scheduling option in the algorithms.py file. Your algorithm is to go over the list of tasks, assigning to each one of them the PE with the lowest current load (you'll have to keep track of the total load given to each PE, which is the sum of the loads of the tasks given to that PE).
Repeat your simulations using listscheduling instead of roundrobin. Are results better? Run experiments with the available algorithms for small and large numbers of tasks and resources and compare their performance.
For listscheduling, try to create an adversary (i.e., worst-case) scenario that leads to a schedule that is (2 - 1/m) from the optimal for m=2 and m=3 resources. For instance, if the optimal schedule on two resources has a makespan equal to 10, then the worst-case schedule by the list scheduling algorithm should result in a makespan equal to 10x(2-1/2)=15. Experiment with small numbers of tasks and small loads for a better result.
Write the Largest Processing Time (LPT) list scheduling algorithm (complete a function lpt in the algoruthms.py file). Compare how LPT performs for the adversary case of the basic list scheduler from step 4.
Run experiments the basic list scheduler and the LPT policy with small and large numbers of tasks and resources. Analyze how similarly or differently they behave in the different scenarios.
Write another version of the LPT algorithm with an additional restriction on the maximum number of tasks per resource (you can name it lpt_with_limits). Compare how this new LPT algorithm performs compared with its original code for increasingly restrictive scenarios. Show a situation where their makespans differ significantly for the same set of tasks and resources
Write a version compact version for listscheduling that you name list_scheduling_compact. A compact algorithm takes tasks in lexicographical order and maps them to a list of resources. Tasks are partitioned in contiguous groups of similar size. The first group is mapped to the first resource. The second group is mapped to the second resource. Etc.
Focus on the LPT algorithm. Try to create an adversary scenario that leads to a schedule that is (4/3 - 1/3m) from the optimal for m=3 resources.
Write the list scheduling algorithm for uniform resources (list_scheduler_for_uniform_resources). It will take an additional parameter being the speed of each processor. This list scheduling algorithm takes tasks in lexicographical order and maps them to the least loaded resources. The load of a uniform or related resource is equal to the load of its tasks divided by its speed. Describe your solution and show how it performs for one scenario of your choice.
Code a new version of the simulator so that it can take into input a DAG of tasks. In that case, tasks are available only where there precedent tasks in the graph are finished.
Implement a scheduling algorithm for this DAG based on critical path.