Need a book recommentation for converting a sequential program into a parallel

Question

Suppose I have a sequential program of biological, physical, or chemical simulation.

I need a step-by-step algorithm for translating that sequential program into a parallel program.

Can you recommend a book for this?

Answer 1

No such book exists.

There are plenty of introductions to parallel programming out there, but there is no general advice for turning a sequential program into a parallel program, because it is impossible. If it were possible, compilers would do it.

Having said that, there are a couple of general approaches that may help for a problem like yours:

• Many physical simulators have a core mathematical "solver", such as an algebraic multigrid solver, where most of the time is spent. Such solvers are also often iterative, so they converge on the desired solution. Concentrating on parallelising that may be productive, keeping the main simulation loop sequential.
• Physical simulations tend to not have "action at a distance", so the problem domain can be conceptually split into regions which can then be distributed to different CPUs. The CPUs only have to communicate with each other about what happens at the boundaries. This is a common approach in very large scale simulations, such as weather forecasting and oceanographic simulation.

• rus9384: IMO compilers could do quite a lot to parallelize programs. Construct a flow digraph (forming a partial order) and attempt to put operations (represented as vertices) independent of each other on parallel paths. Now, of course that would require tracking whether any function call affects some global variables, including external function calls (e.g. dlls) which is probably the main bottleneck of creating such a compiler.
• Pseudonym: @rus9384 Well yes, but that's typically to handle instruction-level parallelism and auto-vectorisation. Multiprocessing optimisation typically requires programmer annotations, e.g. OpenMP.