CSC4700-Data Parallelism (2nd Part)

About this Video

• Video Title: CSC4700-Data Parallelism (2nd Part)
• Channel: Stellar at LSU
• Speakers: Unspecified
• Duration: 01:13:43

Introduction

This video lecture continues a discussion on data parallelism, introducing additional building blocks for data-parallel algorithms and illustrating their application through complex examples. The lecture focuses on improving performance by utilizing existing parallel implementations of these building blocks, such as those found in NumPy.

Key Takeaways

• Data Parallel Algorithm Building Blocks: The lecture expands on map, reduce, fold, and scan, introducing filter and sort, and briefly mentioning join, partition, and flatten. These building blocks operate on sequences of elements, leveraging existing parallel implementations for performance gains.
• Zip Iterator: A custom zip iterator in C++ is introduced to facilitate iteration over multiple sequences simultaneously. This simplifies the implementation of algorithms requiring operations on paired elements from different sequences.
• Gather and Scatter Operations: Gather and scatter operations are explained and implemented using the zip iterator, demonstrating how to efficiently copy elements from one array to another based on an index array. Hardware-level optimizations for these operations are also noted.
• Parallel Sort: The lecture differentiates between sort and stable_sort in C++, highlighting the importance of stable_sort when preserving order is crucial, especially when sorting based on one element of a zipped sequence (e.g., sorting employee records by name, then by salary).
• Parallel Filter (copy_if): The parallelization of copy_if is discussed, highlighting the need for a pre-processing step to determine output indices for each chunk of the input sequence. This involves using a bit vector, scan, and scatter operations.
• N-body Problem Example: The lecture concludes with a detailed example of parallelizing an N-body simulation using various approaches, including mutexes per cell, partial meshes, and a fully data-parallel approach using transform, sort, and optimized copying. Performance comparisons of these approaches are presented.