If you're interested in high-performance computing, this talk is for you! This talk aims to revolutionise how you think about the performance of associative operations.
Associative iteration is a powerful technique that allows for efficient computation of associative operations (addition, multiplication, and other monoids) in `O(log(N))` time as opposed to `O(N)` time.
The name for this technique was coined by my collaborators, and it is my goal to share their insights about it.
Associative Iteration is an absurdly general technique that leverages the properties of associativity that when combined with parallelism can achieve outstanding performance with very little effort.
We define Associative Iteration (unrelated to "iterators" as you might expect) as the repeated application of some associative operation with respect to a "count", some explicit number of operations. This technique applies generally to all monoids, so whether you're concatenating string, multiplying matrices, or simply adding integers, this talk will be useful to you!
Furthermore any "divide and conquer" algorithm that can be represented using this method should achieve near optimal or optimal performance.
This talk will specifically introduce a templated function that allows you to leverage the power of Associative Iteration in a way specific to parallelism.