concurrent computation of a function

parallelization

asked 2021-10-26 01:13:57 +0200

5711 ●5 ●37 ●122

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.

edit retag flag offensive close merge delete

add a comment

3 Answers

Sort by » oldest newest most voted

answered 2021-10-27 14:09:21 +0200

David Coudert
726 ●11 ●18 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')

edit flag offensive delete 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 ( 2021-10-27 14:41:33 +0200 )edit

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

Max Alekseyev ( 2021-10-27 16:04:33 +0200 )edit

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 ( 2021-10-28 09:38:31 +0200 )edit

add a comment

answered 2021-10-27 00:42:15 +0200

Max Alekseyev

5711 ●5 ●37 ●122

updated 2021-10-27 16:21:46 +0200

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.

edit flag offensive delete link

add a comment

-1

answered 2021-10-26 09:07:41 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

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

edit flag offensive delete 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 ( 2021-10-26 12:57:26 +0200 )edit

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 ( 2021-10-28 19:03:48 +0200 )edit

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 ( 2021-10-28 19:38:33 +0200 )edit

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

tmonteil ( 2021-10-28 21:45:54 +0200 )edit

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 edit

3 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

concurrent computation of a function