Multi-threaded search for a large solution space

Question

I need to look for a large space of solutions (listing all Latin squares of a certain order) for the right solutions. I am trying multithreading (boost :: thread). I decomposed the solution space into subspaces and explores a specific subspace within a single thread. This works well as there are no dependencies between threads.

But now I want to keep all the valid solutions in the list. Would it be better to use one list (shared data) and surround it with a mutex, or should I create lists (local data) for each thread and join the lists after the threads are finished?

There may be millions of valid solutions for higher orders. Thus, the process will include either many locks / unlocks of the mutexes, or it will include a large amount of memory for each thread.

Thanks Daniel Dekkers

Answer 1

Based on your explanations, you want local lists to be merged at the end of your algorithm. If each thread finds a lot of solutions, using mutexes will significantly slow down your calculations. From what I understand from your context, you should think that memory is pretty cheap today, but it's hard to understand without knowing the size of the solution.

There may also be list merging algorithms that are minimal in memory space (i.e. by copying a small amount of data at a time), which can solve problems with memory size.

Thus, there are hybrid solutions to your problem. For example, you can create a shared container and split it to assign partitions for each stream, interlaced or block. This will allow you to remove the mutex for each access, but this will require a complex container growth mechanism (since it does not seem possible to know how many decisions you will have in advance).