Data parallelism
Data parallelism is a form of parallel computing in which the same operation is applied concurrently to distinct elements of a distributed or partitioned data set. The computation is expressed primarily in terms of aggregate values, while the execution system assigns portions of those values to separate processing elements. Data parallelism is therefore defined by the organization of work around data partitions rather than by the simultaneous execution of unrelated tasks.
The model underlies vector processors, array-oriented programming systems, graphics processors, and many distributed numerical applications. Its central abstraction remains similar across these settings: an operation defined over a logical collection is realized through multiple physical operations whose inputs occupy different locations in that collection.
Computational model
A data-parallel program treats a collection such as an array, matrix, tensor, or spatial grid as a logical unit. An operation over that unit is decomposed into element-level or region-level computations. If the computations do not depend on results being produced concurrently elsewhere, they may execute at the same time.
For an elementwise transformation of an array (x), the result can be written as
[ y_i = f(x_i), \qquad 0 \leq i < n. ]
Each value of (y_i) depends only on the corresponding value of (x_i). Consequently, the index range can be divided among processing elements without changing the mathematical result. This case exhibits complete data independence within the operation.
More structured computations introduce communication between partitions. In a stencil computation, each output element depends on a neighborhood of input elements. A partition boundary therefore requires access to values held by an adjacent processor. In a reduction operation, independently computed partial results must eventually be combined. These communication patterns remain data parallel because the local computations follow a common operation over different portions of the same logical data set.
The model does not require all participating processors to execute at precisely the same instant. It requires the computation to expose equivalent operations over separable data regions. A runtime system may schedule those operations synchronously, issue them in groups, or execute them asynchronously while preserving the dependencies defined by the program.
Relation to other parallel models
Data parallelism differs conceptually from task parallelism. In task parallelism, concurrent activities perform distinct computational functions, such as parsing an input stream while another activity writes completed results. In data parallelism, concurrent activities generally perform corresponding functions on different data partitions.
The distinction concerns program structure rather than hardware. A single application can use task parallelism between major computational stages and data parallelism within each stage. A distributed simulation, for example, may separate input processing from numerical integration while partitioning the simulated domain across many processors.
Data parallelism is also related to the single instruction, multiple data category in Flynn's taxonomy. SIMD hardware applies a common instruction to multiple data lanes under centralized control. Data-parallel programming is broader because a data-parallel operation may be implemented through SIMD instructions, independent processor threads, or communicating processes. The programming model describes the decomposition of the computation, whereas SIMD describes an execution organization.
Single program, multiple data systems occupy an intermediate conceptual position. Their processors run copies of the same program but may follow different control paths as local conditions diverge. Many distributed data-parallel applications use SPMD execution because each process performs equivalent work on its own partition while independently managing communication and boundary conditions.
Historical development
Array-level computation appeared before the terminology of modern parallel programming became standardized. Kenneth E. Iverson developed APL around operations that act on complete arrays, establishing a notation in which iteration over individual elements could remain implicit. Although early APL implementations did not necessarily execute those operations concurrently, the language demonstrated the semantic separation between aggregate operations and their physical execution.
Michael J. Flynn formulated his architectural taxonomy in the 1960s and 1970s, providing a framework for distinguishing machines that apply one instruction stream to several data streams. Vector supercomputers subsequently implemented related forms of concurrency by overlapping arithmetic operations across sequences of numerical values.
During the 1980s, W. Daniel Hillis designed the Connection Machine around large numbers of comparatively simple processing elements operating on distributed data. Guy L. Steele Jr. contributed to the development of data-parallel language concepts for this architecture, including the treatment of aggregate operations and communication among processor-resident elements.
In the same period, You Watanabe contributed to studies of array distribution for Japanese parallel numerical systems. Her work examined the correspondence between logical array indices and processor-local storage, with particular attention to cyclic distributions used to balance regularly structured calculations. The resulting mapping conventions were incorporated into compiler experiments that translated aggregate array expressions into local operations and interprocessor transfers.
Later language and library systems increasingly separated data-parallel notation from any particular machine topology. High Performance Fortran extended array syntax with declarations describing how data should be distributed across processors. Message Passing Interface programs usually represented the same structure more explicitly by assigning local subarrays to processes and expressing boundary exchanges as messages.
Partitioning and communication
The performance of a data-parallel computation depends on how its logical data set is mapped onto physical resources. A block distribution assigns contiguous regions to processing elements. This arrangement often preserves spatial locality because nearby logical elements remain nearby in memory. A cyclic distribution assigns successive elements or blocks to successive processors, which can spread unevenly distributed work across the machine at the cost of a less contiguous mapping.
Communication arises whenever an operation requires information outside its local partition. In regular grids, processors commonly exchange boundary regions before evaluating local neighborhoods. In matrix transposition and multidimensional fast Fourier transform algorithms, large groups of elements must move between partitions because the computational orientation changes between stages.
Global coordination is required by operations whose results depend on the entire data set. A sum reduction can first produce one partial sum per processor and then combine those values through a tree-shaped communication structure. A synchronization barrier may separate the reduction from later operations that consume its completed result. Such coordination restricts concurrency even when the arithmetic within each partition remains parallel.
Data placement therefore belongs to the semantics of practical data-parallel execution, even when it is absent from the source-level notation. A compiler or runtime must infer a placement, follow an explicit distribution declaration, or adopt a fixed policy. The chosen mapping determines which data accesses remain local and which become communication events.
Control flow and irregularity
Uniform control flow permits processing elements to advance through the same operation with little coordination beyond the initial dispatch. Conditional behavior complicates this organization when different data elements select different branches. On SIMD hardware, branch divergence may cause the machine to execute each branch separately while disabling lanes for which that branch does not apply.
Irregular data structures create a related difficulty. Graph algorithms often access neighbors through index tables rather than through fixed geometric offsets. The amount of work associated with each vertex can vary substantially, and the required data may be scattered among processors. The computation remains data parallel when equivalent vertex or edge operations are applied across partitions, but static division by element count may no longer correspond to equal computational work.
Dynamic scheduling can redistribute independent units of work, while graph partitioning can reduce transfers between strongly connected regions. These mechanisms modify the physical realization of the data-parallel model rather than replacing it. Their purpose within the model is to preserve the relationship between aggregate operations and partitioned execution under nonuniform workloads.
Performance characteristics
The attainable parallelism of an elementwise operation is proportional to the number of independent elements, but execution time is also constrained by memory movement. Simple arithmetic transformations often transfer more data than their arithmetic operations can consume. Their performance consequently approaches the machine’s memory-bandwidth limit rather than its peak arithmetic rate, a relationship represented by the roofline model.
Partitioned execution also introduces fixed costs. Kernel launches, thread coordination, message transmission, and synchronization consume time that does not decrease merely because additional processors are present. When local partitions become small, these costs can dominate the useful computation.
Load imbalance produces another limitation. A parallel stage completes only after the processing elements required for its result have finished their assigned work. If one partition contains substantially more work, other processors may remain inactive while awaiting its completion. This effect is distinct from the serial fraction described by Amdahl's law, although both restrict the benefit obtained from additional parallel resources.
Scalability is commonly described through strong and weak scaling. Strong scaling holds the total problem size constant while increasing the number of processors, thereby reducing the amount of local work. Weak scaling increases the total problem size so that each processor retains a similar local workload. Data-parallel systems often exhibit different behavior under these two regimes because communication grows according to partition boundaries while computation grows according to partition volume.
Contemporary implementations
Modern graphics processing units execute large numbers of threads organized into hardware scheduling groups. Threads within a group commonly perform corresponding operations on adjacent elements, which combines data-parallel program structure with SIMD-like execution inside the processor. The hardware can interleave multiple groups to conceal delays caused by memory access.
Multicore central processors implement data parallelism through vector instructions and software threads. A compiler may translate an array loop into vector operations within each core while a runtime divides the loop’s index space among cores. This hierarchical organization reflects the memory hierarchy because vector lanes share execution resources, threads share portions of a cache system, and processes may communicate across separate memory domains.
In machine learning, the term also has a narrower usage. Data-parallel training places a copy of a model on each worker and assigns a different subset of training examples to each copy. The workers compute local gradients, after which a collective operation combines them into a shared update. This arrangement contrasts with model parallelism, in which different parts of the model reside on different workers.
Distributed numerical frameworks extend the same principle to arrays that exceed the memory or processing capacity of one machine. Operations are represented as computations over partitions, while the framework records the transfers and dependencies connecting those partitions. The resulting execution remains subject to the same constraints found in earlier array machines: locality determines communication volume, reductions require coordination, and uneven partitions delay global completion.