This project aim to create a new implementation pattern for interpreters. The main objective is to define an architectural solution to resolve the problem of dynamic adaptation in language interpreters. To do that, we plan to use a modular approach defining an interface in the language specification and multiple modules of dynamic adaptation.
To make this project work correctly you need to clone the ALE Language and do a mvn install
at the root of the project. With this you'll get the appropriate dependancies in your .m2 folder.
This project need to be compiled using Java 8.
In order to validate our approach, we have tested the adaptive Sobel filter on two images, a small one with easily detectable edges, and a big image with less visible edges (the filter is less precise on the ground).
Interpolation | Aproximated version | Reference version |
---|---|---|
1/2 pixels | ![]() |
![]() |
3/4 pixels | ![]() |
![]() |
7/8 pixels | ![]() |
![]() |
Interpolation | Aproximated version | Reference version |
---|---|---|
1/2 pixels | ![]() |
![]() |
3/4 pixels | ![]() |
![]() |
7/8 pixels | ![]() |
![]() |
One of the conclusion on the quality of the produced images, is that the number of interpolated pixels should also depend on the size of the images. In fact, while the high definition image seems to be lightly impacted by the maximum interpolation, the output of the small image seems to be at the limit of being usable in image processing algorithms. However, the result on smaller interpolation ratio show that the impact on the quality of the resulting output is totally acceptable. Moreover, the interpolation ratio of three-quarter of the pixels show the interest of our approach by showing speedup comparing to the reference imprementation of the Virtual Machine while giving as output a degraded but usable edge detection.
The following content is an export of the statistic analysis done for the evaluation of the Self-Adaptable implementation of MiniJava for image processing. This snapshot of the results was made the 2020-10-17.
This notebook aim at providing the analysis process of the Self-Adaptable implementation of MiniJava performances for image processing with an Approximate Loop Unrolling adaptation. This implementation is compared to a reference implementation based on the interpreter design pattern.
from os import listdir
from os.path import isfile, join
import math
import pandas as pd
import json
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
import scipy.stats as st
Build the datastructure containing the results of JMH benchmarks. All the benchmarks were executed on Debian 9 with the Krun kernel, 15Go of RAM, an Intel(R) Xeon(R) W-2104 CPU (Quad Core - 3.20GHz), and run on the GraalVM CE JVM version 20.2.0.
root_dir = './results/'
results=[]
for f in listdir(root_dir):
path = join(root_dir, f)
if isfile(path):
fo = open(path)
jso = json.loads(fo.read())
splt = f.split('_')
vm = splt[0]
stress = splt[1][6:]
measureNb = splt[2]
for (idx, time) in enumerate(jso[0]['primaryMetric']['rawData'][0]):
results.append({
'vm': vm,
'stress': int(stress),
'try': measureNb,
'time': time,
'idx': idx
})
df = pd.DataFrame(results)
df.describe(include='all')
vm | stress | try | time | idx | |
---|---|---|---|---|---|
count | 900 | 900.000000 | 900 | 900.000000 | 900.000000 |
unique | 2 | NaN | 3 | NaN | NaN |
top | reference | NaN | tryI | NaN | NaN |
freq | 450 | NaN | 300 | NaN | NaN |
mean | NaN | 50.000000 | NaN | 13.373716 | 14.500000 |
std | NaN | 35.374997 | NaN | 4.602772 | 8.660254 |
min | NaN | 0.000000 | NaN | 8.198310 | 0.000000 |
25% | NaN | 25.000000 | NaN | 10.880730 | 7.000000 |
50% | NaN | 50.000000 | NaN | 12.630456 | 14.500000 |
75% | NaN | 75.000000 | NaN | 13.175090 | 22.000000 |
max | NaN | 100.000000 | NaN | 25.830481 | 29.000000 |
variances = pd.DataFrame(df.groupby(["vm", "stress"]).time.var())
variances["vm"] = ""
variances["Stress"] = ""
variances.vm = variances.index.get_level_values(0)
variances.Stress = variances.index.get_level_values(1)
variances.index = range(10)
variances.rename(columns={"time":"Variances"}, inplace=True)
deviations = pd.DataFrame(df.groupby(["vm", "stress"]).time.std())
deviations["vm"] = ""
deviations["Stress"] = ""
deviations.vm = deviations.index.get_level_values(0)
deviations.Stress = deviations.index.get_level_values(1)
deviations.index = range(10)
deviations.rename(columns={"time":"Deviation"}, inplace=True)
means = pd.DataFrame(df.groupby(["vm", "stress"]).time.mean())
means["vm"] = ""
means["Stress"] = ""
means.vm = means.index.get_level_values(0)
means.Stress = means.index.get_level_values(1)
means.index = range(10)
means.rename(columns={"time":"Mean"}, inplace=True)
medians = pd.DataFrame(df.groupby(["vm", "stress"]).time.median())
medians["vm"] = ""
medians["Stress"] = ""
medians.vm = medians.index.get_level_values(0)
medians.Stress = medians.index.get_level_values(1)
medians.index = range(10)
medians.rename(columns={"time":"Median"}, inplace=True)
stats = pd.concat([variances, means, medians, deviations], axis=1)
stats["Variance"] = 0
stats.Variance = stats.Variances
del stats["Variances"]
stats = stats.loc[:,~stats.columns.duplicated()]
stats = stats.sort_values(['Stress', 'vm'])
stats.index = range(10)
stats
vm | Stress | Mean | Median | Deviation | Variance | |
---|---|---|---|---|---|---|
0 | adaptive | 0 | 25.574801 | 25.538089 | 0.163591 | 0.026762 |
1 | reference | 0 | 12.605884 | 12.599488 | 0.060774 | 0.003693 |
2 | adaptive | 25 | 16.297958 | 16.300900 | 0.040881 | 0.001671 |
3 | reference | 25 | 12.598613 | 12.594642 | 0.033373 | 0.001114 |
4 | adaptive | 50 | 10.883349 | 10.880684 | 0.035120 | 0.001233 |
5 | reference | 50 | 12.667502 | 12.667936 | 0.032941 | 0.001085 |
6 | adaptive | 75 | 8.454307 | 8.292755 | 0.343647 | 0.118093 |
7 | reference | 75 | 12.674002 | 12.673094 | 0.053748 | 0.002889 |
8 | adaptive | 100 | 8.758603 | 8.687938 | 0.318147 | 0.101217 |
9 | reference | 100 | 13.222144 | 13.176022 | 0.210273 | 0.044215 |
compute_stats : print estimation of the mean and confidence interval of the data
def compute_stats(values):
mean = np.mean(values)
lo, hi = st.t.interval(0.95, df=(len(values) - 1), loc=mean, scale=st.sem(values))
print("Estimated mean : " + str(mean))
print("Confidence interval : [" + str(lo) + ", " + str(hi) + "] delta = " + str(mean - lo))
adaptive = df[df.vm == "adaptive"]
reference = df[df.vm == "reference"]
adaptive_stress0 = adaptive[adaptive.stress == 0]
adaptive_stress25 = adaptive[adaptive.stress == 25]
adaptive_stress50 = adaptive[adaptive.stress == 50]
adaptive_stress75 = adaptive[adaptive.stress == 75]
adaptive_stress100 = adaptive[adaptive.stress == 100]
reference_stress0 = reference[reference.stress == 0]
reference_stress25 = reference[reference.stress == 25]
reference_stress50 = reference[reference.stress == 50]
reference_stress75 = reference[reference.stress == 75]
reference_stress100 = reference[reference.stress == 100]
t_stress0, p_stress0 = st.ttest_ind(a=reference_stress0.time.tolist(), b=adaptive_stress0.time.tolist(), equal_var=False)
t_stress25, p_stress25 = st.ttest_ind(a=reference_stress25.time.tolist(), b=adaptive_stress25.time.tolist(), equal_var=False)
t_stress50, p_stress50 = st.ttest_ind(a=reference_stress50.time.tolist(), b=adaptive_stress50.time.tolist(), equal_var=False)
t_stress75, p_stress75 = st.ttest_ind(a=reference_stress75.time.tolist(), b=adaptive_stress75.time.tolist(), equal_var=False)
t_stress100, p_stress100 = st.ttest_ind(a=reference_stress100.time.tolist(),b=adaptive_stress100.time.tolist(),equal_var=False)
pvalues = [p_stress0, p_stress25, p_stress50, p_stress75, p_stress100]
effectSize = stats.copy()
effectSize["P Values"] = 0
effectSize["Effect Size"] = 0
effectSize["Absolute Effect Size"] = 0
for i in range(10):
if effectSize.loc[i,"vm"] == "adaptive":
SDpooled = math.sqrt((89*effectSize.loc[i+1,"Variance"]+89*effectSize.loc[i,"Variance"])/178)
meanDiff = effectSize.loc[i+1,"Mean"]-effectSize.loc[i,"Mean"]
effectSize.loc[i,"Effect Size"] = meanDiff / SDpooled
effectSize.loc[i+1,"Effect Size"] = 0
effectSize.loc[i,"Absolute Effect Size"] = abs(meanDiff / SDpooled)
effectSize.loc[i+1,"Absolute Effect Size"] = 0
del effectSize["Mean"]
del effectSize["Median"]
del effectSize["Variance"]
del effectSize["Deviation"]
effectSize = effectSize.groupby(["Stress"]).sum()
effectSize["P Values"] = pvalues
effectSize["Stress"] = ""
effectSize.Stress = effectSize.index.get_level_values(0)
effectSize.index = range(5)
print("Stats for adaptive VM with stress level at 0%")
compute_stats(adaptive_stress0.time.tolist())
print("\nStats for adaptive VM with stress level at 25%")
compute_stats(adaptive_stress25.time.tolist())
print("\nStats for adaptive VM with stress level at 50%")
compute_stats(adaptive_stress50.time.tolist())
print("\nStats for adaptive VM with stress level at 75%")
compute_stats(adaptive_stress75.time.tolist())
print("\nStats for adaptive VM with stress level at 100%")
compute_stats(adaptive_stress100.time.tolist())
print("\n\n\nStats for reference VM with stress level at 0%")
compute_stats(reference_stress0.time.tolist())
print("\nStats for reference VM with stress level at 25%")
compute_stats(reference_stress25.time.tolist())
print("\nStats for reference VM with stress level at 50%")
compute_stats(reference_stress50.time.tolist())
print("\nStats for reference VM with stress level at 75%")
compute_stats(reference_stress75.time.tolist())
print("\nStats for reference VM with stress level at 100%")
compute_stats(reference_stress100.time.tolist())
effectSize
Stats for adaptive VM with stress level at 0%
Estimated mean : 25.57480081015556
Confidence interval : [25.540537433595826, 25.60906418671529] delta = 0.034263376559731995
Stats for adaptive VM with stress level at 25%
Estimated mean : 16.297958178133335
Confidence interval : [16.28939578405871, 16.306520572207962] delta = 0.008562394074626667
Stats for adaptive VM with stress level at 50%
Estimated mean : 10.883349342033332
Confidence interval : [10.875993569659844, 10.89070511440682] delta = 0.0073557723734882785
Stats for adaptive VM with stress level at 75%
Estimated mean : 8.454307300866665
Confidence interval : [8.382331807749136, 8.526282793984194] delta = 0.07197549311752915
Stats for adaptive VM with stress level at 100%
Estimated mean : 8.758603195688888
Confidence interval : [8.691968679732373, 8.825237711645403] delta = 0.06663451595651537
Stats for reference VM with stress level at 0%
Estimated mean : 12.605883964122222
Confidence interval : [12.59315511208231, 12.618612816162134] delta = 0.012728852039911587
Stats for reference VM with stress level at 25%
Estimated mean : 12.598612847099998
Confidence interval : [12.591622980866909, 12.605602713333088] delta = 0.006989866233089614
Stats for reference VM with stress level at 50%
Estimated mean : 12.667501712433333
Confidence interval : [12.6606022526539, 12.674401172212766] delta = 0.006899459779432959
Stats for reference VM with stress level at 75%
Estimated mean : 12.67400237858889
Confidence interval : [12.662745132295244, 12.685259624882535] delta = 0.01125724629364555
Stats for reference VM with stress level at 100%
Estimated mean : 13.222143579022223
Confidence interval : [13.178102749755944, 13.266184408288503] delta = 0.0440408292662795
P Values | Effect Size | Absolute Effect Size | Stress | |
---|---|---|---|---|
0 | 7.080518e-208 | -105.096197 | 105.096197 | 0 |
1 | 5.968148e-294 | -99.134433 | 99.134433 | 25 |
2 | 5.065232e-254 | 52.400715 | 52.400715 | 50 |
3 | 2.139275e-102 | 17.156765 | 17.156765 | 75 |
4 | 4.095489e-149 | 16.552534 | 16.552534 | 100 |
Here we try to evaluate the impact of the stress put on the system on the reliability of our benchmarks
sns.catplot(x="Stress", y="Absolute Effect Size", kind="bar", data=effectSize, legend_out=True);
As we can see, the effect size decrease when the stress rise. However, the fact that there is no big difference between 75% and 100% can alarm us on the fact that our approximate loop unrolling adaptive module can be the root cause of the effect size decrease. Yet our data can not show the difference between both due to the strong correlation of those variables in our experiment.
sns.lineplot(data=df, x="idx", y="time", hue="vm", style="stress");
grid = sns.FacetGrid(df, col="stress", hue="vm", sharey=True)
grid.map(sns.lineplot, "idx", "time");
sns.catplot(x="Stress", y="Mean", hue="vm", kind="bar", data=means, sharex=False, legend_out=True);
As the different plot shows, our approach has an important overhead when no adaptations can be done. We assume that it is due to the internal decision model that is called at every MAPE-K loop iteration, hence, when no module can provide optimizations for this concern, the system suffer of performance issues. However, the plots also shows that when the adaptations kick-in, the adaptive version can perform better than the original implementation (which is designed using an interpreter design pattern which is the best in terms of performances). This highlight the challenge behind Self-Adaptable Virtual Machines which is the implementation of an efficient generic feedback loop.