Task definition

Computation of premium and reserve values for endowment insurance policies. The basis version is stripped down version of a computation module as used by a insurance company. All computations are done with double precision and double-operations as defined by IEEE-754.

The optimized versions has to exactly reproduce the results of the original program. Discrepancies because of optimizations / reordering of floating point operations or due to usage of higher-precision intermediate results are therefore not tolerated.

Team

Bernhard Urban, lewurm@gmail.com
Josef Eisl, josef.eisl@student.tuwien.ac.at
Stefan Neubauer, sneubauer@gmx.at

Presentation

You can find the presentation here.

Running things

Location on g0: /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2011w/bjs
Compiling and running a version, e.g. v5:
> cd src
> cd v5
> make
> ./v5

Basis version - v1

For each of the three present value formulas (survival, death, annuity) there is one function with formulas implemented in straightforward way. Thus the program does match the technical tariff description, is comprehensible and easy to maintain.

With optimization switch -O3 for gcc a drastical performance boost is reached. The compiler inlines all functions except the math library function 'pow'.

The test cases for the performance measurements are generated using the stdlib random number generator with fixed seed value:

Gender: male/female, uniform distribution
Age: 0 to 80, int, uniform distribution
Duration: 10 to 50, int, uniform distribution
Insured sum: 10.000 to 60.000, double, uniform distribution
Interest rate: 0.025 or 0.035, double, uniform distribution; a few special cases with other interest rate values
Additional risk: 0 oder randomly, uniform distribution. If randomly: 0 to 0.3, double, uniform distribution; a few special cases with higher additional risk

Boolean state / variable elimination and differenciation in 'barwert'.
Data structure augmentation: maximum probability values added.
Elimination of redundant computation of vn(i+1) in 'barwert'.
One call of 'barwert' (for i=0) removed from reserve calculation part of doit* because the values have been computd for premium calculation already.
Access of probability values from 'barwert': one dereferenciation eliminated by passing in double*.

v9

Precomputation of normalized results values for addrisk=0

Computation refactored to compute results based on normalized values
Packing into non-uniform array to cut down needed size by factor 2
Include generated static initializer with precomputed values

v10

Caching of mostly used vn-values.

Key for caching (irate) shared with 'doit' cache
Include generated static initializer with precomputed values
Parameter changed to pass over pointer to vn-values (before, global cache was used)

v11

Remove specialized methods that are rarely used.
Augment probability vectors with '1' for maximum age + 1, and get rid of special branches in 'barwert' method.
Short-circuiting test on x+n > 102 by first testing x alone (which can be treated as a simple special case by the way).

v12

Implementation of 'pow' with special cases for 0..3 (although 0 is not used, it gets slower without case 0), and using exp and log for other cases.
Common subexpression put outside of loop in precomputation of vn.

v13

Loop peeling in most heavily used loop (inside 'barwert').
Elimination of second induction variable (age), compute it as (x+i) in the loop body.

Optimization overview

	v1	v2	v3	v3.1	v3.2	v4	v4.1	v4.2	v5	v6	v7	v7.x	v8	v9	v10	v11	v11.1	v11.2	v12	v13	v14
