Parallel Programming with Linked Data Structures

Speaker:  Yan Solihin – Orlando, FL, United States
Topic(s):  Architecture, Embedded Systems and Electronics, Robotics


Linked data structures (LDS) such as linked lists, trees, graphs, and hash tables, are used heavily in programs. They utilize pointers and rely on pointer chasing to traverse the data structures. Traditional loop-level parallelization is ineffective for LDS due to loop-carried dependence in the traversal loops. Consequently, a different parallelization strategy is needed. Parallelization can be pursued at a higher level, among the LDS primitives, such as traversal, node insertion, and node deletion. Pursuing parallelization at the LDS primitive level, however, requires a different way to reason about the correctness of operations, and requires fine-grain locking along with all its intricacies. LDS parallelization is a rarely covered topics in SC, and the aim of this tutorial is to cover techniques that can be used to achieve an effective parallelization strategy for LDS.

About this Lecture

Number of Slides:  100
Duration:  120 minutes
Languages Available:  English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.