Ask Your Question
1

Parallel computation for different functions

asked 2020-02-21 01:37:16 -0500

dzhy444 gravatar image

For a single function with a list of inputs, the @parallel decoration can be used to do parallel computation. I am wandering whether it is possible to do parallel computation for different functions.

A simple is example is to calculate the difference f-g of two independent functions f and g. How can I ask SageMath to simultaneously compute the values of f and g, and then calculate the difference?

My time measurements suggest that when calculating the difference f-g, SageMath actually calculates f and g one after another, and then take the difference.

I can think of a naive approach using the @parallel decoration. I can create a function whose input variable is the name of the functions I want to compute simultaneously. Then I use a list of function names as input to get a generator of outputs. This may work if the final result doesn't depend on the order of the outputs, but does not work if the order matters, for example when taking the difference.

In general, suppose I have a flow chart for the computation, in other words, I already know which jobs can be parallelized and how the information flows to the next stage. Then what is the best way to implement the flow chart?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2020-02-21 14:31:46 -0500

vdelecroix gravatar image

The @parallel decorator is based on the multiprocessing Python library. It is nothing advanced and only allows you to perform embarassingly parallel computations (ie no dependence between each individual computation).

If you want more advanced parallelization, a flow chart is not enough as it does not take into account the cost of a given computation. Let us imagine that you have 2 processors for the following tasks

  • A1, A2, A3 that takes respectively 1min, 1min, 3min
  • B that takes 1min and depends on A1, A2, A3

Then, doing it blindly you will start the computation with A1, A2 simultaneously. They will roughly finish at the same time and then A3 will run alone for 3 min.

Even with the assumption that you can give a rough approximation of the time of each task, the scheduling problem is algorithmically non-trivial (ie unlikely to be solved on large instances). I don't know of any Python implementation of something in that direction.

edit flag offensive delete link more

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: 2020-02-21 01:37:16 -0500

Seen: 63 times

Last updated: Feb 21