02229 Systems Optimization E20
Exercise: Assignment of real-time tasks to the multicores of an autonomous vehicle platform
Brief Abstract:
The prime objective of this assignment is to implement a metaheuristic solution over a decent neighbor function to optimize the task assigned to the cores of multicore processors. Starting with a small task assignment data, small.xml with 8 cores, and 9 tasks, we designed a basic neighbor function to implement and validate the simulation annealing method which improved the task scheduling to a great extent. However, the task assignment was pretty straightforward and there was no unschedulable job. To check the extent of our solution, we switched to medium.xml file which contains relatively larger task assignment data than small.xml. This gave us some insights to rectify and optimize the various aspects of our solution and subsequently achieved a valid and more promising solution. The same model is used to run over a large.xml file which contains 17 cores and approximately 250 tasks, and results were fairly auspicious. One important thing to note is that this large file with a significantly large number of tasks than cores initially showed some unschedulable tasks but later after the number of task shifts in between cores, there was a significant positive change in performance. This serves the purpose of this assignment and as an end solution, we have solution.xml which contains optimal placement of tasks corresponding to cores.
Set-up
This section contains initial setup of variables, dataframes and extraction of data from xml files. DFapp contains the tasks with deadlines, id, period and WCET parameters whereas DFplat comprises of machines and cores with Id's and WCRT factor.
Example of how the DFapp and DFplat dataframes will look like
Functions definitions
This section contains all the required functions which are used to calculate important parameters.
Mean laxity function:
Returns the mean laxity of the dataset to be used as cost function.
Laxity function:
Appends a column to the tasks dataset containing the new laxities calculated as:
$ L_i = D_i - WCRT_i $
Returns the updated tasks dataset.
Priority function:
Sets for each task an unique proprity represented as an integer. The lower the integer, the higher is the priority of the task (the task with priority 0 is the highest priority task).
Allocation Function
This function is used at the initialization to randomly allocate the tasks to cores.
Neighbor function
Generates a neighbor starting from the current dataset. The simplest option is to take a random task and move it from the current core to another random core.
Schedulability function:
Checks if the whole set is schedulable by checking that all the laxities are positive. Returns True or False.
WCRT calculation
The longest response time is calculated as:
$$R_i = C_i + I_i$$
Where interference $I_i$ is:
$$Ii = \sum{j=1}^{i-1}\frac{R_i}{T_j}C_j$$
To calculate WCRT, the following formula is used:
$$Ri = C_i + \sum^{i - 1}{j = 1}\frac{R_i}{T_j} C_j$$
where $R_i$ is the longest response time of a task $\tau_i$, $C$ is the worst-case computation time and $T$ is the period.
The algorithm used is from 4.4.2, Hard-Real time periodic scheduling chapter.
Simulated annealing algorithm
Initialization
- Generate a random schedule using the function.
- Set initial temperature T and reduction parameter r.
Looping: apply the simulated annealing algorithm.
- Generates a new neighbor and computes WCRT and schedulability.
- Updates WCRT and laxity.
- Check schedulability. If it's false, penalize the laxity with a factor 100000.
- If (new laxity) > (old laxity), accept the solution. Otherwise, accept with certain probability.
- Decrease the temperature: T = T(1-r)
Showing total number of tasks allocated on each core
Results
Get results in XML format
In order to get the Solution back in a XML format, the pandas dataframe will have to be converted into a string and then appended to the solution xml file