federeghe / chronovise Goto Github PK

Implement a new estimator: Generalised Maximum Likelihood Estimation (GMLE)

as suggested by #11

No paper mentioning WCET is complete without reference to its seminal paper: https://doi.org/10.1145/1347375.1347389 Please add the citation after the first appearence of WCET.

The MLE and PWM abbreviations are mentioned without explaining their meaning. Please provide their definition. Moreover, you need to provide a citations for them, as you have already done for the Kolmogorov-Smirnov and Anderson-Darning tests. A citation is needed also for Block-Maxima, Peak-over-threshold, Generalised Extreme Value and Generalised Pareto Distribution.

Also, seminal papers and state-of-the-art resources for MBPTA are missing:

• https://doi.org/10.1109/ECRTS.2012.31 was the first paper to introduce MBPTA, which is based on EVT. Moreover, an appropriate citation for EVT should be provided.

• https://www.tdx.cat/handle/10803/460819?locale-attribute=en my PhD thesis explains that in order to safely use MBPTA certain properties needs to be present. This is that:

  a) the execution times processed by EVT need to be independent and identically distributed random variables (i.i.d.). This is a requirement coming from EVT theory and has been relaxed later by Santinelli et al under certain circumstances.

  b) the events that take place during analysis and affect the execution time of the program (eg. cache misses) must be equal or worse than the ones that take place at operation. This is a requirement of MBPTA in order to ensure that the pWCET is not underestimated, and it is described in the literature as
  representativeness.

  It is very important to note that those properties are not present in existing platforms, so MBPTA cannot be applied on them without additional measures. In my thesis I proposed hardware and software solutions that make this possible. A simple solution is to make the events that affect the execution time, eg. cache misses, random from execution to execution, so that both properties are satisfied by construction: 1. the cache misses do not depend from one execution to another -> independence, 2. the events follow the same random distribution from execution to execution -> identical distribution, 3. due to identical distribution, the events that happen at analysis are the same with the ones at operation.

  Currently the paper only mentions the requirement a) but not b). I think it is very important that the paper mentions both requirements of MBPTA, to prevent that people are using chronovise (and therefore MBPTA) blindly, without ensuring its correct application, because this can result in unsafe pWCET estimates.

• https://doi.org/10.1145/3065924 identifies and solves a problem of classical MBPTA, proposing MBPTA-CV; MBPTA-CV takes values only from the tail of the distribution, which are used to model the tail of the distribution with EVT. In contrast, original MBPTA uses values from the entire distribution processed with Block-Maxima or Peak-Over Threashold, which may not belong to the tail of the distribution, resulting in a Generalised Extreme Value (GEV) or Generalised Pareto (GP) distribution with shape that is unsuitable for pWCET use. Thefore, MBPTA-CV can obtain pWCET in cases that original MBPTA fails, while it requires the collection of fewer samples.

• https://doi.org/10.1145/3185154 This independent comparison study performed a comparison between the Exponential Model employed by MBPTA-CV and the Block-Maxima or Peak-Over Threashold used by original MBPTA. It shows that the Exponential Model provides sound results, while Block-Maxima or Peak-Over Threashold can provide unsafe pWCETs (underestimation).

In addition to the above missing references, it is worth to note that MBPTA-CV is available as open source from https://doi.org/10.5281/zenodo.1065776 Therefore, the claim in the paper that source code for MBPTA is not available has to be revised. However, I still think that chronovise is a useful tool for MBPTA, because it can provide a common platform for the comparison of the different approaches.

