Index of /anton/lvas/effizienz-abgaben/2019w/g12/effiziente-programme

	Name	Last modified	Size	Description
	Parent Directory		-
	LICENSE	2019-12-21 16:27	34K
	Makefile	2020-01-06 19:01	574
	bench.sh	2020-01-09 14:00	387
	bench_results_opts/	2020-01-09 14:12	-
	doc/	2020-01-09 15:16	-
	original/	2020-01-09 16:03	-
	readme.md	2020-01-09 15:56	2.9K
	src/	2020-01-09 14:03	-
	tools/	2020-01-06 19:01	-

# Effiziente Programme 
By Christoph Hochrainer, Alexander Graf und Anton Oellerer

## Task Description
http://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe19/

## Building
To build the project with all binaries, navigate to the source folder
and call the make command:
```
cd ./src
make
```
to build the standard alpha beta pruning example execute
```
make default
```
to get a profiled (better gcc optimzed) version of ```default```
execute:
```
make comp_profile
```
there is also a hashtable/caching and openmp variant of the project.
This can be build by
```
make comp_table
```
```
make comp_openmp
```
and for an micro optimized oware version
```
make comp_opt_oware
```
To use all optimizations except for the table:
```
make comp_opt_oware
```

## Testing
Tests are carried out by the test generator file in the tools folder.
To check if the current built comp binary is correct execute:
```
make test
```
on the top level of the project. 
This will built the alpha beta search projects if no binary is available, 
generate test cases and compare the output 
of the implementation against the output of the original program.

## Benchmarking
For benchmarking use benchmark.py in tools/.

## Program Structure

### src
Source code of our improved oware program.

### tools
Self written tools for testing. 
The "test generator.py" uses the original binary and
our binary and compares the outputs for asserting correctness.

### original
The original project (with small changes in the Makefile).
This will be used to check the correctness of our program.

## Optimizations

### Alpha Beta Pruning
We extended the Min-Max-Search in comp.c with Alpha-Beta-Pruning.
As pseudo code reference we used the AlphaBeta function under 
the ["Principal-Variation-Suche"](https://de.wikipedia.org/wiki/Alpha-Beta-Suche) section
without the "Principal-Variation" parts.

### Micro optimizations in oware
#### Calculate application in constant time 
The seeding step now is done via a loop from ```0``` to ```no_houses```, where the
augumentation of the seeds for each house is calculated only once.
The capturing step is done in a subsequent loop.

#### Manual loop unrolling
Unrolling all the loops which only had 6 iterations gives compared to the effort
a huge performance boost. This can be seen by using our bench example with the default and
comp_opt_oware.

### Using GCC Profiling 
Making use of ```-fprofile-generate``` and ```-fprofile-use``` to boost performance and improve
the branch prediction.

### OpenMP for Parallel comp
Extend the comp.c file with parallel executed move computations using openmp-for.
It improves the real runtime significantly but costs more
CPU runtime. Test yield that it is better for profiling to use only 1 thread (OMP_NUM_THREADS=1).
To turn openmp off permanently set define USE_OPENMP=0 in comp.h or in compilation step.
Default compilation uses openmp.

### Lookup Table with Zobrist Hashing
TODO