concurrent computation of a function

parallelization

6922 ●9 ●52 ●161

Suppose I have two functions f1(x) and f2(x) that compute the same entity. Depending on the value of x one may be much faster than the other, or vice versa. It's apriori unknown which of the two functions will be faster for a given x.

So, I'd like like to run the two functions on the given x concurrently in parallel, and as soon as one produces an answer, I'd like to terminate the other function as well and return that answer. Please help me to design such a parallelized function concurrent_run(f1,f2,x) in Sage.

add a comment

3 Answers

Sort by » oldest newest most voted

answered 3 years ago

Max Alekseyev

6922 ●9 ●52 ●161

updated 3 years ago

After some googling and reading documentation, I have found that this can be done via standard Python's module multiprocessing as explained below.

First, we need our functions to store their results in a given queue, which can be done via a wrapper:

def func_wrapper(queue, func, x):
    queue.put( func(x) )

Then the concurrent run of f1 and f2 on x can be implemented as follows:

def concurrent_run(f1,f2,x):
    q = multiprocessing.Queue()
    p1 = multiprocessing.Process(target=func_wrapper, args=(q,f1,x))
    p2 = multiprocessing.Process(target=func_wrapper, args=(q,f2,x))

    p1.start()
    p2.start()

    res = q.get()

    p1.terminate()
    p2.terminate()

    return res

PS. Perhaps, we can simply use return q.get() without explicitly calling .terminate() methods and letting the corresponding Process classes to take care of a clean-up. On the other hand, for unresponsive processes we can use .kill() instead of .terminate() to force their shutdown.

link

add a comment

answered 3 years ago

David Coudert
766 ●12 ●20 http://www-sop.inria.f...

A simple solution proposed here using the @parallel decorator. It can easily be extended to other cases.

def use_all(f, algorithms):
    @parallel(len(algorithms), verbose=False)
    def h(alg):
        return f(algorithm=alg)
    for input, output in h(algorithms):
        return output, input[0][0]

and then

sage: set_random_seed(0)
sage: g = graphs.RandomGNP(20, .5)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.61 ms, sys: 15.3 ms, total: 17.9 ms
Wall time: 63.4 ms
(6, 'DLX')
sage: g = graphs.RandomGNP(50, .3)
sage: %time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
CPU times: user 2.03 ms, sys: 11.8 ms, total: 13.8 ms
Wall time: 124 ms
(6, 'MILP')

link

Comments

What's happening with the running threads upon return from the caller (use_all)? I suspect they may still be running in background until their normal completion, which would be a waste of resources.

Max Alekseyev ( 3 years ago )

I've tested this approach and it seems to work fine (ie. terminates the running threads upon return from the caller).

Max Alekseyev ( 3 years ago )

It might work due to garbage collection killing the other spawned processes. I think @parallel uses fork rather than threads to avoid problems with Python's GIL. For what it's worth, I actually wrote the @parallel decorator in the first place, but can barely remember how it works. I just remember trying to find a simple-to-use "notation" at a Sage Days that would make it easy to do things in parallel in Sage, and @parallel seemed easy to sell :-).

William Stein2 ( 3 years ago )

add a comment

-1

answered 3 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

You can have a look at https://doc.sagemath.org/html/en/refe...

link

Comments

I do not see there how to implement what I need. E.g. how to interrupt all parallelism as soon as one thread produced a result?

Max Alekseyev ( 3 years ago )

Apparently, @david-coudert was able to derive a simple solution from the @parallel decorator that was pointed by this link (the other process get interrupted once the first returns a result). Did you ever try ?

tmonteil ( 3 years ago )

Yes, and I've accepted his solution. I've also added my own solution (based on multiprocessing module) above. Your link alone was not sufficient as the tricky part (terminating processes) is not described there.

Max Alekseyev ( 3 years ago )

It is not described in @david-coudert either, @parallel just works.

tmonteil ( 3 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

concurrent computation of a function

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

concurrent computation of a function savecancel

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

concurrent computation of a function