In this aspect, I would like to see MBPTA-CV (Exponential Model and selecting data only from the tail) to be implemented in chronovise, as well as at least the EQMAE (Estimated Quantile's Mean Absolute Error) minimisation criterion proposed in https://doi.org/10.1145/3185154 although the implementation of the
Generalised Maximum Likelihood Estimation (GMLE) and L-moments would be nice to have, too. The reason is that those missing features are considered the current state of the art in MBPTA, and therefore they must be included in chronovise in order to increase its use from the research and engineering community. I believe that implementing those additional features will not be very difficult, since chronovise seems to be extensible.

Finally, please fix some entries in the references section (Ieee, Sies, Rtas) and make sure that all entries follow the same format (some entries have the full first names of the authors while some others only the first letter, some entries have first the surname of the author etc).

@federeghe - I tried to build the software for the JOSS review and had a problem with the compiler versions. I tried several versions of gcc up to 4.9, and clang 3.8 but they fail to compile. It builds ok with gcc-5.4. So you can modify the requirements ("What you need" Section at README.md) as follows:
A modern compiler with C++14 support like GCC (version 5 or later) or LLVM (XX version or later) and the CMake building tool.

Also for configuring the project:
In case that you have multiple complilers installed in your system, you can specify a compatible compiler as follows:
CC=gcc-5 CXX=g++-5 cmake ..

@federeghe - according to the license of each of the original images (https://creativecommons.org/licenses/by-sa/2.5/deed.en and https://support.flaticon.com/hc/en-us/articles/207248209-How-I-must-insert-the-attribution-) you need to attribute the author as well in addition to the link to the original images.

Implement PoT approach besides BM approach. The distribution should be a GPD.

Related bug: #6

The following tasks have to be performed:

• Build a shared library also (to check if ceres is ok)
• Put in subdirectory the examples
• Compile tests only if an argument is supplied to cmake (or make tests)
• Add code coverage analysis
• Compile documentation only if required

PWM estimator is a good candidate to be added as another option to MLE.

Unfortunately, MLE estimator must work with double, however this may impact on the precision if an T_TIME=unsigned long (as it is currently). An evaluation and fixes are required to fix this problem.

In general the provided documentation is in a very good shape. I think that the page about the brief information about MBPTA is very useful for any end user that is going to use it.

I only have some small suggestions for improvement:

• The member functions in the SimpleExecutionContext class miss doxyzen documentation
• The Sample applications documentation page should be expanded to cover the new example simple_hello_world_cv_2.cpp. It doesn't need to be long, just to mention that it shows how you can feed measurement samples to chronovise, preferably read from a file once the feature #15 is implemented.

Add an Erlang upper-bounder like "Probabilistic Deadline Miss Analysis of Real-Time Systems Using Regenerative Transient Analysis" L. Carnevali et al. 2014.

steps to reproduce:

git clone https://github.com/federeghe/chronovise.git
cd ./chronovise/
mkdir build
cd build
cmake -DCERES_SOLVER=OFF ..
make

output:

[  2%] Building CXX object CMakeFiles/chronovise.dir/src/input/generator_uniform.cpp.o
[  5%] Building CXX object CMakeFiles/chronovise.dir/src/aec.cpp.o
[  7%] Building CXX object CMakeFiles/chronovise.dir/src/aec_hmi.cpp.o
[ 10%] Building CXX object CMakeFiles/chronovise.dir/src/evt/gev_distribution.cpp.o
[ 12%] Building CXX object CMakeFiles/chronovise.dir/src/evt/gpd_distribution.cpp.o
[ 15%] Building CXX object CMakeFiles/chronovise.dir/src/evt/evtapproach_bm.cpp.o
[ 17%] Building CXX object CMakeFiles/chronovise.dir/src/evt/evtapproach_cv.cpp.o
[ 20%] Building CXX object CMakeFiles/chronovise.dir/src/evt/evtapproach_pot.cpp.o
[ 22%] Building CXX object CMakeFiles/chronovise.dir/src/evt/pwcet.cpp.o
[ 25%] Building CXX object CMakeFiles/chronovise.dir/src/safety.cpp.o
[ 27%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_ad.cpp.o
[ 30%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_bds.cpp.o
[ 32%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_cvm.cpp.o
[ 35%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_kpss.cpp.o
[ 37%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_ks.cpp.o
[ 40%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_rs.cpp.o
[ 42%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/estimator_pwm.cpp.o
[ 45%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/estimator_cv.cpp.o
[ 47%] Building CXX object CMakeFiles/chronovise.dir/src/statistical/test_ljung_box.cpp.o
[ 50%] Building CXX object CMakeFiles/chronovise.dir/src/utility/relation_node.cpp.o
[ 52%] Building CXX object CMakeFiles/chronovise.dir/src/utility/utility_hmi.cpp.o
[ 55%] Building CXX object CMakeFiles/chronovise.dir/src/utility/exporter.cpp.o
[ 57%] Building CXX object CMakeFiles/chronovise.dir/src/utility/fileimporter.cpp.o
[ 60%] Linking CXX static library libchronovise.a
[ 60%] Built target chronovise
Scanning dependencies of target chronovise-app
[ 62%] Building CXX object apps/chronoapp/CMakeFiles/chronovise-app.dir/chronoapp.cpp.o
[ 65%] Linking CXX executable chronovise-app
/usr/bin/ld: CMakeFiles/chronovise-app.dir/chronoapp.cpp.o: in function `void execute_pwcet_estimation<double>(chronovise::MeasuresPool<int, double> const&)':
/home/denisovlev/Projects/chronovise/apps/chronoapp/chronoapp.cpp:186: undefined reference to `chronovise::Estimator_MLE<int, double, false>::run(chronovise::MeasuresPool<int, double> const&)'
/usr/bin/ld: CMakeFiles/chronovise-app.dir/chronoapp.cpp.o: in function `void execute_pwcet_estimation<unsigned long>(chronovise::MeasuresPool<int, unsigned long> const&)':
/home/denisovlev/Projects/chronovise/apps/chronoapp/chronoapp.cpp:186: undefined reference to `chronovise::Estimator_MLE<int, unsigned long, false>::run(chronovise::MeasuresPool<int, unsigned long> const&)'
/usr/bin/ld: CMakeFiles/chronovise-app.dir/chronoapp.cpp.o:(.data.rel.ro._ZTVN10chronovise13Estimator_MLEIimLb0EEE[_ZTVN10chronovise13Estimator_MLEIimLb0EEE]+0x20): undefined reference to `chronovise::Estimator_MLE<int, unsigned long, false>::run(chronovise::MeasuresPool<int, unsigned long> const&)'
/usr/bin/ld: CMakeFiles/chronovise-app.dir/chronoapp.cpp.o:(.data.rel.ro._ZTVN10chronovise13Estimator_MLEIidLb0EEE[_ZTVN10chronovise13Estimator_MLEIidLb0EEE]+0x20): undefined reference to `chronovise::Estimator_MLE<int, double, false>::run(chronovise::MeasuresPool<int, double> const&)'
collect2: error: ld returned 1 exit status
make[2]: *** [apps/chronoapp/CMakeFiles/chronovise-app.dir/build.make:85: apps/chronoapp/chronovise-app] Error 1
make[1]: *** [CMakeFiles/Makefile2:253: apps/chronoapp/CMakeFiles/chronovise-app.dir/all] Error 2
make: *** [Makefile:84: all] Error 2

Implement the EQMAE method (https://doi.org/10.1145/3185154). This requires a change in the EVT process flow that should be carefully evaluated.

Suggested in #11

Implement a new estimator: L-moments

Suggested in #11

Currently, the EV distribution is written as a single distribution corresponding to the GEV distribution, however we should consider the GPD also, so we have to refactor the EV class. Probably we have to rename EV -> GEV and create a parent class.

In the simple_hello_world_cv_2.cpp example the time samples are provided statically in an array defined in the test_cv_values.h header file. However, this means that the program has to be recompiled every time in order to be used with a new data set.

In order chronovise to be easier to use by end-users (e.g. engineers not developers) , it would be useful to provide a utility function that can parse directly an input file such as test_cv_values.txt. Moreover, this will provide compatibility with MBPTA-CV.

Implement the Anderson-Darling test and the modified version of it.