Problem Statement
Disclaimer: As this problem statement could also be used for other students in the future, I only provide a description of the problem statement and the results we've discovered. The repository for the actual implementation remains private.
Integers can be represented in different bases. For example, the number 12 in base 10 could be written as 2 in base 6. This also works for negative bases. As everyone knows, computers operate in integer base 2.
The goal of the project was to realize a method that allows for optimized arithmetic operations (+, -, *) on a specified integer base by implementing a program with following signature:
/**
* Calls method responsible for the arithmetic operation defined by op
* The result of the operation is returned in @param result[in]
* @param[in] base : [Integer] -> base in which calculations are performed
* @param[in] alph : [String] -> alphabet which specifies the meaning of chars in the base
* @param[in] z1, z2: [String] -> input values given in respective base, specified by alphabet
* @param[in] op : [char] -> operation to be performed ( + / - / * )
* @param[in] result: [String] -> string in which the result of the operation is returned
*/
void arith_op_any_base_V3(int base, const char *alph, const char *z1, const char *z2, char op, char *result)Overview
We realized three implementations:
1.SIMD-Optimized Arithmetic Operations without converting to Binary
2.Non-SIMD-Optimized Arithmetic Operations with converting to Binary before performing arithmetic Operation
3.Non-SIMD-Optimized Arithmetic Operations (simplest version)
The implementations resulted in different performance results. By using SIMD-Optimizations, we were able to increase the performance in comparison to the non-SIMD Version by 120% percent. You can find a graph of the time measurements here:
Technologies
Throughout the project, we made extensive usage of significant technologies. Overall, we used and learned following technologies througout the project:
- Makefiles
- Bash (for testing our implementations)
- C
- Python
Summary
If you would like to take a look at the implementation, please send me an email using contact(at)florianklein.me. Overall, we learned a lot about team work and cooperation throughout this project.