Ask Your Question
4

concurrent computation of a function

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

Max Alekseyev gravatar image

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

3 Answers

Sort by ยป oldest newest most voted
1

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

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 more

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 gravatar imageMax 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 gravatar imageMax Alekseyev ( 2021-10-27 16:04:33 +0200 )edit
3

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

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

Max Alekseyev gravatar image

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 more
-1

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

tmonteil gravatar image
edit flag offensive delete link more

Comments

1

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

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

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

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 328 times

Last updated: Oct 27 '21