Re: [Help-glpk] Multithreading/parallelization

[Harley Mackenzie]

Andrew,

Thanks for your comments - you may get another reply as I messed up the
sending of the last reply and have had to rewrite this email.

I do agree that parallelism is a brute force technique but I believe
that new generations of processors will use multiple cores and fast
virtual threads to deliver improved computational performance, given the
current state of technology. Nothing we are suggesting will inhibit the
implementation of any new algorithmic improvements suggested and these
multi-threaded techniques have been used to great effect in the
commercial LP codes. 

I am proposing implementing all three of the below objectives listed in
your email as the requirements do have some common elements and the
current implementation is limiting the potential of the package in many
implementations.

What is the state of the release schedule of GLPK and are there any
changes that are to be released soon?

Regards,

Harley Mackenzie

On Mon, Dec 17, 2012, at 16:49, Andrew Makhorin wrote:
> 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
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk


-- 
-----
  Dr. Harley Mackenzie
  HARD software

  address@hidden
  www.hardsoftware.com
  + 61 3 5222 3435