Re: [Help-glpk] Multithreading/parallelization

[Reginald Beardsley]

I'm interested in speeding up the solution of of a single problem on a 
multicore machine.  Multiple problems are better handled at the shell and OS 
level. I can already trivially do multiple problems via a shell script (yes, I 
owe everyone an example on the wiki). So there's really no need for a large 
number of threads.

Whether multiple threads per core are useful remains to be determined and is 
largely dependent upon the processor model.  The new Sparc processors may well 
be able to usefully run 8-16 threads per core, but I'm sure other processors 
can't do that.

>From a pure throughput perspective, running multiple problems, one per core, 
>is probably optimal in which case no changes are needed.  However, when one 
>wants to solve a single problem quickly there is the potential to get a 4-8x 
>speedup by multithreading the appropriate parts of the code.  That's probably 
>worth doing if the code changes aren't too complex. As I learned from my 
>CWP/SU experience, how you solve the problem can have a huge (>100x) effect on 
>how much effort is required.  So the first solution to come to mind may not be 
>the right solution.

After a quick review of the glpk manual, it's pretty clear that very little of 
the code would be affected by multithreading aimed at improving single problem 
performance. The general rule of thumb is that 10% of the code accounts for 90% 
of the run time.  In this case, I suspect it's more like 1%.  In some cases, 
the code may not even be part of glpk.

I'd be grateful if someone could point me to a good set of example problems 
that exercise the various solvers via glpsol.  I'm far too ignorant of linear 
programming and OR to be able to construct them myself.  The examples in the 
distribution that I've tried run so quickly as to not be very useful for 
profiling.  I'm going to start w/ those since I already have them, but bigger 
problems are important.

Ideally I'd like examples that take at least 2-5 minutes to run on a 3.2 GHz 
Xeon.  That should let me get a good picture of what routines I need to study 
closely.  Longer is OK so long as they don't take more than a few hours.  I'm 
quite content to run things overnight for a few days.

Have Fun!
Reg