RTSS 2016 - Artifact Evaluation

This tutorial explains how to reproduce the experiments discussed in the paper

A. Biondi, A. Balsini, M. Pagani, E. Rossi, M. Marinoni, G. Buttazzo - "A Framework for Supporting Real-Time Applications on Dynamic Reconfigurable FPGAs", IEEE Real-Time Systems Symposium (RTSS 2016), to appear, November 2016

This document is organized as follows:

Environment setup
1.1 Environment from scratch
1.2. Virtual machine
How to compile and run the experiments
Overview of the code structure

Please follow the instructions detailed in each section. In case of problems or further questions, feel free to contact us by email.

Note: Altough the software infrastructure of this artifact is platform-independent, the instructions provided in this dcument refer to an environment setup for the Linux operating system.
The following commands and examples have been tested on the latest release of Ubuntu Linux to date (16.04).

1. Environment setup

The schedulability analyses presented in Section IV of the paper have been implemented in C++11 and make use of a linear program solver.
We strongly recommend the use of IBM CPLEX solver (tested during our experiments).
The open-source solver GNU Linear Programming Kit (GLPK) can also be used, however it is discouraged.
We report the instructions to support only these two solvers.

Warning: Despite of being free, open-source and easily installable, GLPK has several bugs that (in most of the cases) prevent to run the experiments.

The following sections describe the steps required to run the experiments discussed in Section V.
We provide two ways to replicate the experiments:

by setting up the whole environment from scratch; or
by using a ready-to-use virtual machine.

1.1 Environment from scratch

To compile and execute the experiments is it necessary to install the following three software components:

A Linear Program Solver;
The CMake tool; and
The LEMON library.

Below, we report the detailed instructions to install each of these software components.

1.1.1 Installing a Linear Program Solver

Thanks to the abstraction provided by the LEMON library, our analysis framework is able to work with several linear program solvers. However, we report the instructions to support only IBM CPLEX and GLPK.

IBM CPLEX (recommended)

IBM ILOG CPLEX is a commercial software. A 90-days trial version can be freely downloaded from here.

Free academic licenses are also available.

For instance, if the 90-days trial version is used under Linux (x86_64), at the date in which these istructions have been written it is possible to download the file COSCE1263LIN64.bin from the IBM web-site. The filename may change when newer versions of CPLEX will be released.
Once the installer has been downloaded, give it execution privileges and execute it

$ chmod +x COSCE1263LIN64.bin

$ sudo ./COSCE1263LIN64.bin

GLPK (discouraged)

GLPK (GNU Linear Programming Kit) is typically available as a package for most Linux distributions. On a debian-based distirbution, GLPK can be installed as follows

$ sudo apt-get install libglpk-dev

Note: In order to use GLPK with LEMON, LEMON must be fully recompiled with the proper configuration. Please refer to Installing LEMON section for the detailed instructions.

1.1.3 Installing CMake

CMake is typically available as a package for most Linux distributions.
On a debian-based distirbution, CMake (and the corresponding Linux bulding tools) can be installed as follows

$ sudo apt-get install cmake build-essential

1.1.2 Installing LEMON

LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is an open-source C++ template library providing efficient implementations of common data structures and algorithms with focus on optimization methods for graphs and networks.
Limited to this analysis framework, LEMON is used as an abstraction layer to write code that is independent of the specific APIs of the linear solvers.

Warning: The current stable release of LEMON (1.3.1) has issues in identifying the CPLEX solver: the problem seems solved in the lastest (but not stable) version of the library.

Please perform the following commands to install the latest version of LEMON

First, create the folder ~/RTSS2016 and navigate in it

$ mkdir ~/RTSS2016

Then install Mercurial, clone the LEMON repository and prepare the directory to compile the library

$ sudo apt-get install mercurial

$ hg clone http://lemon.cs.elte.hu/hg/lemon

$ cd lemon

$ mkdir build

$ cd build

If IBM CPLEX is used execute the following command (please fix the path if a different version of IBM CPLEX is used)

$ cmake .. -DILOG_ROOT_DIR=/opt/ibm/ILOG/CPLEX_Studio_Community1263

Otherwise, if GLPK is used, just run cmake with no options

$ cmake ..

Finally, it is possible to make and install the LEMON library

$ make

$ sudo make install

1.2 Virtual machine

To simplify the environment setup, a virtual machine disk is available for download at this address.
This virtual machine disk can be run through Virtual Box.

