# concurrent computation of a function

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 close merge delete

Sort by ยป oldest newest most voted

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')

more

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.

( 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).

( 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 :-).

( 2021-10-28 09:38:31 +0200 )edit

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.

more
more

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?

( 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 ?

( 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.

( 2021-10-28 19:38:33 +0200 )edit

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

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