Sort resource access schedule for multiple threads so the number of writing conflicts gets minimized

Question

Scenario:

Given a set of resources R:

Given a set of threads T, which will run in parallel:

Each thread needs to access a list of n resources. Each list is a sample of R, meaning that each resource is unique within each list:

But since the access lists are sampled randomly, there can be conflicts:

The random resource lists will be initialized once in the beginning. After that, each thread will do an atomicAdd operation on each resource in the list, subsequently. The access order of the resources in each list is irrelevant.

Question:

Is there an algorithm which sorts the scheduling lists, so that the number of writing conflicts gets minimized? So the final result would look like this:

My insights so far:

• The random sampling is important for the context of the algorithm, so it is not an option to initialize the lists in another way (only their order may be altered).
• The overall schedule can be viewed as a matrix S with |T| rows and n columns, where each entry is an element of R.
• If |T| <= |R|, a solution without any conflicts is possible.
• If |T| == |R|, the columns of an optimized scheduling matrix S are permutations of R.
• If |T| > |R|, the average number of conccurrent accesses in an optimized scheduling matrix should be |T| / |R|

Possible approaches:

I am looking for an analytical solution for this problem. Could it be np-complete? If this is the case, I am thinking about designing a genetic algorithm to solve this problem.

Edit 1: Added diagrams.

Answer 1

I think the question is asking "can we sort the lists to reduce the conflicts."

I think an optimum solution is NP complete, but I would look for the number of occurances in the set for each resource.

Step 1

The most commonly used resource is the hardest one to schedule. Thus I would place in each of the threads this resource in position 1, 2, 3, 4, ... Until conflict occurs (which may be unavoidable) e.g. 1,2,3,4,..., n, 1, 2,... .

These are the "big stones". These should be placed first.

Step 2

The next most commonly used resource should then be tried. This should identify which slots (1 => n) have been used recently and search through that list for a slice which is both unallocated and not recently used.

Whichever slot is chosen, it moves to the top of the recently used queue to be avoided for a while.

This favours distributing the resource, but allows duplicates. These duplicates will become recently used, and not favoured again for scheduling until no valid choices are available.

Finally

Step 2 is repeated for each of the resources in order of their occurances.