Parallel implementation

Basic concepts regarding parallel implementation

What it is a parallel implementation?

It is a computer program based on a parallel algorithm, that will be executed in a computer with more than one processor.

The existence of a parallel algorithm depends on the characteristic of the problem to be solved. There are problems that to execute step number N it is imperative that first the step of number N-1 has finished. One of the reasons that it can happen is that one of the values used to make a calculation on step N is indeed calculated in step N-1. Therefore, it is not possible to the processor execute step N without knowing the value calculated on step N-1. So N and N-1 can not be executed at the same time.

A way to develop a parallel algorithm is to analyze the steps that must be execute to solve the problem and to verify if each step depends on some previous step. If it does not depend, then it is possible to leave a processor executing this step while other processors execute the remaining portion and be advancing the work. This way, it diminishes the total time necessary to execute the whole problem.

Figure: In a parallel algorithm more than one person is following the receipt at a specific moment.


What it is a shared memory multiprocessor?

It is a computer with more than a processor that can have access the same memory. The majority of the existing computers currently possess only one processor. This is the case of the personal computers, most common it is the Intel Pentium processor. In the case of a multiprocessor, there are more than one programs being executed at the same time and having access to the same memory. In this in case,special care is taken so that the processors do not have access one same position of memory at the same time, for example.