Why Multi Threading slower than sequential?

Hi every one.
I have a problem with multi threading. When I run an example (70+ costumers, 4000 iterations, regret Insertion …) with 9 Threads, it takes more times (30+ seconds ), while 19 seconds maximum using 1 thread.
I dont know where the problem comes from, supposing that everything is coded right!! I suspect window 10.
Thank you for your help.

Hi @anasstaha19,

How many routes do you have in your problem? If only one, then you probably won’t benefit from multi threading. Please refer to @stefan’s comment in this post, which is also quoted as below:

95 percent of the computation time is spent on re-inserting jobs, i.e. finding the best insertion position. Basically, jsprit goes through every route to find the best insertion position of a job. With the concurrency mode you can only distribute the task to find the best position in an entire routes (you cannot split a route into subroutes). Thus, if you only have one route, only one thread is used no matter how many you configured. If you have 20 routes and configured 4 threads, you can distribute 5 to each thread. Note, that when you use BestInsertion, your problem must be relatively large to gain from concurrent calc (otherwise performance gets worse due to the overhead of distributing). If you use RegretInsertion, I think that you can always gain. But you need to analyse it.

Best regards,
He

Hi @jie31best
Thank you for your answer

I did a test, with 50 customers 5 routes, the concurrent mode is not efficient. I also used an instance with 524 customers, 50 routes, the concurrent mode shows a little improvement, It only save 25 seconds approximately .
I am wondering if this improvement is considered huge for a concurrent mode !

Best regards,
Anass

Hi,

Multiple threads always come with overhead, and if you use many threads,
it might be that the overhead is bigger than the actual savings. As a
rule of thumb, I would not use more threads than you have cores for
these kind of computation intensive tasks.

Best,
Stefan

Hi @stefan
I use this to get nu of threads
int threads = Runtime.getRuntime().availableProcessors();
if only some one can confirm that we can get more improvement in time calculation using concurrent mode

Best, Anass.

As a future development, it would probably be beneficial to have an option to run multiple ruin and recreates in parallel. So each thread runs its own ruin and recreate and we just synchronise the master / best / current solution between threads. You would then get a speed-up in-proportion to the number of threads (assuming you have a real CPU available for each thread), irrespective of the number of routes.

You would then get a speed-up in-proportion to the number of threads

If the necessary (?) synchronization does not hurt too much :slight_smile: … but it would be definitely interesting how one could further/better parallelize the algorithm.

For anything other than toy problems the synchronisation costs should be tiny - as they’ll be so much quicker than a single ruin and recreate iteration. You probably wouldn’t want to wait for each thread to finish its ruin and recreate iteration however, before starting the next iteration - you’d just let them go independently. So the master solution should be controlled by a separate thread, the ruin and recreate threads read an immutable copy of shared the master solution (held as a volatile variable and replaced atomically) at the start of each ruin and recreate iteration and post a new solution to some sort of master new-solution-queue at the end of their iteration. The thread controlling the master solution then pops solutions off this queue and accepts/rejects them according to the simulated annealing-type acceptance criteria. Only the access to the new-solution-queue needs to be synchronised, nothing else.

Powered by Discourse