Loop Rule 1: Code motion out of loops									x	x	x	x	x	x	x	x	x	x	x	x	x
Loop Rule 2: Combining Tests
Loop Rule 3: Loop Unrolling												x
Loop Rule 4: Transfer-Driven Unrolling / Modulo Variable Renaming												x
Loop Rule 5: Unconditional Branch Removal	x	x	x	x	x	x	x	x	x	x	x	x	xx	xx	xx	xx	xx	xx	xx	xx	xx
Loop Rule 6: Loop Fusion		x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
Loop Peeling																				x	x
Software Pipelining																					x
Logic Rule 1: Exploit Algebraic Identities									x	x	x	x	x	x	x	x	x	x	xx	x	x
Logic Rule 2: Short-Circuiting Monotone Functions																x	x	x	x	x	x
Logic Rule 3: Reordering Tests
Logic Rule 4: Precompute logical functions
Logic rule 5: Boolean/State Variable Elimination													x	x	x	x	x	x	x	x	x
Long-circuiting
Arithmetic with flags
Alternate flag representation
Space-For-Time 1: Data Structure Augmentation													x	x	x	xx	xx	xx	xx	xx	xx
Space-For-Time 2: Precompute Functions						x	x	x	x	x	xx	xx	xx	xx	xx	xx	xx	xx	xx	xx	xx
Space-For-Time 3: Exploit Common Cases - Memoization (Caching)
Space-For-Time 4: Lazy Evaluation
Time-For-Space 1: Packing							x	x						x
Time-For-Space 2: Interpreters, Factoring
Space-For-Time 1 opposite: Data Structure Reduction					x
Space-For-Time 2 opposite: Recompute Results
Space-For-Time 3 opposite: Uncaching
Space-For-Time 4 opposite: Eager Evaluation
Time-For-Space 1 opposite: Unpacking
Time-For-Space 2 opposite: Compilation to code				x
Procedure Rule 1: Collapsing Procedure Hierarchies - Inlining	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c
Procedure Rule 1: Collapsing Procedure Hierarchies - Specialization										x	x	x	x	x	x	x	x	x	x	x	x
Procedure Rule 2: Exploit Common Cases - Precomputed tables/code sequences												x		x	xx	xx	xx	xx	xx	xx	xx
Procedure Rule 3: Coroutines
Procedure Rule 4: Transformation on Recursive Procedures
Procedure Rule 5: Parallelism - prefetching, instruction scheduling	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c
Recursion or strip mining for cache-blocking
Expression Rule 1: Compile-Time Initialization														x	xx	xx	xx	xx	xx	xx	xx
Expression Rule 2: Strength Reduction/Incremental Algorithms/Differentiation			x	x	x	x	x	x	x	x	x	xx	xx	xxx	xxx	x-	xx	x	xx	xx	xx
Expression Rule 3: Common Subexpression Elimination													x	x	x	x	x	x	xx	xx	xx
Expression Rule 4: Pairing Computation		x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
Expression Rule 5: Exploit word parallelism / SIMD	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c	cx	c	c	c

Results

	took [ms]	total cycles (tsc)	loc	binsize	branch mispred	L2 access	u+s instr	user cycles	system cycles
