CODEWITHSUNDEEP
parallel-processing
Dervin Thunk
Dervin Thunk

Reputation: 20119

What is the relationship between vectorization and embarrasingly parallel?

The question says it all. It seems to me that vectorization is very closely related to embarrassingly parallel problems. In other words, all vectorizeable programs must be embarrassingly parallel programs. Is this correct?

Upvotes: 6

Views: 6740

Answers (3)

minjang
minjang

Reputation: 9050

A quick summary for embarrassingly parallelism:

A code is embarrassingly parallel if the code can be parallelized without any efforts, especially handling data dependency. Note that embarrassingly parallelism only means that the code will be safely parallelized without effort; it doesn't guarantee any optimal performance.

A simple example would be summation of two vectors.

// A, B, and C are all distinct arrays.    
for (int i = 0; i < N; ++i)
  C[i] = A[i] + B[i];

This code is embarrassingly parallel because there is no data dependency on C. This code can be simply parallelized, for example, by using OpenMP:

#pragma omp parallel for 
for (int i = 0; i < N; ++i)
  C[i] = A[i] + B[i];

Vectorization is a particular form of how parallelism is achieved. In particular, vectorization mostly uses dedicated SIMD execution hardware units in processors using specialized instructions such as x86 SSE/AVX and ARM NEON. Compilers may automatically vectorize your code, or you can manually vectorize using intrinsics and direct assembly code.

I don't think that vectorization necessarily means that the code to be vectorized must be embarrassingly parallel. But, in practice, most vectorizable code is embarrassingly parallel because virtually all SIMD instructions assume that. I can't find any SIMD instructions that allow data dependent operations. In that sense, yes, you can say that vectorizable programs need to be embarrassingly parallel.

However, in a broad sense, vectorization could embrace GPGPU-style SIMD programming such as Nvidia's CUDA and Intel's MIC architecture. They allow more flexible SIMD operations by handling data-dependent operations and branches.

To summarize, in a narrow definition of the vectorization, i.e., vectorization for conventional CPU's SIMD operations, I believe that vectorizable programs should be embarrassingly parallel. However, an advanced form of SIMD/vectorization could enable data-dependent operations and arbitrary branches.

Upvotes: 6

SunnyChattha
SunnyChattha

Reputation: 195

Parallelism is to use our computing devices as much as possible, so we try to schedule tasks in such a way so that their execution is almost independent of each other.

Now, Vectorization, in parallel computing, is a special case of parallelization, in which software programs that by default perform one operation at a time on a single thread are modified to perform multiple operations simultaneously.

Vectorization is the more limited process of converting a computer program from a scalar implementation, which processes a single pair of operands at a time, to a vector implementation which processes one operation on multiple pairs of operands at once.

lets take a simple example of addition of two arrays:

in normal mode, we need a loop to add the two arrays. We can make it parallel in many ways, like we can make two threads and divide the arrays in two equal parts and assign to threads respectively. Now, maximum no. of threads that can increase performance is equal to the no. of nodes of array or length of array. And if we apply parallelism then it should not need to loop all the array to add it. it should launch only one command and both the array will be added. To do this, we need to make the array addition program parallel in such a way so that it doesnot need any loop. for this we will divide arrays into portions equal to length of array and assign each portion to a new thread and launch all of them simultaneously so that all additions occur under a single instruction without looping at a same time.

FOr a rutine to be completely vectorized, it must be embarassingly parallel like in the above example. But it depends on the given scenerio. for two rutines having interdependencies, they can be individualy vectorized, etc.

Upvotes: 0

Richard A.
Richard A.

Reputation: 1157

Embarrassingly parallel problems are tasks that require no effort to write in parallel form. Vectorisation is the process by which a conventional procedure becomes parallel.

So, this isn't a case of one being a logical sub-type of another, but a trend. The closer a problem is to being embarrassingly parallel, the less vectorisation is required.

Upvotes: 3

Related Questions