Read Me

The purpose of the project is to simulate four voltage scaling algorithms with RM and EDF scheduling.

The four algorithms that have been simulated are:

• NO SCALING
• STATIC
• PAST
• AGED_AVERAGES

The explanation of various terms and steps in an algorithm is given below:

1. The number of tasks to be scheduled - The user must pick the number of tasks to be scheduled from the drop down menu. There are 5 - 8 tasks provided.
2. Calculation time - This is the time for which the graph is displayed. The user can provide an input, or use the default value.
3. Execution time - This is the worst case execution time of the task i.e it is the longest possible time for which the task can run. The user can provide an input, or use the default value.
   In the case of the PAST and AGED_AVERAGES algorithms, this is provided in the form of a range - the first input represents the lower bound of the execution time, and the second represents the upper bound.
4. Period/Deadline - Every task repeats in intervals equal to its period. Each iteration of a task must finish before the next iteration arrives. If it does not, the task misses its deadline, and so is unschedulable.
   The user can provide an input, or use the default value.
5. Voltage - The voltage can be scaled statistically for every task, or can be given in the form of a range for different utlizations. If given for every task, the voltage is statistically scaled at the beginning of the algorithm. If given in the form of a range, the voltage is scaled depending on the utilization of the system. For high utilization, the largest voltage is taken, and for lower utilizations, the voltage is scaled in steps.
6. Frequency - The frequency can be scaled statistically for every task, or can be given in the form of a range for different utilizations. If given for every task, the frequency is statistically scaled at the beginning of the algorithm. If given in the form of a range, the frequency is scaled depending on the utilization of the system. For high utilization, the largest frequency is taken, and for lower utilization, the frequency is scaled in steps.
7. Rate Monotonic Graph - This graph indicates the schedule of the tasks on applying Rate Monotonic scheduling to the algorithm. The graph is a plot of Time VS Task Voltage. The graph is plotted for as long as the Calculation time (refer ii).
8. Earliest Deadline First Graph - This graph indicates the schedule of tasks on applying Earliest Deadline First Scheduling to the algorithm. The graph is a plot of Time VS Task Voltage. The graph is plotted for as long as the Calculation time.
   
   Note: The on the chart indicate the execution time for that task for that particular iteration.
10. Power - Power is calculated based on the formula:
    P = C * f * Vdd^2

Click on one of the links below to view the tool:

1. No Voltage Scaling
2. STATIC algorithm
3. PAST algorithm
4. AGED_AVERAGES algorithm

Click here to return to the Index.

Further references:

1. Rate Monotonic Scheduling
2. Earlist Deadline First scheduling
3. Static Voltage Scaling - A paper by Pillai and Shin (2001)
4. PAST Voltage Scaling
5. AGED_AVERAGES Voltage Scaling

Voltage Scaling Algorithms
Computer Architecture, Fall 2005