Parallelization of a quadratic algorithm

Question

Let's say I have a vector (array, list, whatever...) V of N elements, let's say V₀ to V_(N-1). For each element V_i, a function f(V_i,V_j) needs to be computed for every index j (including the case i=j). The function is symmetric so that once f(V_i, V_j) is computed, there is no need to recompute f(V_j,V_i). Then we have N(N+1)/2 total evaluations of the function, making this a O(N²) algorithm. Let's assume the time it takes to compute f is relatively long but consistent.

Now, I want to parallelize the execution of the algorithm. I need to determine a schedule for (some number M of) worker threads so that two threads do not use the same part of memory (i.e. the same element) at the same time. For example, f(V₁,V₂) could be evaluated parallel to f(V₃,V₄), but not parallel to f(V₂,V₃). The workflow is divided into steps such that for each step, every worker thread performs one evaluation of f. The threads are then synchronized, after which they proceed to the next step and so on.

The question is, how do I determine (preferably optimally) the schedule for each thread as a series of index pairs (i,j) so that the complete problem is solved (i.e. each index pair visited exactly once, considering the symmetry)? While a direct answer would of course be nice, I'd also appreciate a pointer to an algorithm or even to relevant websites/literature.

Answer 1

This reminds me of a common sports scheduling problem: In a league with N teams, arrange N-1 gamedays, so that every team has one game per day and plays every other team once.

Playing chess, there is a quite illustrative solution to this problem. Arrange all boards side by side on a long table. One player always remains at the same chair. The other players rotate around the table in the same direction skipping that player.