The credentials for accessing the virtual machine are the following

username: osboxes
password: password

The virtual machine is already equipped with the GLPK linear solver: however, its use is discouraged.
We recommend the use of IMB CLPEX.
IBM CPLEX is a commercial software, hence it cannot be redistributed with the virtual machine provided for this artifact evaluation. A 90-days trial version can be freely downloaded from here. Free academic licenses are also available.
Please refer to the previous section for the instructions to install CLPEX.

Note: Once CPLEX is installed, LEMON must be recompiled with the proper configuration in order to make CPLEX the default linear solver. Please refer to the corresponding instructions.

2. How to compile and run the experiments

The following steps explain how to compile and run the experiments presented in Section IV of the paper.

First, download and extract the compressed folder that contains the source code of the analyses. If the Virtual Machine is used, this step can be skipped since the folder is already available in the home directory ~/RTSS/.

$ wget RTSS2016_FRED.tar.gz

$ tar xvf RTSS2016_FRED.tar.gz

Then, move into the uncompressed folder

$ cd RTSS2016_FRED

To compile the source code, two parameters are available:

solver={CPLEX, GLPK}, to decide which linear program solver is used;
runs=value: the number of runs (i.e., collected samples, repetitions) to be performed for each value varied in the experiments. The default value is 500 (the same chosen for the experiments in paper), but can be decreased to speed-up the experiments at the cost of less accuracy due to sampling noise.

For instance, the following command compiles the analysis framework with IBM CPLEX and 500 runs

$ make solver=CPLEX runs=500

Note: If the solver is switched, it is necessary to run make clean before compiling the analysis framework with the new parameter.

The experiments presented in Figures 6, 7 and 8 of the paper can be run by launching the following command

$ ./RTSS_FRED

Warning: It bears repeating that, if GLPK is used, it can happen that the experiment will hang due to the bugs discussed in the previous section. Note that this a limitation of GLPK and not of our implementation. If this happens, please kill the process and re-execute the above command.
Again, we recommend the use of IBM CPLEX to run the experiments.

Interpreting the outputs

The last command produces data on the standard output in order to check the execution progress.
Experimental results are stored in the following txt files:

swPP.txt: data used to generate Figure 6 (Schedulability ratio as function of U).
hwPP.txt: data used to generate Figure 7 (Schedulability ratio as function of U^H).
appendPP.txt: data used to generate Figure 8 (Schedulability ratio as function of increasing number of tasks).

The numbers in the output files represent the measured schedulability ratios for each tested analysis.

The output files should look structurally as follows:

U	P	NP	Sta	SW
0.05	1	1	1	1
0.1	1	1	1	1
0.15	1	1	1	1
0.2	1	1	1	0.99
0.25	1	1	1	0.43
0.3	1	1	1	0.05
0.35	1	1	1	0
0.4	1	1	1	0
0.45	1	1	1	0
0.5	1	1	1	0
0.55	0.946	0.932	0.998	0
0.6	0.574	0.498	0.964	0
0.65	0.136	0.118	0.778	0
0.7	0.024	0.018	0.438	0
0.75	0.004	0.004	0.13	0
0.8	0	0	0	0
0.85	0	0	0	0
0.9	0	0	0	0

The first column represents the parameter varied in the experiment (utilization factor in this example) while the other columns report the schedulability ratio for each tested analysis.
Specifically, the labels have the following meanings:

P (FRED-P): the approach proposed in the paper, used with preemptive FRI management;
NP (FRED-NP): same as FRED-P but with non-preemptive FRI management;
Sta (Static): the FPGA is supposed to have an infinite area, meaning that all the HW-tasks are statically assigned to a fixed slot and do not require reconfiguration;
SW (Software): a pure software implementation of the tested task sets.

3. Overview of the Code Structure

The following files can be found in the package provided with this artifact evaluation and contain the implementations of the analyses proposed in the paper.

File	Description
main.cpp	Prepares the task sets parameters and calls all the functions associated to the experiments
delay_bound.h/cpp	Computes the delay bounds stated by Theorem 1 and Theorem 2 in the paper
generator.h/cpp	Generator of task sets and platform configurations. Definition of the data structures to represent SW- and HW-tasks in FRED
rta_ss.h/cpp	Implementation of the response-time analysis for self-supending tasks proposed by Nelissen et al. in [27]
ss_task.h	Definition of the data structure to represent a self-suspending task