Re: [Help-glpk] Multithreading/parallelization

[glpk xypron]

Hello Harley,

GLPK not being threadsafe is hindering integration into other tools as well as 
reducing solution speed for MIP problems.

The issue has been recurring for many years, and obviously is an issue for 
enough users to deserve being fixed.

In your mail you indicated some necessary work steps. I see the following 
additional work:

Currently GLPK has one environment structure which holds all memory references 
and which is destroyed in case of an error. To make GLPK thread safe it is 
necessary to have separate environment structures for each instance of a the 
GLPK problem object (glp_prob). This has implications on several API functions, 
e.g. glp_free_env, glp_error_hook, glp_malloc. Furthermore all functions 
calling xerror or xassert will be affected.

The effort needed is considerable and hence I appreciate your idea to develop a 
solution in a community working environment. Before starting I would be  
interested to hear about Andrew's vision for GLPK.

Best regards

Heinrich Schuchardt


-------- Original-Nachricht --------
> Datum: Sat, 15 Dec 2012 12:45:14 +1100
> Von: Harley Mackenzie <address@hidden>
> An: address@hidden
> Betreff: Re: [Help-glpk] Multithreading/parallelization

> Hi Reginald
> 
> I was actually going through the same process of looking at the previous
> posts about developing a multi-threaded implementation of GLPK and was
> about to make a proposal for discussion about the future development of
> a multi-threaded version of GLPK.
> 
> From my investigation the two main libraries for the implementation of
> multi-threaded support for GLPK are the pthread library for linux
> systems and the pthread library for Windows that has been released under
> LPGL and is therefore compatible with the license of GLPK and could be
> included as part of the source with the appropriate inclusion of the
> license.
> 
> Thinking about a possible development path I would suggest a multi-stage
> approach so as to maintain compatibility with the existing version. The
> thinking is that the multi-threaded version would be an option during
> the build process until it was in a stable enough form that it could
> possibly become the default.
> 
> The development steps could be:
> 
>   1. Modify the make and autotools files to support the option of
>   multi-threaded compilation of GLPK with the appropriate linkage of the
>   correct pthread library for that platform with an option to activate
>   these features.
> 
>   2. Change the main non-reentrant data structures and dynamic memory
>   allocation routines with conditional compilation options so that
>   single-threaded compilation is un-affected.  
> 
>   3. Start the implementation of the multi-threaded versions of the MIP
>   branch and bound algorithms as I believe that these routines would be
>   the easiest to implement multi-threaded versions with the greatest
>   benefit with the most straight forward implementation. Again these
>   would all be conditionally compiled with the single or multi-threaded
>   compilation option.
> 
>   4. Implement multi-threaded implementation of the other solution
>   techniques where appropriate and can be feasibly implemented.
> 
> I am not an expert in multi-threaded C development or LP development but
> I am a very experienced programmer and have done a lot of C/C++ work in
> the past and developed multi-threaded applications in other languages. 
> 
> In terms of project management of the proposed development, it is
> important to understand that Andrew Makhorin is responsible for the
> development of GLPK and is, I believe, the only person with commit
> rights for the GLPK code. There hasnt been a new version of GLPK for
> some time and I dont know if Andrew has developments in the works that
> havent yet been released or whether he has any interest in the
> multi-threaded development of GLPK.
> 
> I certainly would like to do this within the existing project management
> of GLPK, but a possible way of coordinating the development of this
> relatively major change to the GLPK code would be to temporarily fork
> the project and host on GitHub where multiple participants could
> contribute to the project with a view to merging the changes back into
> the main GLPK source code at a later time. The GLPK wikibooks could be
> used for the documentation of the code and implementation with maybe a
> dedicated forum to discuss code design and implementation issues for
> this major task.
> 
> I am NOT suggesting a permanent forking of the code, just a temporary
> fork to facilitate community development of this major change to the
> GLPK code, with a view to merging back into the main GLPK code trunk at
> a later time.
> 
> I put this proposed plan up for discussion and would be interested to
> hear from members of the GLPK community who would like to participate,
> have different ideas about the management of the project or other
> comments.
> 
> Harley Mackenzie
>