[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] GLPK re-endrant

From: François Galea
Subject: Re: [Help-glpk] GLPK re-endrant
Date: Sat, 04 Jul 2009 11:00:55 +0200
User-agent: Mozilla-Thunderbird (X11/20090103)

ILOG describes that many MIPs can be solved >= 1.7 times
faster using multiple threads and shared memory.

Probably if a machine has more than one cpu. However, it is a brute
force approach. (It would help if the machine has 2^n processors, where
n is the number of binary variables :) Try to solve gesa2 or gesa3
from miplib without and with mir cuts. That what's I mean.

This is not only brute force. Parallel branch-and-bound can be seen as multiple searches in the whole B&B domain. With chance, one of the searches may find a good solution faster than sequential search on a single core, since the search order may be different. Multiplying the number of search threads not only enables the use of several cores, but also raises the chance for faster finding a near-optimum solution, quickly reducing the size of the search space, and helping find the optimum faster.

In case of column generation (like in the CLSP) multiple
subproblems could be solved at the same time on separate

My understanding is that a major group of functions that
has a problem with threading is the memory allocation
(xfree, ...).

Yes, because different threads would use the same memory pool
implemented by xmalloc/xfree. This might be resolved by storing
the 'tls' pointer (defined in glplib02.c) in the thread local

The Bob++ parallel algorithm framework I am contributing to has a parallel B&B which can be used for MIP solving. It can make use of GLPK for solving LP bounds in the different B&B nodes. For now we used a patched version of GLPK where xmalloc/xfree simply use the C malloc/free calls. Recent versions of Glibc make use of very effective thread-friendly memory allocators, which drastically reduce overhead due to multithreading, using techniques such as caching, making malloc/free perfect for multithreading, and removing all needs for TLS-like memory allocation.

However, our patched version may still be broken, since we hadn't noticed the strtok and strerror issue.


François Galea

reply via email to

[Prev in Thread] Current Thread [Next in Thread]