PollyProf - The Potential of Polyhedral Optimization: An Empirical Study

Analysis Framework

The analysis framework we used is a Makefile based system that instruments projects provided in LLVM-IR and executes a defined set of test-cases for each testing class (Standard, Dynamic, Extended). You can get the source of the framework The archive contains all programs tested with our empirical study, as well as Makefile scripts to execute benchmarks and arbitrary test inputs on these binaries.

Setup

The study can be configured via changes to Makefile.config. Imortant variables are:

Prepare the measurement

The user who runs our analysis framework needs permission to execute processes with the SCHED_FIFO priority queue (see /etc/security/limits.conf). If you don't want to execute within SCHED_FIFO (timings can be wrong/inconsistent) adapt the script test.sh in the top-level directory of the study. You need to change the following line:
exec /usr/bin/time -f "%U,%S,%e" -a -o ${TIME} taskset 0x00000001 chrt -f 20 ${REAL_PROG} $*
to this:
exec /usr/bin/time -f "%U,%S,%e" -a -o ${TIME} taskset 0x00000001 ${REAL_PROG} $*
The download above already contains this change, as usually a user is not allowed to execute in SCHED_FIFO.

Run the analysis

Makre sure the variables are set up properly are set up to contain: Make sure polly-prof and our modified LLVM is available in your PATH and execute:
make report -i
Make sure it starts spending some time on the opt tool instead of throwing up on errors. With VERBOSE enabled you should see the following
mkdir -p std
clang -Xclang -load -Xclang ......
proceeding without errors. This can take a while (Expect at least 1 day). This builds the binaries for each testing class, executes the tests and generates the required report files. Ignoring the errors is necessary for now, as some tests may return error codes, which we do not ignore properly in our Makefiles yet. Afterwards you can generate the merged data set (as shown below) by executing:
make diagrams

Compiled results

The compressed results can be found in the following table:

Raw data