v1 -O0	40.590	107.811.766.300	191	14.610	252.992.700	4.971.190	133.925.626.549	107.750.516.058	61.302.306
v1 -O3	17.040	45.321.190.740	191	14.563	167.488.975	957.977	66.647.366.781	45.302.381.328	18.828.864
v2	14.820	39.445.528.510	177	13.571	95.634.618	2.350.907	54.201.707.201	39.427.922.795	17.624.268
v3	12.430	33.079.188.560	165	13.379	37.303.026	120.553	40.739.516.826	33.064.169.838	15.037.324
v3.1	12.720	33.821.425.200	339	17.233	72.105.917	1.513.053	40.924.678.034	33.802.838.325	18.614.920
v3.2	12.270	32.663.476.680	160	13.219	42.012.284	902.275	40.567.699.941	32.650.397.448	13.091.556
v4	580	1.541.626.240	172	13.386	4.098.582	55.740	2.593.109.589	1.539.988.691	1.638.380
v4.1	1.010	2.690.269.530	172	12.554	4.132.318	81.065	2.645.301.007	2.688.077.082	2.195.196
v5	530	1.422.501.060	181	13.418	3.842.254	50.645	2.233.418.494	1.420.768.057	1.734.528
v6	520	1.389.941.130	258	14.218	3.616.454	49.063	2.155.970.146	1.386.996.215	2.946.660
v7	300	817.998.800	320	15.057	2.058.831	2.859.787	1.275.602.609	815.891.179	2.109.510
v7.1	340	917.032.100	343	15.313	1.953.671	2.798.885	1.341.472.808	914.662.726	2.370.438
v7.2	330	895.924.070	396	16.049	1.944.563	2.817.180	1.352.886.151	885.217.347	10.707.768
v7.3	570	1.517.942.400	9.626	166.401	2.979.248	81.797.814	1.386.377.618	1.514.630.116	3.313.492
v7.4	1.350	3.605.461.390	1.391.811	31.745.655	2.429.869	95.398.004	2.217.719.065	3.564.199.602	41.279.628
v7.5	350	931.469.850	58.639	800.580	2.060.628	5.329.464	1.261.986.622	927.600.051	3.872.154
v7.6	340	915.661.670	1.800	39.567	2.147.947	3.085.277	1.314.510.004	912.532.952	3.129.372
v7.7	470	1.255.015.150	8.499	162.596	1.253.878	41.884.180	1.253.091.070	1.252.388.408	2.627.942
v8	290	785.230.010	369	16.119	1.765.879	2.868.768	1.203.447.326	783.038.186	2.192.938
v8.1	300	821.937.630	367	17.694	2.076.730	2.936.626	1.215.385.324	819.759.200	2.180.086
v8.2	270	725.439.710	349	17.734	1.742.288	3.120.048	1.130.889.549	722.526.443	2.914.142
v8.3	270	725.644.620	340	657.111	1.798.764	3.065.348	1.130.497.499	723.775.145	1.870.684
v8.4	260	718.872.800	344	7.021.526	1.815.043	468.936	1.070.422.006	713.808.230	5.070.574
v8.5	260	730.616.090	350	17.751	1.815.683	455.632	1.071.800.789	714.974.230	15.644.196
v8.6	260	712.085.010	351	3.416.054	1.814.148	454.304	1.069.933.817	708.925.330	3.162.056
v8.7	260	717.114.950	357	15.863	1.808.583	431.783	1.071.039.959	707.310.885	9.804.884
v9	260	712.035.070	351	3.416.054	1.813.777	455.238	1.069.944.597	708.755.931	3.280.980
v10	120	320.681.060	358	3.416.920	1.581.238	359.985	573.303.002	317.670.176	3.013.888
v11	100	289.020.010	271	3.415.900	1.555.709	359.794	552.358.602	285.803.276	3.218.148
v11.1	100	296.199.860	273	3.415.996	1.554.152	360.598	536.571.561	293.265.048	2.936.862
v11.2	680	1.834.271.590	301	3.416.156	1.548.280	373.646	736.784.335	1.830.587.091	3.687.406
v12	100	283.449.280	284	3.416.197	1.614.741	360.126	553.853.065	280.217.287	3.235.192
v13	100	276.029.240	289	3.416.261	1.504.346	360.429	537.868.968	273.025.620	3.005.446
v14	100	263.174.890	290	3.416.293	1.502.030	362.193	545.477.489	259.987.565	3.188.864

Dropped Optimizations

Mortality values in switch instead of double**: slowdown (v3.1)
Mortality values: merge into double* instead of double**. Increases L2-misses, slight decrease in total cycles (v3.2)
Packing of mortality-values as int / unsigned short (v4.1): performance drop
Packing of mortality-values as float (v4.2): gives diverging results
Replacment of 'pow' by optimized version for integral exponent: gives diverging results
Transfer-Driven Loop Unrolling for barwert (v7.1): performance drop
Loop unrolling by 4 for barwert (v7.2): performance drop
Specialized functions for barwert (for each n), complete unrolling (v7.3): performance drop
Specialized functions for barwert (for each gender, age, n combination), complete unrolling (v7.4): more performance drop, out of mem when compiling with -O3
Specialized functions for barwert (for each endage), complete unrolling, goto with labels (v7.5): performance drop but quite ok
Specialized functions for barwert (for each age), complete unrolling, goto with labels (v7.6): performance drop but quite ok
Specialized functions for barwert (for each gender), complete unrolling, goto with labels (v7.7): performance drop but quite ok
More precomputation: precomputing qx results in slowdown (v8.1)
Precomputation of barwert values for addrisk=0, load from binary file (v8.2)
Precomputation of barwert values for addrisk=0, with big static initializer (v8.3)
Precomputation of doit values for addrisk=0, load from binary file (v8.4)
Precomputation of doit values for addrisk=0, with big static initializer (v8.5)
Packing of precomputation of doit values for addrisk=0, load from binary file (v8.7)
Use of double* instead of double[i] for qx and vn (v11.1)
Use profiling information for gcc. Depending on version of the program, this results in speedup or slowdown.
SIMD via builtin instructions (v11.2). Apperently GCC already produces very good SIMD code in our case.