Fundamentals of Parallel Multicore Architecture

Chapter 4

Parallel Programming for Linked Data Structures

Contents

4.1   Parallelization Challenges in LDS

4.1.1   Loop-Level Parallelization is Insufficient

4.2   Approaches to Parallelization of LDS

4.2.1   Parallelizing Computation vs. Traversal

4.2.2   Parallelizing Operations on the Data Structure

4.3   Parallelization Techniques for Linked Lists

4.3.1   Parallelization among Readers

4.3.2   Parallelism among LDS Traversals

4.3.3   Fine-Grain Lock Approach

4.4   The Role of Transactional Memory

4.5   Exercises

In Chapter 3, we have discussed parallel programming techniques that are applicable for applications that rely on matrices as their data structures. Accesses to a matrix are characterized by a nest of loops in which each loop iterates ...