Re: [Help-glpk] Multithreading/parallelization

[Harley Mackenzie]

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

On Sat, Dec 15, 2012, at 6:23, Reginald Beardsley wrote:
> What is the status of multithreading or parallelization support in glpk
> and glpsol in particular?  I've found a good bit of prior discussion, but
> nothing recent.
> 
> Is there intent to do this or a desire not to do it?  I'm gradually
> wandering into solving ever larger problems which will probably put
> considerable pressure on me to speed things up.
> 
> If there is an interest in taking advantage of multicore processors, has
> anyone done any profiling of a representative problem suite to identify
> what routines would benefit most?  I'm pretty familiar w/ what needs to
> be done and have growing incentive to do at least some of the work.
> 
> Reg
> 
> _______________________________________________
> 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