[Nauty] Parallelizing generation

[Tomas Peitl]

Hi everyone,

I've got a question about parallelization in generators such as genbg 
(I'm using a modified version of genbg provided by Brendan some time 
ago, but that shouldn't make a difference I hope).

I noticed that the speedup from parallelization using the res/mod 
feature pretty much plateaus at around 5-6 cores, and it doesn't really 
make too much sense to use more than that. Is this more or less correct, 
or am I missing something? To be fair, the speedup does grow a bit even 
beyond 6 cores (depends on the particular case I guess), but the 
dependence on the number of jobs looks more logarithmic than linear 
(didn't really try to fit a curve). So if you have more than one 
generation task, it makes sense to use fewer cores per task, and instead 
run several tasks in parallel.

I have some aggressive custom pruning, but on the other hand each job 
generates roughly the same number of results, and the running times are 
also more or less uniformly distributed, so the splitting of the search 
space seems OK.

How does the res/mod feature work? Does each job still have to generate 
everything, just with the advantage of quickly skipping over graphs that 
belong to other jobs? Or can it run in "O(N/j)"?

Many thanks,
Tomas