Threads possibility

[AboZeid]

Is there a possibility to work on threads while generating a timetable?
I think it may reduce time wasting .

[Liviu Lalescu]

There are 3 variants:

1) If you have 4 cores, you could start 4 FET programs (take care to start them at least one second apart, so that the random seed is different - check the random seed at start of generation to be different in each one). Then, generate four timetables in parallel, in each FET. They'll occupy all the cores.

2) There would be a variant to make FET generate multiple in parallel, each timetable on one core. This is a variant of the above, not very difficult to implement.

3) The best: to make FET generate a single timetable on multiple cores. I have an idea of how to do that and I can help another person with advice. I am not sure if the speed gain would be significant, but it may be for 2-4-8 cores - about 2-4-8 times faster.

The idea I have in mind is to evaluate each slot in which to put a new activity, in parallel, on separate cores. So, this idea may be useful for maximum n_hours_per_week cores.

It seems complicated.

[yannick guenet]

Hi,

I was looking on the code and it looks like you code the generate function to be threaded. I would like to be able use my 6 cores (12 threads) . what can I do ? I don't want to run 12 threads of generate but really 12 thread to speed up the generation.

Thanks

[Liviu Lalescu]

Hi,

I was looking on the code and it looks like you code the generate function to be threaded. I would like to be able use my 6 cores (12 threads) . what can I do ? I don't want to run 12 threads of generate but really 12 thread to speed up the generation.

Thanks

My generate function takes place on only one thread (I use only 2 threads, one for generation and the other one for the interface).

What you suggest is really complicated and may be left as an assignment for a courageous person.

One must think about the random number generator when making multi-threaded generation. Because even if you start with the same random seed in two generations, you may end up with different results. This is only one problem.

[yannick guenet]

I can spend time on this. Can you help me for this. Which part of the code on generate can be threaded ? did you take a look on tablix project , they use PVM and use each node (thread) for making new generation of population.

[Liviu Lalescu]

I can spend time on this. Can you help me for this. Which part of the code on generate can be threaded ?

Volker is also interested in this.

I think that maybe evaluation of each slot can be done on a separate thread (line 3191 and below in generate.cpp of official FET-5.16.0). So maximum n_slots_per_week parallelization. But any idea should be debated.

did you take a look on tablix project , they use PVM and use each node (thread) for making new generation of population.

FET uses no longer a genetic algorithm, which is bad. It uses an algorithm which is more complicated to parallelize.

[Volker Dirr]

Yes, Liviu is right. One idea is to parallelise linie 3191-8434.

The first step is to check all varibles (especialy line 1-190) if they are only readable needed or if it is also need to write to them.
Most (all?) variables that are prepared in the generation_pre.cpp are only readable needed.
So it shouldn't be difficult to care about that.
But many variables from the generation.cpp are also needed writeable. So each thread need it's own copy of that variables.
Also the random number generation is a problem. (You need to give each thread a "known" random number. The results must be independed from the number of threads.)
You must also be carefull of several (inline) functions in that code (for example rooms/space constraints). Check also that variables.
After you checked all variables it is needed to care about placeing them good in the memory.
For example if just do an array or list with the variables for the random number geneartion, then your speedup will be not high (it might even happen that it is slower then with single core!), because there will be a lot of "false sharing" slowdowns. So you must care about placing all variables good in the momory. (Care about cachlines of the cpu! Place all (writeable) variables for one thread continously in the memory!).