Maximizing the System Value while Satisfying Time and Energy Constraints

Based on a paper published in RTSS'02 [ RTSS02.ps ] [ RTSS02.pdf ]

Written by Patrick E. Lanigan
while working with the PARTS project at
the University of Pittsburgh

This applet requires J2RE 1.3.1, but version 1.4.0 & higher is recommended.

Get the latest Java 2 Runtime Environment here.

Index

Introduction

"Typical real-time scheduling theory has addressed deadling and energy constraints as well as deadline and reward constraints simulataneously in the past. However, we believe that embedded devices with varying applications typically have three constraints that need to be addressed: energy, deadline, and reward. These constraints play important roles in the next generation of embedded devies, since they provide users with a variety of QoS-aware trade-offs. An optimal scheme would allow the device to run the most critical and valuable applications, without depleting the energy source while still meeting all deadlines" - from Rusu, Melhem, Mosse, "Maximizing the System Value while Satisfying Time and Energy Constraints" [ RTSS02.ps ] [ RTSS02.pdf ]

The problem of maximizing the system value while meeting time and energy constraints is NP-hard, requiring exponential time to find the optimal solution. This applet gives a graphical demonstration of two heuristic-based algorithms, REW-pack and REW-unpack, which in logarithmic running time, closely approximate the optimal solution.

For more detailed information on the algorithms demonstrated here, see this paper (PDF version).

[Back to Index]

Quick Start

To get started:

  1. Select the Power Model tab. Choose a predefined power model from the pull-down box.
  2. Select the Task Set tab. Choose a predefined task set from the pull-down box.
  3. From the pull-down box at the top of the applet, select an algorithm.
  4. Click "Run Simulation".
  5. The results will be displayed in the bottom portion of the applet window.

Available algorithms:

Available task models:

Available power models:

[Back to Index]

Parameters

In this section you will find a description of the simulator, task set, and power model user parameters available in the applet.

Simulator

Power Model

Linear Generation

Speed Level Properties

Task Model

Random Generation

Task Properties

[Back to Index]

Experiments

This section describes how to create, edit, and run custom experiments. Custom experiments can be run using a custom task model, a custom power model, or both. These can be made by modifying a predefined model or by generating new models.

Saving to and loading from your local disk is also covered in this section.

Creating an Experiment

Task Model

To create a random task model, in the Task Model panel:

  1. Enter the number of tasks you wish to generate in the # Tasks field.
  2. Hit the "Generate" button.

This will create a task set with the specified number of tasks and attributes assigned randomly within the following intervals: WCET [1, 100], Reward [1, 100], Activity [0.8, 1.2]. Any previously loaded custom task models will be replaced by the newly generated one.

Power Model

To create a new linearly spaced power model, in the Power Model panel:

  1. Enter the number of speed levels you wish to generate in the # Speeds field.
  2. Enter a minimum and maximum voltage, and a minimum and maximum frequency for the power model in the appropriate fields.
  3. Hit the "Generate" button.

This will create a custom power model with speed levels spaced linearly between the miniumum and maximum values. Any previously loaded custom power models will be replaced by the newly generated one.

Editing an Experiment

Individual tasks and speed levels can be added, edited and deleted by following the same basic steps.

Adding an Item

  1. Identify a new item by entering an unused ID in the respective ID field.
  2. Use the mouse or the tab key to move between fields, filling in all the information.
  3. Click the "Add/Change" button to add your new item to the list.

Editing an Item

  1. Select an item to edit by
    1. clicking on it in the display list -or-
    2. entering its ID in the respective ID field and using the mouse or tab key to change fields.
  2. Enter the new values. Note: To change the display color of a speed level, click the color box next to the "Display Color" label. This will bring up a color chooser dialog from which you may choose a new color.
  3. Click the "Add/Change" button to commit your changes.

Deleting an Item

  1. Select an item to edit by
    1. clicking on it in the display list -or-
    2. entering its ID in the respective ID field and using the mouse or tab key to change fields
  2. Click the "Delete" button.

Once a model has been edited, it is saved as a "Custom" model and is accessible through the respective model chooser pull down boxes. You can switch back and forth between predefined models and your custom model. However, only one custom model of each type (power and task) can be loaded in the program at a time. Once changes have been made to another predefined model, the new custom model will replace any previously loaded custom model. For information about saving and loading custom models to and from your local disk, see the next section.

