Show
Sequential vs. data-parallel job execution Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like arrays and matrices by working on each element in parallel. It contrasts to task parallelism as another form of parallelism. A data parallel job on an array of n elements can be divided equally among all the processors. Let us assume we want to sum all the elements of the given array and the time for a single addition operation is Ta time units. In the case of sequential execution, the time taken by the process will be n×Ta time units as it sums up all the elements of an array. On the other hand, if we execute this job as a data parallel job on 4 processors the time taken would reduce to (n/4)×Ta + merging overhead time units. Parallel execution results in a speedup of 4 over sequential execution. One important thing to note is that the locality of data references plays an important part in evaluating the performance of a data parallel programming model. Locality of data depends on the memory accesses performed by the program as well as the size of the cache. History[edit]Exploitation of the concept of data parallelism started in 1960s with the development of Solomon machine.[1] The Solomon machine, also called a vector processor, was developed to expedite the performance of mathematical operations by working on a large data array (operating on multiple data in consecutive time steps). Concurrency of data operations was also exploited by operating on multiple data at the same time using a single instruction. These processors were called 'array processors'.[2] In the 1980s, the term was introduced [3] to describe this programming style, which was widely used to program Connection Machines in data parallel languages like C*. Today, data parallelism is best exemplified in graphics processing units (GPUs), which use both the techniques of operating on multiple data in space and time using a single instruction. Description[edit]In a multiprocessor system executing a single set of instructions (SIMD), data parallelism is achieved when each processor performs the same task on different distributed data. In some situations, a single execution thread controls operations on all the data. In others, different threads control the operation, but they execute the same code. For instance, consider matrix multiplication and addition in a sequential manner as discussed in the example. Example[edit]Below is the sequential pseudo-code for multiplication and addition of two matrices where the result is stored in the matrix C. The pseudo-code for multiplication calculates the dot product of two matrices A, B and stores the result into the output matrix C. If the following programs were executed sequentially, the time taken to calculate the result would be of the (assuming row lengths and column lengths of both matrices are n) and for multiplication and addition respectively. // Matrix multiplication for (i = 0; i < row_length_A; i++) { for (k = 0; k < column_length_B; k++) { sum = 0; for (j = 0; j < column_length_A; j++) { sum += A[i][j] * B[j][k]; } C[i][k] = sum; } } // Array addition for (i = 0; i < n; i++) { c[i] = a[i] + b[i]; } We can exploit data parallelism in the preceding code to execute it faster as the arithmetic is loop independent. Parallelization of the matrix multiplication code is achieved by using OpenMP. An OpenMP directive, "omp parallel for" instructs the compiler to execute the code in the for loop in parallel. For multiplication, we can divide matrix A and B into blocks along rows and columns respectively. This allows us to calculate every element in matrix C individually thereby making the task parallel. For example: A[m x n] dot B [n x k] can be finished in instead of when executed in parallel using m*k processors. Data parallelism in matrix multiplication // Matrix multiplication in parallel #pragma omp parallel for schedule(dynamic,1) collapse(2) for (i = 0; i < row_length_A; i++){ for (k = 0; k < column_length_B; k++){ sum = 0; for (j = 0; j < column_length_A; j++){ sum += A[i][j] * B[j][k]; } C[i][k] = sum; } } It can be observed from the example that a lot of processors will be required as the matrix sizes keep on increasing. Keeping the execution time low is the priority but as the matrix size increases, we are faced with other constraints like complexity of such a system and its associated costs. Therefore, constraining the number of processors in the system, we can still apply the same principle and divide the data into bigger chunks to calculate the product of two matrices.[4] For addition of arrays in a data parallel implementation, let's assume a more modest system with two central processing units (CPU) A and B, CPU A could add all elements from the top half of the arrays, while CPU B could add all elements from the bottom half of the arrays. Since the two processors work in parallel, the job of performing array addition would take one half the time of performing the same operation in serial using one CPU alone. The program expressed in pseudocode below—which applies some arbitrary operation, if CPU = "a" then lower_limit := 1 upper_limit := round(d.length / 2) else if CPU = "b" then lower_limit := round(d.length / 2) + 1 upper_limit := d.length for i from lower_limit to upper_limit by 1 do foo(d[i]) In an SPMD system executed on 2 processor system, both CPUs will execute the code. Data parallelism emphasizes the distributed (parallel) nature of the data, as opposed to the processing (task parallelism). Most real programs fall somewhere on a continuum between task parallelism and data parallelism. Steps to parallelization[edit]The process of parallelizing a sequential program can be broken down into four discrete steps.[5]
Data parallelism vs. task parallelism[edit]
Data parallelism vs. model parallelism[edit]
[6] Mixed data and task parallelism[edit]Data and task parallelism, can be simultaneously implemented by combining them together for the same application. This is called Mixed data and task parallelism. Mixed parallelism requires sophisticated scheduling algorithms and software support. It is the best kind of parallelism when communication is slow and number of processors is large.[7] Mixed data and task parallelism has many applications. It is particularly used in the following applications:
Data parallel programming environments[edit]A variety of data parallel programming environments are available today, most widely used of which are:
Applications[edit]Data parallelism finds its applications in a variety of fields ranging from physics, chemistry, biology, material sciences to signal processing. Sciences imply data parallelism for simulating models like molecular dynamics,[9] sequence analysis of genome data [10] and other physical phenomenon. Driving forces in signal processing for data parallelism are video encoding, image and graphics processing, wireless communications [11] to name a few. See also[edit]
Notes[edit]
References[edit]
What is data parallelism with example?Data Parallelism means concurrent execution of the same task on each multiple computing core. Let's take an example, summing the contents of an array of size N. For a single-core system, one thread would simply sum the elements [0] . . . [N − 1].
What is data parallelism in operating system?Data parallelism refers to scenarios in which the same operation is performed concurrently (that is, in parallel) on elements in a source collection or array. In data parallel operations, the source collection is partitioned so that multiple threads can operate on different segments concurrently.
What is the difference between task parallelism and data parallelism?In data parallelism, the same instruction is performed repeatedly and simultaneously on different data. In task parallelism, the execution of different processes (threads) is distributed across multiple computing nodes.
What are the two types of parallelism?The definition of parallelism is based on the word “parallel,” which means “to run side by side with.” There are two kinds of parallelism in writing—parallelism as a grammatical principle and parallelism as a literary device.
|