Feedback DVS-EDF Scheduling for Crusoe Processor

Abstract

This project is to implement the feedback DVS-EDF algorithm for Transmeta's Crusoe processor under Linux and evaluate its power-saving performance. An outline of the solution is proposed.
 

Background

This project is based on Feedback DVS-EDF algorithm [1][2], an EDF-based dynamic voltage scaling scheduling algorithm for power-aware computing. In our previous work, Feedback DVS-EDF has been implemented in a simulation environment. Significant power-saving effect has been observed in the simulation experiments. In order to further examine the performance and properties of Feedback DVS-EDF on real-life environment, an implementation of this algorithm on real power-aware processors is a necessity. We choose Transmeta's Crusoe processor for this project as our test-bed. Compared to some other power-aware processors, Crusoe allows us to adjust both processor frequency and voltage in multiple levels based on processor activity, with relatively fast frequency transition time, which makes it an ideal hardware platform for power-saving computing.
 

Objective

The goal of this project is to implement a user-level scheduler on the Crusoe processor,
and to control the frequency and voltage levels on the fly according to feedback DVS-EDF.
The following functions are expected in the scheduler:

• A general API to control frequency and voltage levels for Cursoe. The API should be able to be easily ported later to other processors.
• An interface to specify real-time tasks requirements, including a task's period, relative deadline, actual execution time, worst case execution time, and other system parameters.
• Scheduling tasks according to feedback DVS-EDF.
• Low overhead of task scheduling and frequency scaling is required.
• Energy consumption can be monitored.

• Traverse each task's specification to create a worst-case scheduling scenario.
• All tasks being scheduled are assumed to be periodic empty tasks (the body of the task is an empty loop). Each task's actual execution time is assumed to be known in advance and is indicated in an input file.
• The task scheduling decision and the frequency scaling decision are made only at the following three occasions:
• each tasks release time
• each tasks completion time
• subtasks splitting time (when a task runs into its Cb portion)
Since each task's actual execution time is known in advance, all the above decision points can be determined statically. The scheduler is to be implemented in a timer signal handler (SIGALRM, installed by setitimer() and signal()), which is triggered exactly at the first decision point. The handler makes the scheduling decision and adjusts the processor frequency and voltage level according to feedback DVS-EDF. Before the handler returns, it installs another timer interrupt, which will be triggered at the next decision point, and so on.
 
• Frequency control is implemented by writing specific registers in the Crusoe processor. Details can be found in longrun.c.
• Power consumption can be benchmarked according to the battery life, or some other metrics.
• In the future, several extensions can be made further under different dimensions:
• Scheduled tasks will be extended to be real tasks (not empty tasks) whose actual execution time is not known until its completion.
• The scheduler will be implemented as a Linux kernel module, which can be linked to the kernel dynamically and to replace the original Linux scheduler module.

Bibliography

[1] "Energy-Conserving Feedback EDF Scheduling for Embedded Systems with Real-Time Constraints" by A. Dudani and F. Mueller and Y. Zhu in ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded
Systems (SCOPES'02), June 2002.
[2] "Preemption Handling and Scalability of Feedback DVS-EDF" by Y. Zhu and F. Mueller in Workshop on Compilers and Operating Systems for Low Power, Sep 2002.
[3] Crusoe documentation
[4] The RTLinux manifesto. by V. Yodaiken In Proc. of the Fifth Linux Expo, Raleigh, NC, Mar. 1999. 11.
[5] www.fsmlabs.com
[6] KURT - Kansas University Real-Time Linux