The table above was generated using the following raw data, generated with our empirical analysis framework.
NameSthDynTsthJitDynTjitExtDynTextTrawDomainTsth_papiTjit_papiText_papiCallsSthCallsJitCallsExt
xlintstrfs5.959732.7618455.2249614.82755.2371015.87732.54Scientific0.1925649.2594810.15066372253064106033589806
postgres24.17302269.43626.14105288.37144.57173415.8660Database102.599115.661227.514339515698382739705752878654
xlintstc00000015.4Scientific000000
xeigtstc6.5748416.023752.1815954.013752.5891865.104313.86Scientific1.4977731.142640.39364956361103055791133668552
povray15.43327453.03627.61837631.99290.47926781.402313.86Multimedia104.997247.075361.5443474504558176092831196404573
hmac5.645160.00024811.009170.00010911.888110.0001430Encryption6.043846.043846.04384202020
linpack5.8093116.00585.2070516.806285.1294016.674733.91Scientific0.7177721.256651.266237522041584414189389
gzip2.5770412.07383.7682512.433636.4560238.277412.58Compression0.06374950.3044419.8129210957100743965563979
md51.326260.0003775.673760.0001414.225350.0001420Encryption2.115342.115342.11534777
python0000000Compilation12.6024004170332500
xlintstd0000008.51Scientific000000
xlintstds5.440382.3124564.446049.3324964.597009.75762.26Scientific0.01856764.975915.07073614431646606716779837
xeigtstd9.5923815.011950.4047461.430250.7456273.782512.43Scientific1.9531137.700347.28976463129124756077156488853
ccrypt0.338200.12152613.734290.16324145.339500.9440730Encryption0.0002792250.03317680.6684829241097872212110
rc40.000006.4e-050.000006.6e-050.000006.4e-050Encryption000000
xlintstz00000016.74Scientific000000
xeigtstz4.8301620.425850.7458160.805551.3074972.780417.97Scientific1.4440632.678442.16614778634108137757139534156
crocopat3.50389226.8715.21768229.53119.50857343.771149.53Verification11.715918.377699.07323876975960814288327848585
xlintstrfc2.094246.7218849.9006919.169450.8733620.86556Scientific0.1914679.8110110.9966335933246613836387500
mcrypt-ciphers11.500990.05172612.900040.05358937.900830.1378070.02Encryption0.009410560.01084420.07706533114135885255021
sha51271.216800.02300388.185210.02842287.792170.0295630.01Encryption0.004725680.008925850.00892585156382953729537
leveldb1.367780.0579041.749680.077100.07611858.83Database0.0006122410.001103613.887172026365212863243
blowfish0.000000.0030170.848840.0030630.942480.0030770Encryption01.903812.0246906367
minisat6.582182655.726.572472668.539.971422893.982335.83Verification252.54252.917435.4668356950378369406241441023730
sha10.065760.00456289.317390.00484988.346330.0048740Encryption6.043840.0005684230.000568423218811881
des1.075270.0003721.129940.00035436.015040.001330Encryption6.043841.208770.000761222242519
lulesh-omp44.001411281.3846.658141660.7548.110501905.93280.31Simulation782.1981111.541317.5258841280336782693544359801901
js0.314266.0819621.2145610.83137.7998925.75245.9Compilation0.02435373.4776815.2656805901150817950516300
xlintstrfd6.917862.8387155.2795814.734155.0588316.09192.52Scientific0.1925649.2594810.15066372253064106033589806
xz12.47186165.90419.04481201.20638.16606442.429122.79Compression33.511861.4542250.13110895605203361402827719243
xlintsts0000007.88Scientific000000
rsa25.206740.98250328.374001.0978344.675245.406251.19Encryption0.298860.3984623.8396988974131857312705819
xlintstzc0.450773.4531865.012408.6709965.960538.872213.4Scientific0.01789913.992624.10318592311321219013578058
xeigtsts11.2347012.701951.9843857.504852.1229569.163910Scientific1.9428936.061645.74326429313119333422151371255
ruby27.45117773.27668.23405452.39774.505701457.51334.59Compilation339.455246.5681081.9711233085218159332353580404496
ecdsa0.595831.5133530.360953.7192148.7882734.65433Encryption0.009701871.8102826.74832105599049388513145
sha2560.041670.02399670.074350.03590970.979780.0359060.02Encryption1.813150.009447730.0094477363126431264
x2644.6322424.835932.7912954.866240.1960181.400221.83Multimedia1.6954826.885948.9038561061588969491161830294
bn17.285011.4110242.440502.7479849.5581813.33321.95Encryption0.1899991.251269.52644628735414061831524457
tcc1.652621.047731.941121.0498119.028881.593890.78Compilation0.02638470.03110220.465536873111029221540529
sdcc4.6084937.17413.0763945.06527.3795167.163233.93Compilation2.799769.4034226.348992648383111736187192550
dsa14.777190.0657532.382530.13486945.260730.4116460.12Encryption0.006564520.06014470.28630221723199028947418
avconv32.76636391.59845.82239954.05850.473062241.53158.45Multimedia185.103646.0651707.7261253388021379275815651112367
mcrypt-aes0.988470.0006071.034930.0007734.808640.0010190Encryption2.719731.027456.31581934209
crafty32.66182149.38235.68458180.53849.10960762.65649.67Simulation78.253104.134551.1032589511913445938591823685121
cast23.136071.8219123.688171.8328852.315592.550862.22Encryption0.6043850.6043851.20877200000320000034000006
sqlite33.37639209.7710.54960253.08842.850961222.55133.74Database10.346742.3868826.465342389681402644952734900865
7za17.1108387.677117.1943186.794136.24539182.44458.49Compression22.178322.178496.32777339156173391595318763285
lulesh19.81049358.9420.87439360.15634.13904562.886221.18Simulation82.336482.3397247.041272463799272474936817496596
lammps23.66195571.56741.878951578.1149.630172737.59297.26Simulation212.6831007.11945.270380010933326551386436962735
bzip25.0750418.000317.8098923.361248.40733149.86116.43Compression1.250965.54803104.472413963518359303345715359