Re: [Help-glpk] Multithreading/parallelization

[Harley Mackenzie]

Thanks for the comments.

Your point is very true about the environment structures as my item 2
was meant to cover all of the data structures. However, I hadn't
realised that this step was a lot larger than I had anticipated and
there many dependent routines that also needed to be changed. I have
only been basing my initial assessment on what needed to be done on the
many discussions over the past few years. I havent engaged in any
detailed assessment of the code yet.

Is it necessary to have multiple structures or could a single
environment structure be used with controlled access to the single
structure through the use of mutexes when accessed from multiple
threads? I may be missing something fundamental here.

Also, I certainly definitely agree that for the code to move forward, we
do need to do this work.

I shall gather any further comments and put together a more detailed
work plan. 

Harley

On Sat, Dec 15, 2012, at 17:31, glpk xypron wrote:
> 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
> > 


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

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