Why not use mutiple CPUs

[fromturkey]

Hello,
I am using FET for a long time nad thanks to everybody who contributed to the software.
But I think the program should be able to use multiple CPUs/cores. Especially when trying to generate difficult timetables it takes a lot of time processing. If the program could use multiple CPUs, it would take much more shorter.
Is it possible with the current algorithm?
Thanks.

[Liviu Lalescu]

Thanks for the appreciation!

Unfortunately, I cannot think of how to adapt the FET algorithm to multiple cores. But I'll add your suggestion in the TODO (it was suggested also previously, but I forgot to add it).

[Volker Dirr]

Scheduling the activities is pretty random. So you already know that difficult timetables sometimes need hours, but sometimes are also solved in a few minutes.
So if you have a multicore CPU, you can currently open as many FET programms as you have cores. (Don't forget to use other file names for the dataset. Don't open FET more times then you have cores, because in that case it will slow down generating.)

[fromturkey]

Thank you for quick replies.

I hope Liviu could find a way of using multithreading for the algorithm.

And Volker, thank you for your suggestion but I think your solution doesn't fit my problem. Because when I run multiple instances of the program and run the algorithm on their own, each of the instance will try to solve the problem on its own(with different seeds). But I need cooperation between these instances. So the as I mentioned before, the algorithm should be able to run in parallel(perhaps not the whole algotihm but a crutial/high cpu using part of it) to achieve what I want.

Thanks again. I will be following the TODO.

[Volker Dirr]

If your problem is "generating a timetable with a specific seed", then you are right.
If your problem is "generating a timetable with a random seed as fast as possible", then you are wrong.

Of course generating a single timetable with multicore sound much better, but there is a technical problem at the moment. It won't scale with the number of cores.
I already thought and tried myself about using multicore, but sadly there are a few problems:
- you can't parallelize all parts of the algorithm.
So even if you are a very good coder, if you have 2 cores it won't be 2 times faster. You can be happy if 90% of the source is parallelizeable. So you will get max factor 1,9.

Second problem is that most parts of the algorithm need to break as soon as a result was found. So the cores/parts are not totally independent. That mean they always need to check results from the other core. That will decrease again the factor. So if you have luck you will maybe have max factor 1,8.

Third problem:
- You need time to prepare the tasks. Sadly it look like there are too many tasks, it will decrease the factor down under 1. So slower then 1 single core, even several cores are calculating :-(
You can try to solve this by coding bigger tasks. In that case it won't decrease the factor so much. Sadly it will have an other big disadvantage: The same random seed will fit into different results :-( so in fact it won't be better then starting FET several times.

So don't expect results in near future, because it is a very difficult to do that. You can't just simply parallelize all loops. I tried that some years ago. Because of the problems i wrote above, using more cores was much slower then just using the single core :-(

BTW: It is already in the TODO some years now (TODO number 14)

[Liviu Lalescu]

No, Volker, TODO #14 is for multiple timetables, which would be a possible task (but it is a bit complicated, of course). fromturkey asks single generation on multiple cores, which is maybe impossible - anyway, seems very difficult to me on the current algorithm.

The idea from TODO #14 is simple, just start n_cores threads, each with its own memory, and generate for each one starting from a different seed. But the realization is a bit more complicated than the idea, because we did not think of this from the beginning of the FET project.

[Volker Dirr]

Yes, we wrote that, because i found the problems above. So that TODO will result into getting faster timetables then generating a single one with multi cores.

[TaughtWare]

So that TODO will result into getting faster timetables then generating a single one with multi cores.

Yes, I would welcome that feature. I would like to see FET make use of multiple processor cores. When generating (let's say) a hundred timetables, each core can generate a separate timetable. Hopefully this will not affect the stability of the software.

[Liviu Lalescu]

You are right. Unfortunately, this is not very easy to make. It is in the TODO, but I don't know if and when I'll do it.

Meanwhile, you could start n_cores FET instances, ensure that each one has a different random seed, and generate multiple on each one.