1
edit
Changes
→Description
</pre>
The strange thing is that after these parallelisations The algorithm performed worse. I think this has to do with the granularity of the parallelism, because we aren't solving 1000 by 1000 matrices but a very large amount of 20 by 20 matrices, the parallelism isn't splitting into all that much and some of that may be faster off serial. Where our Our serial solution could solve up to 20 cities, this parallelised version can't solve more a 500 city problem around 10 times faster than 16 without taking minutesthe non-serial version can. Another approach would have been to parallelise the whole nodes instead of the operations in them, but this is a little bit difficult because for each node to exist, the parent needs to have been evaluated already. There would have to be some very complex Node management logic to determine which nodes to spawn and which not to spawn, when to halt evaluation on certain nodes and that sort of thing.
Learn from me and think long and hard about what you want to parallelise in regards of granularity, because in this case parallelising the individual operations in the Node made my algorithm significantly worse. It took a lot of programmer effort and gave me no reward in terms of speed. I did learn a lot about C++ writing this algorithm, so all was not lost.