Re: [Help-glpk] Multithreading/parallelization

[Andrew Makhorin]

I'd like to note that in this discussion three different aspects not
related to each other are mixed up.

1. Reenterability.

It is a property of the code that allows running several instances of
the same program in parallel using the only copy of that program in the
memory. This property requires the program not to alter its own code
and statically allocated data.

The glpk code is reenterable except two internal routines tls_set_ptr
and tls_get_ptr (see src/glpenv02.c). In a reenterable version of glpk
these two routines should be replaced with platform-specific ones.

2. Thread-safety.

It is a property that allows several threads running in parallel to use
the package resources (i.e. data objects and functions) simultaneously.

The glpk code is not thread-safe, because it use no synchronization
mechanism (like mutexes or semaphores) to prevent different threads to
change the same program object (e.g. glp_prob) at the same time, i.e.
program objects in glpk are non-shared. For example, even if a
reenterable version were used, two threads would be not allowed to
call, say, glp_simplex or glp_intopt for the same problem object. On
the other hand, it is difficult to imagine the situation where such
a feature would be needed.

3. Parallel computations.

It is a technique when some computations are performed in parallel,
as a rule, in a multiprocessor environment. (Please note that parallel
computations assume neither reenterability nor thread-safety.)

The glpk code is serial by design, in particular, because the standard
C language provides no features for parallel programming.

Though parallelization allows reducing the solution time, in my
opinion, it is a brute force approach (at least for problems which glpk
is intended to solve); moreover, since in case of hard mips the solution
time grows exponentially, this approach helps not so much (until you
have 2**n processors, where n is the number of integer variables :). It
seems to me that algorithmic solutions are able to provide much greater
performance.


Andrew Makhorin