Optimal generation (sustained maximum attainable parallelism) of pairings for SVD

[alexbarcelo]

This expands on the following comment (#302)

• Uses the simplest pairings for columns, which might not be the best for parallelism (other pairings should be explored)

I provide a very crude proof-of-concept implementation of an "optimal" pairing generation in this gist:

https://gist.github.com/alexbarcelo/940e34bea1a788383086b494c5ce1bde

This gist contains the main algorithm (scombinations) as well as a quick and dirty testing harness (test_combinations).

As of it is right now, it works for $n = 2^k$. It should be easy to adapt (just do everything the same but dropping invalid pairs).

About optimality criteria

If there are n columns, the maximum parallellism that can be attained in the SVD algorithm is equal to n/2 (because each pair contains two columns, and each column is INOUT, thus we cannot schedule more than n/2 simultaneous tasks). The total number of pairs (aka total number of tasks aka len(combinations(range(n), 2))) is (n-1)*n/2. The algorithm I provide gives n-1 "steps", each step containing n/2 pairs, which is the optimal following these criteria.

Note that my algorithm gives the pairings structured in "steps". That is done for my sanity and for ease of validation. The final result can be flattened into a list of pairs; using that flat list and using it to schedule tasks should hopefully make everything work (according to my assumptions and understanding of the algorithm).

In order to use scombinations as a drop-in replacement of the itertools.combinations a flattening postprocess needs to be applied (which sounds scary but it's just sum(steps, list())).

[alexbarcelo]

Could somebody remove the bug label and should I recommend adding both algorithm related and enhancement ones?