Where does the speedup come from?

speedup

With discrete partitioning we change from running a single process to running several processes simultaneously. As we have seen (section Employing discrete partitioning), if we have suitable hardware, there can be good speedups in elapsed time due to parallel running of the processes. However, there are other factors contributing to the speedups obtained.

When working with the complete system the integration step size is a global quantity. The scope of this step is the whole system and the solution for every state variable is advanced through time using this step.

Discrete partitioning works with a collection of processes (a master process and one or more slaves). Each process has its own integration step.

This means that each process can go at its own speed. The sub-system corresponding to one process may not be stiff at all and an Adams step can be used with no Jacobian evaluations. Another sub-system will be very stiff and will be integrated using BDF methods. Yet another may contain differential algebraic equations and the DASSL integrator must be used. This gives enormous flexibility.

Most of the systems likely to benefit from discrete partitioning will have at least part of the system numerically stiff. This means for the complete system a lot of BDF integration steps will be used. This further implies that there will be many Jacobian evaluations. Jacobian evaluations consume a lot of CPU time.

When discrete partitioning is used, instead of one large Jacobian there will be a collection of smaller ones. It will always be faster evaluating the collection of small Jacobians than the single large one even if all the small Jacobians have to be evaluated. If one or more process is able to use Adams methods, the CPU reduction will be even greater.

There are of course some disadvantages. There are overheads in launching the slave processes. There are overheads in inter-process communication. When we have multiprocessors, we cannot keep them all fully occupied. There will be times when a process has to wait for another to communicate.

Discrete Partitioning has been extensively tested on a variety of systems. For systems with the right characteristics, extremely high speedups have been recorded. This makes it possible to apply analysis such as batch runs, Monte Carlo methods and optimization which were impossible without discrete partitioning.