Saving & Loading Experiments Locally

The "Save" and "Load" buttons will only become active if the applet has permission to access your local disk. By default, applet security settings typically do not allow local disk access. In order to save and load task and power models locally, you will need to configure your Java Virtual Machine to give unsigned applets the proper permissions.

If you are unfamiliar with Java permissions and are using the Sun JVM, you can download the standalone application version of the demo. To run the file, type java -jar REWSim.jar at the command line. You must have J2RE v1.3.1 or higher installed.

Task and power models are saved to plain text files. The first line in the file is a header specifying the type of model represented in the file. The second line specifies how many items the model contains. Each item is listed on a space-delimited new line. The last line in each file should be a footer denoting the end of the model. If you wish to generate your own model files, they should use the following formats:

Task Model Power Model

<--BEGIN TASK MODEL-->
[number of tasks]
[item_id] [wcet] [reward] [activity]
... more tasks ...
[item_id] [wcet] [reward] [activity]
<--END TASK MODEL-->

 <--BEGIN POWER MODEL-->
[number of speed levels]
[item_id] [frequency] [voltage]
... more levels ...
[item_id] [frequency] [voltage]
<--END POWER MODEL-->

Viewing Results

Run the simulation by selecting an algorithm and clicking "Run Simulation". A results window will appear in the results display area at the bottom of the application window. Once the algorithm has completed, the results window will be updated to display the schedule found by the algorithm. It will also display the deadline and energy used as a percentage of the total available, the total reward of the schedule, the approximate running time of the algorithm, and the number of steps needed to find a solution.

To get a better view of the results, you can resize the results display area. Drag the separator bar vertically, or use the "One Touch" buttons to expand the display area to your liking. You can also resize the entire application window for more viewing space.

The schedule is represented in two ways. The "Saved Solution" box lists each task in the solution and its associated frequency. The graphs represent each task as a colored bar; the task's speed level is plotted along the y-axis, and the relative energy and deadline usage of each task is plotted along the x-axis of the respective graphs. You can have as many results windows opened at one time as your system's resources allow. The graphs can be zoomed in and out using the buttons located to the bottom right of each graph.

Animation

Animation is controlled using the buttons located in the top left corner of the window. The animation supports play/pause, stop, step forward, and fast forward functions. Pausing the animation freezes it at the current stage. Stopping playback returns the results window to its inital state.

During animation, the graphs change to represent the current selected tasks and their respective speed levels. The animation also lists the current reward, energy usage, and deadline usage of the selected tasks. The best solution found so far is listed in the "Saved Solution" list, with the currently selected tasks listed in the "Selected Tasks" list. Tasks that have not been considered are listed in the "Unused Tasks" list, and once a task has been dropped it is moved to the "Dropped Tasks" list.

The progress bar shows the progress of the algorithm by counting the major steps taken by the algorithm, which include:

  • Adding a task.
  • Droping a task.
  • Increasing the speed of some task.
  • Decreasing the speed of some task.
  • Saving the current solution.

Note: The animator will only record the first 100,000 steps of any experiment for playback. However, the experiment will still run to completion as long as it is not cancelled by the user. (See Resource Concerns Running the Optimal Algorithm)

[Back to Index]

Resource Concerns Running the Optimal Algorithm

The optimal algorithm is very expensive by nature. Accordingly, finding the optimal solution with any more than a few tasks and speed levels can cause problems with memory and processor usage.

In order to facilitate animation, the REWSim traces each algorithm and stores its steps in memory. This trace list is played back each time the experiment is animated. Since the optimal can potentially take millions of steps, trace list can grow very fast consuming large amounts of memory. For this reason, the animator will only record the first 100,000 steps of any experiment. To further reduce the overhead of tracing the algorithms, you can disable animation before running an experiment by deselecting the checkbox labeled "Enable Animation".

You can close the graph window after it appears in the results viewing area to stop the optimal algorithm if it is taking too long to complete or placing too high a load on your processor.

Generally, all of the algorithms perform less operations with tighter constraints. Accordingly, to experiment with more tasks and speed levels, try lowering the energy and deadline available.

[Back to Index]

Page and applet created by Patrick Lanigan,
a current Computer Science student at the University of Pittsburgh.