I have an algorithm which is running in a sequential way however, I don't get the desired performance especially when it comes to execution time and i would like to remodel it to make it suitable for a distributed execution but i don't know who or where to start.
Any tips would be very much appreciated.
Following Flynn's taxonomy (https://en.wikipedia.org/wiki/Flynn%27s_taxonomy), the most immediate way to parallelize your code is to identify those sections of your algorithm that are Single Instruction Multiple Data (SIMD).
For example, imagine to have a vector (or list) of real numbers and you need to extract the square root of each element. Sequentially, you would do something like (imagine we don't have built-in libraries or functions):
for index in [0,len(list)):
list(index) = sqrt(list(index))
where [] means the bound in included and () the bound is not included. Here I used 0-based indexing as in C/C++ or python, using 1-based indexing as in Matlab it would be [1,len(list)].
In parallel, you would instead split the list in a number of sublists equal to the number of threads available, and then apply the previous loop to each sublist. Each sublist's loop is run at the same time in a different thread and results are pooled together at the hand.
Practically, there are different libraries and macros that help you parallelize your code. In C/C++ and Fortran, you should look at OpenMP (easier to learn) and MPI (steeper learning curve, but more powerful) for CPU-based parallelization, and to openACC (hardware agnostic, but not always as effective) or to CUDA (NVIDIA specific, but more powerful). If you're working with a different language or software (Python, Matlab, R, ...) there are language-specific libraries available that implement the previous paradigms (OpenMP, MPI, OpenACC, CUDA) and allow you to parallelize your code.
A final caveat: programming languages do not have the same flexibility and power with respect to parallel computing capabilities. C/C++ and Fortran are probably the best; Python is known to be poor when it comes to parallelization due to a built-in feature that prevents multi-threading (there are workarounds, though). Sometimes, to achieve significant speed-ups, changing language could be the best choice.
Expediting execution by choice of programming language and compilers is very effective. Changing a code written in one language to another may be a big job. However, in some cases where such changes are possible and one can use Fortran, the Intel compiler can be a welcome solution.
Happy computing.
Regards, T. DebRoy
- Badges
- Science topic
- Similar topics
- Biological Science
- Kinesiology
- Running