Final project done for the Parallel and Distributed Systems: paradigms and models (2019).
Implementation in C++ of the "Divide and Conquer" paradigm using only the standard libraries. The implemented code gives the possibility to execute in parallel, with a custom number of threads, any problem that can be solved with this paradigm. The problem must be defined by four basic functions that model the problem and the resolution steps:
- std::vector Divide(inType) : Divides the problem into two or more simpler sub-problems
- bool BaseCaseTest(inType) : Checks if the input problem is the base case
- outType BaseCaseSolution(inType) : Solves the base problem
- outType ConquerFunc(std::vector&) : Merges two solutions
Thanks to the use of templates, functions can handle any type in both input and output (must be consistent between functions).
The implemented solution although very general makes a basic assumption that the aggregation function respects the commutative property. This can be a problem when used when the order of aggregation is important.
- If you want to test the code make sure you have enough physical cores
- otherwise the high number of threads will only produce hoverheads.