Data parallelism performs the same operation simultaneously on separate portions of a dataset. It can reduce latency when those portions can be processed independently, then combined into a result. section 9.3.1
Sum an array in parallel
A sequential sum visits N elements one at a time. Instead, split the array into segments, sum each segment on a separate processing unit, and combine the partial sums. For 1,000 elements, the illustrative work per unit falls from roughly 1,000 instructions to 500 with two units or 250 with four; those figures describe the divided work, not a measured end-to-end speedup. section 9.3.1
Figure 9.4 Summing values of an array sequentially means stepping through each element one at a time. With data parallelism, you can reduce latency by summing subsets of the array in parallel.
The diagram contrasts a sequential array sum with concurrent sums over subsets of the array. section 9.3.1
Partitioning determines how useful the parallel work is. Choose independent, similarly sized chunks to balance work and limit communication; contiguous matrix blocks are preferable to scattered elements in the given example. SIMD instructions offer another scale of data parallelism: a 512-bit AVX-512 instruction can handle up to eight 64-bit integers, while GPUs can execute thousands of floating-point operations per clock cycle. More processing units create opportunities to divide work further, but the partition and the cost of combining results still matter. section 9.3.1 section 9.1
