Stanford CS149 I Parallel Computing I 2023 I Lecture 8 - Data-Parallel Thinking

Data Parallel Programming Concepts

• The remainder of the course will focus on writing code using operations that are known to be highly parallel, rather than focusing on low-level details like threads and dependencies. (3m30s)
• The concept of "sequences" will be used, which are ordered collections of elements that can only be accessed through specific operations, unlike arrays. (5m15s)

Data Types for Sequences

• Different programming languages have their own data types that embody the concept of sequences, such as std::sequence in C++, lists in Scala, dataframes and NumPy arrays in Python, and tensors in PyTorch and TensorFlow. (5m23s)

Higher-Order Functions for Parallelism

• Map is a higher-order function that takes a function F and a sequence s, partitions s into smaller subsequences, applies F to each subsequence in parallel, and concatenates the results. (12m46s)
• Fold, also known as foldLeft in Scala, is a higher-order function that takes a function f (which takes two arguments of types A and B and produces a B), a starting element B, and a sequence of elements of type A. It iteratively applies f to the elements of the sequence and the accumulator, producing a single output of type B. (13m27s)

Parallelizing Map and Fold

• The function argument of map only needs to handle a single element of the array, making it inherently parallelizable. (11m0s)
• Map can be implemented in parallel using techniques like SIMD processing or thread pools to handle arbitrarily large input sequences. (12m2s)
• Parallelizing fold requires the function f to be associative. If f is associative, a parallel implementation can split the input sequence, apply fold to the subsequences in parallel, and then combine the results using f. (17m40s)

Data Parallel Primitives

• Map is a primitive that applies a function to a sequence of numbers. For example, multiplying each number in a sequence by 10. (19m3s)
• Fold is a primitive that takes a sequence and reduces it to a single value using a binary operator, such as summing all elements in a sequence. (19m8s)
• Scan is a primitive that produces a sequence where each element is the result of applying a binary operator (like addition) to all elements up to and including the current element in the input sequence. (20m20s)

Parallel Summation on GPUs

• Parallel Summation on GPUs: The speaker discusses implementing a parallel sum operation on a GPU, aiming for a highly parallel solution with the same number of threads as elements. (25m48s)

Analyzing Algorithm Complexity

• Analyzing Algorithm Complexity: A sequential scan of an array of size 'n' has a cost of O(n), while a parallel scan using a combining tree approach initially results in O(n log n) work. (27m15s)

Optimizing Parallel Scan

• Optimizing Parallel Scan: An alternative algorithm, attributed to Guy Blelloch, maintains a logarithmic span while reducing the work complexity to O(n) by employing a two-phase approach with an "upsweep" and "downsweep" (combining and splatting tree) to efficiently compute partial sums. (28m38s)

Practical Considerations for Parallel Scan

• A scan algorithm implemented with an infinite number of processors would not be efficient in practice because it doesn't fully utilize all processors, and data movement can be inefficient. (31m57s)
• A simpler approach for parallelizing a scan on two cores involves dividing the array in half, performing sequential scans on each half, and then parallelizing the application of the base to the second half. (33m17s)
• A CUDA or ISPC implementation of a scan for SIMD architectures would involve each thread computing its lane, performing a logarithmic number of additions based on its lane index, with some threads becoming inactive as the computation progresses. (35m11s)

Work Efficiency vs. Utilization

• An algorithm that takes 10 cycles to complete work can be faster than one that takes 5 cycles if the computer has more execution units than the 5 cycle algorithm can utilize. (38m26s)
• When there are more threads than processing units, it can be beneficial to use a less work-efficient algorithm to ensure full utilization of processing power. (40m39s)

Example: Parallel Scan of 1024 Elements

• A scan of 1024 elements can be completed in 11 cycles by breaking the data into 32 element chunks, performing a scan on each chunk in parallel, scanning the results of each chunk, and then updating each element with the results of the second scan. (42m36s)

Optimizations in Data Parallel Primitives

• Sophisticated data parallel primitives are used to efficiently implement operations on machines. (43m30s)
• Nvidia likely uses these types of optimizations, particularly for larger Single Instruction Multiple Data (SIMD) widths, to improve power efficiency by a factor of 1.5 or more. (44m42s)

Segmented Scan

• Segmented scan, a common operation in applications dealing with sequences of sequences, like graphs or particle simulations, can be implemented efficiently by adapting the work-efficient scan algorithm. (46m41s)

Sparse Matrix Multiplication

• Compressed sparse row format stores sparse matrices by storing a sequence of nonzero values and their corresponding column indices. (51m19s)
• The format also includes an array indicating the starting index of each row's subsequence in the nonzero values and column indices arrays. (52m42s)
• To perform sparse matrix multiplication using this format, a "gather" operation can be used to create a new array containing the elements of the dense vector corresponding to the column indices of the nonzero values. (54m11s)
• A map operation then multiplies the nonzero values with the corresponding elements in the gathered array. (54m43s)
• Finally, a segmented scan operation sums the products across each row to obtain the final result. (54m57s)
• Sparse matrix multiplication can be parallelized by flattening the matrix and treating it as a data parallel computation. This approach is efficient when the number of non-zeros is significantly larger than the number of rows. (55m48s)

Gather and Scatter Operations

• Gather and scatter are essential data movement operations in data parallel thinking. Gather creates a dense output from a sparse input using an index sequence, while scatter distributes dense data to potentially sparse locations based on indices. (57m11s)
• A scatter operation, often used in histogram computations, can be implemented using a sort and segmented scan if a dedicated scatter operation is unavailable. (1h0m18s)

Data Structure for Particle Simulation

• The speaker describes a data structure that is a sequence of sequences, where the outer sequence represents a grid of cells and the inner sequences represent lists of particle IDs in each cell. (1h5m9s)

Parallelizing Particle Simulation

• A naive implementation to create this data structure would involve iterating over each particle, computing the cell it belongs to, and appending the particle ID to the corresponding cell list, potentially using a lock for synchronization. (1h6m3s)
• This naive implementation is deemed to have limited parallelism due to potential synchronization bottlenecks caused by the lock. (1h6m49s)
• To reduce contention for a shared lock in a parallel computing context, one solution is to create a separate cell list for each worker thread. (1h7m37s)
• An alternative approach involves implementing a lock for each individual cell to minimize collisions between threads accessing different cells. (1h8m16s)
• A high-performance parallel sorting algorithm can be employed to group particle indices by their corresponding grid cells, effectively achieving a group-by operation. (1h12m0s)

Creating a Uniform Grid

• To create a uniform grid in a data-parallel way, a data structure is created that stores the start and end indices of particles belonging to each cell in the grid. (1h13m41s)
• This data structure is constructed using a series of data-parallel operations: map, sort, and another map. (1h14m6s)

Libraries for Data Parallel Programming

• Libraries like Nvidia's Thrust for GPUs and Apache Spark for distributed programming provide high-level primitives (map, sort, scan, segmented scan) based on these data-parallel concepts. (1h16m35s)